On Kemeny's constant and stochastic complement.

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. • Expression of Kemeny's constant employing the constants of stochastic complements. • New recursive algorithms for computing Kemeny's constant. • Application of the new expression to structured transition matrices. [ABSTRACT FROM AUTHOR]