[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]

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). Choose a target state according to the fixed vector [math]\mat{w}[/math]. Start from state [math]i[/math] and wait until the time [math]T[/math] that the target state occurs for the first time. Let [math]K_i[/math] be the expected value

of [math]T[/math]. Observe that

[[math]] K_i + w_i \cdot 1/w_i= \sum_j P_{ij} K_j + 1\ , [[/math]]

and hence

[[math]] K_i = \sum_j P_{ij} K_j\ . [[/math]]

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

Notes