A graph theoretic interpretation of the mean first passage times

Abstract

Let $m_{ij}$ be the mean first passage time from state $i$ to state $j$ in an $n$-state ergodic homogeneous Markov chain with transition matrix $T$. Let $G$ be the weighted digraph without loops whose vertex set coincides with the set of states of the Markov chain and arc weights are equal to the corresponding transition probabilities. We give a graph-theoretic interpretation to $m_{ij}$. Namely, We show that $m_{ij}=f_{ij}/q_j$ if $i\ne j$ and $m_{ij}=1/{\tilde{q}}_j$ if $i=j$, where $f_{ij}$ is the total weight of 2-tree spanning converging forests in $G$ that have one tree containing $i$ and the other tree converging to $j$, $q_j$ is the total weight of spanning trees converging to $j$ in $G$, and ${\tilde{q}}_j=q_j/{\sum }_{k=1}^n{q}_k$. The result is illustrated by an example. Keywords: Markov chain; Mean first passage time; Spanning rooted forest; Matrix forest theorem; Laplacian matrix

8 pages, 3 figures, 8 references. A typo has been fixed in the example. An advanced version follows

Cited by in corpus (5)

• Tree formulas, mean first passage times and Kemeny's constant of a Markov chain
• Hitting Time Quasi-metric and Its Forest Representation
• On resistance distance of Markov chain and its sum rules
• Exact and Approximate Mean First Passage Times on Trees and other Necklace Structures: a Local Equilibrium Approach
• On the Poisson equation for nonreversible Markov jump processes