[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

Show that, for an ergodic Markov chain (see Theorem),

[[math]] \sum_j m_{ij} w_j = \sum_j z_{jj} - 1 = K\ . [[/math]]

The second expression above shows that the number [math]K[/math] is independent of [math]i[/math]. The number [math]K[/math] is called Kemeny's constant. A prize was offered to the first person to give an intuitively plausible reason for the above sum to be independent of [math]i[/math]. (See also Exercise \ref{exer 11.5.27}.)