Average First-Passage Time

Topics: First-Passage Time

---

(theorem)

In a Markov chain, we can calculate the average first-passage time for the state $j$ when starting at $i$, denoted $p_{ij}$, with:

$${\mu }_{ij}=1+\sum _{k\ne j}{p}_{ik}{\mu }_{kj}$$

Explanation

Here, we are basically considering that the only two possibilities for the first transition are two:

1. Reaching $j$
2. Reaching any other $k\ne j$

If we reach $j$ during the first transition, then it only took us 1 step to reach it.

If we first pass through $k\ne j$ before eventually reaching $j$, then we have to take 1 step (to reach $k$) then take ${\mu }_{kj}$ more steps to reach $j$ from $k$.

When taking into consideration the probabilities of reaching through any $k$ and adding up all of them, we obtain the average first-passage time from $i$ to $j$.