Completion Problems and Sparsity for Kemeny's Constant

2023/08/20 by Stephen Kirkland, Kirkland, Stephen · 1 citation
Computer Science · Engineering · Mathematics · #15A83 #15B51 #60J10 #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Probability (math.PR) #Spectral Theory (math.SP) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2308.10259

openalex publication_date 2023/08/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a partially specified stochastic matrix, we consider the problem of completing it so as to minimize Kemeny's constant. We prove that for any partially specified stochastic matrix for which the problem is well-defined, there is a minimizing completion that is as sparse as possible. We also find the minimum value of Kemeny's constant in two special cases: when the diagonal has been specified, and when all specified entries lie in a common row.

Cited by

• Kemeny's constant minimization for reversible Markov chains via structure-preserving perturbations

Related

• Kemeny's constant minimization for reversible Markov chains via structure-preserving perturbations
• Sharp Bounds for Multiple Models in Matrix Completion
• A Spectral Approach to Kemeny's Constant
• A deterministic theory of low rank matrix completion
• Fast matrix completion without the condition number