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

Abstract

In a finite state 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 \sum_j π_j m_(ij) is a constant K, not depending on i. This constant has since become known as Kemeny's constant. A variety of techniques for finding expressions and various bounds for K are derived. 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.

13 pages

References in corpus (2)

• The Kemeny constant of a Markov chain
• The Distribution of Mixing Times in Markov Chains

Cited by in corpus (23)

• On the spectrum of the normalized Laplacian of iterated triangulations of graphs
• The normalized Laplacian spectrum of subdivisions of a graph
• Tree formulas, mean first passage times and Kemeny's constant of a Markov chain
• Correlation Functions, Mean First Passage Times and the Kemeny Constant
• Exact results for the first-passage properties in a class of fractal networks
• Large deviations for the Skew-Detailed-Balance Lifted-Markov processes to sample the equilibrium distribution of the Curie-Weiss model
• Hitting Time Quasi-metric and Its Forest Representation
• Efficient Algorithms for Minimizing the Kirchhoff Index via Adding Edges
• Spectra, hitting times, and resistance distances of $q$-subdivision graphs
• Kemeny's Function for Markov Chains and Markov Renewal Processes
• The Meeting Time of Multiple Random Walks
• On the Kemeny time for continuous-time reversible and irreversible Markov processes with applications to stochastic resetting and to conditioning towards forever-survival
• Robotic Surveillance Based on the Meeting Time of Random Walks
• Hitting times and resistance distances of $q$-triangulation graphs: Accurate results and applications
• Markov Chain-Based Stochastic Strategies for Robotic Surveillance
• Edge corona product as an approach to modeling complex simplical networks
• Extended corona product as an exactly tractable model for weighted heterogeneous networks
• A Computational Framework for the Mixing Times in the QBD Processes with Infinitely-Many Levels
• The normalized Laplacian and related indexes of graphs with edges blew up by cliques
• The normalized Laplacians and random walks of the parallel subdivision graphs
• Heterogeneous Mean First-Passage Time Scaling in Fractal Media
• Normalized Laplacian spectra of central vertex join and central edge join of graphs
• The normalized Laplacian spectra of subdivision vertex-edge neighbourhood vertex(edge)-corona for graphs