A graph theoretic interpretation of the mean first passage times

Details A graph theoretic interpretation of the mean first passage times A graph theoretic interpretation of the mean first passage times

2007-01-12

arxiv.org/abs/math/0701359v2

Mathematics

Probability

7 pages, 5 references

Scientific paper

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}^nq_k$. The result is illustrated by an example. Keywords: Markov chain; Mean first passage time; Spanning rooted forest; Matrix forest theorem; Laplacian matrix

Affiliated with

Also associated with

No associations

Rating

A graph theoretic interpretation of the mean first passage times does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A graph theoretic interpretation of the mean first passage times, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A graph theoretic interpretation of the mean first passage times will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-218538