Given a stochastic matrix P partitioned in four blocks Pij, i,j=1,2, Kemeny's constant κ(P) is expressed in terms of Kemeny's constants of the stochastic complements P1=P11+P12(I−P22)−1P21, and P2=P22+P21(I−P11)−1P12. 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.
On Kemeny's constant and stochastic complement
Bini Dario Andrea.;Durastante F.
;Kim Sooyeong;Meini Beatrice
2024-01-01
Abstract
Given a stochastic matrix P partitioned in four blocks Pij, i,j=1,2, Kemeny's constant κ(P) is expressed in terms of Kemeny's constants of the stochastic complements P1=P11+P12(I−P22)−1P21, and P2=P22+P21(I−P11)−1P12. 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
