Kemeny's constant

For a finite ergodic Markov chain[4] with transition matrix P and invariant distribution π, write m_ij for the mean first passage time from state i to state j (denoting the mean recurrence time for the case i = j). Then

${\displaystyle K=\sum _{j}\pi _{j}m_{ij}}$

is a constant and not dependent on i.[5]

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 K_i be the expected value of T. Observe that

${\displaystyle K_{i}+w_{i}\cdot 1/w_{i}=\sum _{j}P_{ij}K_{j}+1}$

and hence

${\displaystyle K_{i}=\sum _{j}P_{ij}K_{j}.}$

By the maximum principle, K_i is a constant. Should Peter have been given the prize?