In probability theory, Kemeny’s constant is the expected number of time steps required for a Markov chain to transition from a starting state i to a random destination state sampled from the Markov chain's stationary distribution. Surprisingly, this quantity does not depend on which starting state i is chosen.[1] It is in that sense a constant, although it is different for different Markov chains. When first published by John Kemeny in 1960 a prize was offered for an intuitive explanation as to why quantity was constant.[2][3]
Definition
For a finite ergodic Markov chain[4] with transition matrix P and invariant distribution π, write mij for the mean first passage time from state i to state j (denoting the mean recurrence time for the case i = j). Then
\( K = \sum_{j} \pi_j m_{ij} \)
is a constant and not dependent on i.[5]
Prize
Kemeny wrote, (for i the starting state of the Markov chain) “A prize is offered for the first person to give an intuitively plausible reason for the above sum to be independent of i.”[2] Grinstead and Snell offer an explanation by Peter Doyle as an exercise, with solution “he got it!”[6][7]
In the course of a walk with Snell along Minnehaha Avenue in Minneapolis in the fall of 1983, Peter Doyle suggested the following explanation for the constancy of Kemeny's constant. Choose a target state according to the fixed vector w. Start from state i and wait until the time T that the target state occurs for the first time. Let Ki be the expected value of T. Observe that
\( K_i+w_i \cdot 1/w_i = \sum_j P_{ij}K_j + 1 \)
and hence
\( K_i = \sum_j P_{ij}K_j. \)
By the maximum principle, Ki is a constant. Should Peter have been given the prize?
References
Crisostomi, E.; Kirkland, S.; Shorten, R. (2011). "A Google-like model of road network dynamics and its application to regulation and control". International Journal of Control. 84 (3): 633. doi:10.1080/00207179.2011.568005.
Kemeny, J. G.; Snell, J. L. (1960). Finite Markov Chains. Princeton, NJ: D. Van Nostrand. (Corollary 4.3.6)
Catral, M.; Kirkland, S. J.; Neumann, M.; Sze, N.-S. (2010). "The Kemeny Constant for Finite Homogeneous Ergodic Markov Chains" (PDF). Journal of Scientific Computing. 45 (1–3): 151–166. CiteSeerX 10.1.1.295.9600. doi:10.1007/s10915-010-9382-1.
Levene, Mark; Loizou, George (2002). "Kemeny's Constant and the Random Surfer" (PDF). The American Mathematical Monthly. 109 (8): 741–745. CiteSeerX 10.1.1.305.937. doi:10.2307/3072398. JSTOR 3072398.
Hunter, Jeffrey J. (2012). "The Role of Kemeny's Constant in Properties of Markov Chains". Communications in Statistics - Theory and Methods. 43 (7): 1309–1321. arXiv:1208.4716. doi:10.1080/03610926.2012.741742.
Grinstead, Charles M.; Snell, J. Laurie. Introduction to Probability (PDF).
"Two exercises on Kemeny's constant" (PDF). Retrieved 1 March 2013.[permanent dead link]
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
