The Role of Kemeny's Constant in Properties of Markov Chains

Abstract

In a finite irreducible Markov chain with stationary probabilities {π i } and mean first passage times m ij (mean recurrence time when i = j) it was first shown, by Kemeny and Snell (1960 Kemeny , J. G. , Snell , J. L. ( 1960 ). Finite Markov Chains . Princeton, NJ : Van Nostrand . Republished (1976) as Finite Markov Chains: With a New Appendix Generalization of a Fundamental Matrix. New York: Springer-Verlag . [Google Scholar]), that is a constant, K, (Kemeny's constant) not depending on i. A variety of techniques for finding expressions and bounds for K are given. The main interpretation focuses on its role as the expected time to mixing in a Markov chain. Various applications are considered including perturbation results, mixing on directed graphs and its relation to the Kirchhoff index of regular graphs.