The role of Kemeny's constant in properties of Markov chains

Date
2011
Authors
Hunter, JJ
Supervisor
Item type
Conference Contribution
Degree name
Journal Title
Journal ISSN
Volume Title
Publisher
MSM Conference
Abstract

In a finite m-state irreducible Markov chain with stationary probabilities {πi} and mean first passage times mij (mean recurrence time when i = j) it was first shown, by Kemeny and Snell, that the sum, over j, of πj and mij is a constant, K, not depending on i. This constant has since become known as Kemeny’s constant. We consider a variety of techniques for finding expressions for K, derive some bounds for K, and explore various applications and interpretations of these results. Interpretations include the expected number of links that a surfer on the World Wide Web located on a random page needs to follow before reaching a desired location, as well as the expected time to mixing in a Markov chain. Various applications have been considered including some perturbation results, mixing on directed graphs and its relation to the Kirchhoff index of regular graphs.

Description
Keywords
Markov chains , Kemeny’s constant , Mixing times , Perturbations , Regular graphs
Source
Markov & Semi-Markov Processes & Related Fields, MSMPRF 2011, Sithonia, Greece, 2011-09-20 - 2011-09-23
DOI
Rights statement
NOTICE: this is the author’s version of a work that was accepted for publication. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in (see Citation). The original publication is available at (see Publisher's Version)