Introduction to Probability · Problem 11.19

Random Walks — Grinstead & Snell

Mathematics — Probability · markov-chains-kemeny-constant

Problem

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

\sum_j m_{ij} w_j = \sum_j z_{jj} - 1 = K.

The second expression above shows that the number

K

is independent of

i

. The number

K

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

i

. (See also Exercise 24.)