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), 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.

Keywords:

• Directed graphs
• Markov chains
• Mixing
• Kemeny constant
• Kirchhoff index

Mathematics Subject Classification:

• 60J10