Tree formulas, mean first passage times and Kemeny's constant of a Markov chain
Preprint
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 $\textbf{t}$ spanning $S$ with root $j$ and edges $i \rightarrow k$ directed to $j$, of the tree product $\prod_{i \rightarrow k \in \textbf{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,\textbf{t})$ is the last state before $j$ in the path from $i$ to $j$ in $\textbf{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 $\textbf{f}$ labeled by $S$ with $r$ trees, of the product of $p_{ij}$ over edges $i \rightarrow j$ of $\textbf{t}$. We show that these results can be derived without appeal to the matrix tree theorem. A list of relevant literature is also reviewed.
Keywords
All Related Versions
This publication has 48 references indexed in Scilit:
- Generalized loop‐erased random walks and approximate reachabilityRandom Structures & Algorithms, 2012
- Recurrence of Distributional Limits of Finite Planar Graphs2011
- The Kemeny Constant for Finite Homogeneous Ergodic Markov ChainsJournal of Scientific Computing, 2010
- Forest Volume Decompositions and Abel–Cayley–Hurwitz Multinomial ExpansionsJournal of Combinatorial Theory, Series A, 2002
- Spanning tree formulas and chebyshev polynomialsGraphs and Combinatorics, 1986
- A combinatorial approach to matrix algebraDiscrete Mathematics, 1985
- Enumeration ofQ-acyclic simplicial complexesIsrael Journal of Mathematics, 1983
- The frequency of cyclic processes in biological multistate systemsJournal of Mathematical Biology, 1980
- Line-digraphs, arborescences, and theorems of tutte and knuthJournal of Combinatorial Theory, Series B, 1978
- A certain polynomial of a graph and graphs with an extremal number of treesJournal of Combinatorial Theory, Series B, 1974