In this video, I'll talk about how to calculate the mean first passage time for an ergodic
Markov chain.
For an ergodic chain, the mean first passage time from state i to state j is the expected
number of transitions before we first reach state j, given that we are currently in state
i.
It is denoted by mij.
We can use the following recursive method to calculate the mean first passage time.
Assume that we are currently in state i.
We can reach state j via two ways.
The first way is to go directly from state i to state j in one transition.
The probability is pij.
Alternatively, we can also go to a state k, which is not state j.
The probability is pik.
Then from there we calculate the expected number of transitions from state k to state
j, which is denoted by mkj.
It will take an average of 1 + mkj transitions to go from i to j.
Therefore, the mean first passage time from i to j is equal to 1 transition times the
probability, plus the sum of 1+mkj transitions times the corresponding probabilities.
It can be simplified to this form.
The mean first passage time from i to itself is equal to 1 over πi, where πi is the steady-state
probability of state i.
Let's revisit the toothpaste brand example we examined in a previous video.
This is an ergodic Markov chain.
This is the corresponding transition matrix.
And the steady-state probabilities are 2/3 and 1/3 for state 1 and state 2, respectively.
Let's use the formula to calculate the mean first passage time from state 1 to itself.
m11 is equal to 1 over π1.
It is equal to 1.5.
It means, if we are currently in state 1, it will take on average 1.5 transitions to
first come back to state 1.
Similarly, m22 is equal to 3.
It means, if we are currently in state 2, it will take on average 3 transitions to first
come back to state 2.
m12 is equal to 10.
If we are currently in state 1, it will take on average 10 transitions to first reach state
2.
It means, a person who last purchased brand 1 toothpaste will purchase brand 1 ten times
on average before switching to brand 2.
m21 is equal to 5.
If we are currently in state 2, it will take on average 5 transitions to first reach state
1.
It means, a person who last purchased brand 2 toothpaste will purchase brand 2 five times
on average before switching to brand 1.
Let's push it further and take a look at this extreme case.
This is no longer an ergodic Markov chain because each state is periodic with a period
of 2.
But these formulas still work.
This is the corresponding transition matrix.
And the steady-state probabilities are 1/2 for both state 1 and state 2.
Let's use the formula to calculate the mean first passage time from state 1 to itself.
m11 is equal to 1 over π1.
It is equal to 2.
It means, if we are currently in state 1, it will take on average 2 transitions to first
come back to state 1.
Similarly, m22 is equal to 2.
It means, if we are currently in state 2, it will take on average 2 transitions to first
come back to state 2.
m12 is equal to 1.
If we are currently in state 1, it will take on average 1 transition to first reach state
2.
m21 is equal to 1.
If we are currently in state 2, it will take on average 1 transition to first reach state
1.
That is how to calculate the mean first passage time.
Thanks for watching.