Tree formulas, mean first passage times and Kemeny's constant of a Markov chain

In this paper, we aim to provide probabilistic and combinatorial insights into tree formulas for the Green function and hitting probabilities of Markov chains on a finite state space. These tree formulas are closely related to loop-erased random walks by Wilson’s algorithm for random spanning trees, and to mixing times by the Markov chain tree theorem. Let $m_{ij}$ be the mean first passage time from $i$ to $j$ for an irreducible chain with finite state space $S$ and transition matrix $(p_{ij};i,j\in S)$. It is well-known that $m_{jj}=1\mathrm{/}{\pi }_j={\mathrm{\Sigma }}^{(1)}\mathrm{/}{\mathrm{\Sigma }}_j$, where $\pi$ is the stationary distribution for the chain, ${\mathrm{\Sigma }}_j$ is the tree sum, over $n^{n-2}$ trees $\mathbf{\text{t}}$ spanning $S$ with root $j$ and edges $i\to k$ directed to $j$, of the tree product ${\prod }_{i\to k\in \mathbf{\text{t}}}{p}_{ik}$, and ${\mathrm{\Sigma }}^{(1)}:={\sum }_{j\in S}{\mathrm{\Sigma }}_j$. Chebotarev and Agaev derived further results from {\em Kirchhoff’s matrix tree theorem}. We deduce that for $i \ne j$,$m_{ij} = \Sigma_{ij}/\Sigma_j$,where$\Sigma_{ij}$ is the sum over the same set of $n^{n-2}$ spanning trees of the same tree product as for ${\mathrm{\Sigma }}_j$, except that in each product the factor $p_{kj}$ is omitted where $k = k(i,j,$\mathbf{\text{t}}$)$isthelaststatebefore$j$inthepathfrom$i$to$j$in$$\mathbf{\text{t}}$$\mathrm{.}ItfollowsthatKemen{y}^{\mathrm{\prime }}sconstant$\sum_{j \in S} m_{ij}/m_{jj}$equalsto$ \Sigma^{(2)}/\Sigma^{(1)}$,where$\Sigma^{®}$ is the sum, over all forests $\mathbf{\text{f}}$ labeled by $S$ with $r$ trees, of the product of $p_{ij}$ over edges $i\to j$ of $\mathbf{\text{t}}$. We show that these results can be derived without appeal to the matrix tree theorem. A list of relevant literature is also reviewed.