Introduction to Probability · Problem 11.24

Random Walks — Grinstead & Snell

Mathematics — Probability · markov-chains-kemeny-constant

Problem

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 (see Exercise 19). Choose a target state according to the fixed vector

\mathbf{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

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,

K_i

is a constant. Should Peter have been given the prize?

Related theory

Markov Chains Transition Matrices And Stationary Distributions

Browse the problem library