A combinatorial perspective on the Kemeny constant and more

Abstract

Let $M$ be an irreducible transition matrix on a finite state space $V$. For a Markov chain $C=(C_k,k\ge 0)$ with transition matrix $M$, let $\ddot{I}{„}_u^{\ge 1}$ denote the first positive hitting time of $u$ by $C$, and $\ddot{I}$ the unique invariant measure of $M$. Kemeny proved that if $X$ is sampled according to $\ddot{I}$ independently of $C$, the expected value of the first positive hitting time of $X$ by $C$ does not depend on the starting state of the chain: all the values $(E(\ddot{I}{„}_X^{\ge 1}|C_0=u),u\in V)$ are equal. \par In this paper, we show that this property follows from a more general result: the generating function ${\sum }_{v\in V}E(x^{\ddot{I}{„}_v^{\ge 1}}|C_0=u)\det (Id-x{M}^{(v)})$ is independent of the starting state $u$, where $M^{(v)}$ is obtained from $M$ by deleting the row and column corresponding to the state $v$. The factors appearing in this generating function are: first, the probability generating function of $\ddot{I}{„}_v^{\ge 1}$, and second, the sequence of determinants $(det(Id-x{M}^{(v)}),v\in V),$ which, for $x=1$, is known to be proportional to the invariant measure $(\ddot{I}{}_u,u\in V)$. From this property, we deduce several further results, including relations involving higher moments of $\ddot{I}{„}_X^{\ge 1}$, which are of independent interest.

13 pages, 1 figure