On Kemeny's constant and stochastic complement
Dario A. Bini, Fabio Durastante, Sooyeong Kim, Beatrice Meini · Linear Algebra and its Applications · 2024
Given a stochastic matrix P partitioned in four blocks P i j , i , j = 1 , 2 , Kemeny's constant κ ( P ) is expressed in terms of Kemeny's constants of the stochastic complements P 1 = P 11 + P 12 ( I − P 22 ) − 1 P 21 , and P 2 = P 22 + P 21 ( I − P 11 ) − 1 P 12 . Specific cases concerning periodic Markov chains and Kronecker products of stochastic matrices are investigated. Bounds to Kemeny's constant of perturbed matrices are given. Relying on these theoretical results, a divide-and-conquer algorithm for the efficient computation of Kemeny's constant of graphs is designed. Numerical experiments performed on real world problems show the high efficiency and reliability of this algorithm.