### - Art Gallery -

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. 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.
Definition

For a finite ergodic Markov chain 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.
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.” Grinstead and Snell offer an explanation by Peter Doyle as an exercise, with solution “he got it!”

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]