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

Abstract

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/{\pi }_j={\Sigma }^{(1)}/{\Sigma }_j$, where $\pi$ is the stationary distribution for the chain, ${\Sigma }_j$ is the tree sum, over $n^{n-2}$ trees $\text{t}$ spanning $S$ with root $j$ and edges $i\to k$ directed to $j$, of the tree product ${\prod }_{i\to k\in \text{t}}{p}_{ik}$, and ${\Sigma }^{(1)}:={\sum }_{j\in S}{\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 ${\Sigma }_j$, except that in each product the factor $p_{kj}$ is omitted where $k=k(i,j,\text{t})$ is the last state before $j$ in the path from $i$ to $j$ in $\text{t}$. It follows that Kemeny's constant ${\sum }_{j\in S}{m}_{ij}/m_{jj}$ equals to ${\Sigma }^{(2)}/{\Sigma }^{(1)}$, where ${\Sigma }^{(r)}$ is the sum, over all forests $\text{f}$ labeled by $S$ with $r$ trees, of the product of $p_{ij}$ over edges $i\to j$ of $\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.

29 pages, 2 figures. This paper is published by https://projecteuclid.org/euclid.bj/1517540464

References in corpus (3)

• Forest matrices around the Laplacian matrix
• Fast Generation of Random Spanning Trees and the Effective Resistance Metric
• Laplacian matrices and spanning trees of tree graphs

Cited by in corpus (8)

• Exact results for the first-passage properties in a class of fractal networks
• Hitting Time Quasi-metric and Its Forest Representation
• Analytic relationship of relative synchronizability to network structure and motifs
• On resistance distance of Markov chain and its sum rules
• Analytical results for the distribution of first-passage times of random walks on random regular graphs
• Exact and Approximate Mean First Passage Times on Trees and other Necklace Structures: a Local Equilibrium Approach
• Information retrieval and structural complexity of legal trees
• On the Kemeny time for continuous-time reversible and irreversible Markov processes with applications to stochastic resetting and to conditioning towards forever-survival