Mean First Passage and Recurrence Times

What this lecture covers

This is a worked problem on Markov chains: given a two-state chain modeling a student who is either "up to date" or "fallen behind," how long on average does it take to first reach one state from another? The lecture answers this using a recursive equation built from the one-step transition probabilities.

It sits within the probability course's unit on Markov chains, following the setup of states and transition probabilities. After watching, you should be able to write the first-step recursion for expected first passage time and expected recurrence time in a simple Markov chain and solve it algebraically.

Key ideas

• First passage time: for a chain starting in state j, the (random) number of steps until it first reaches a target state.
• Recurrence time: for a chain starting in the target state itself, the number of steps until it returns to that state, not counting the starting step.
• First-step recursion: the expected first passage time from state j equals 1 (for the next step) plus the weighted sum, over all next states, of the transition probability times the expected first passage time from that next state.
• Boundary condition: the expected first passage time from the target state to itself is 0, since you're already there.
• Markov property: the recursion works because, after one step, the future only depends on the current state, not on how you got there.
• Solving the recursion: because the equation is linear in the unknown expected times, plugging in known transition probabilities reduces it to one equation in one unknown, solvable by algebra.

Walkthrough

Setting up the Markov chain and first passage time (0:02)

The lecture introduces a two-state chain with states 1 ("up to date") and 2 ("fallen behind"), with transition probabilities 0.2, 0.8, 0.6, and 0.4 between and within the states. It defines t_j as the expected first passage time to state 1, starting from state j, illustrated with a sample path where the chain starts in state 2 and first reaches state 1 at time 3.

Deriving the recursion for t2 (2:14)

The lecture sets up the recursive equation t2 = 1 + P21*t1 + P22*t2, explaining that after one step the chain lands in some state j, and from there it takes the expected time t_j to reach state 1. Since t1 = 0 by definition, the equation simplifies to t2 = 1 + 0.4*t2, which solves to t2 = 5/3.

Recurrence time back to state 1 (4:16)

The second part defines t1* as the expected recurrence time: starting in state 1, the expected number of steps to return to state 1 (not counting time 0). The same first-step recursion applies, giving t1* = 1 + P11*t1 + P12*t2, where t1 = 0 again drops out, leaving t1* = 1 + 0.2*(5/3) = 4/3.

Wrap-up on the recursion technique (8:26)

The lecture closes by summarizing the general pattern: any such expected time can be written as one step plus the expected remaining time from wherever that step lands, and this only works because the chain's future depends solely on its current state.

Before you watch

• Be comfortable with Markov chain notation: states, transition probabilities, and the Markov (memoryless) property.
• Review how to set up and solve simple linear equations for unknown expected values.

Check your understanding

1. Why is t1 = 0 in the recursion for expected first passage time to state 1?
2. How does the recursion for recurrence time differ from the recursion for first passage time, and why is that difference necessary?
3. Given transition probabilities P21 and P22, how would you set up the recursion to compute the expected first passage time from state 2?
4. Why does the first-step recursion rely on the Markov property to be valid?