Seyed Masoud Hosseini · Overview · Study log · Weekly summaries · Ideas · Search · Transcript · RSS feed

Probability · Lecture 61 of 76 · 9:27

Mean First Passage and Recurrence Times

Study guide

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

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

Vocabulary

first passage time (phrase): The number of steps it takes a process to reach a target state for the first time.
The first passage time from state 2 to state 1 is what we compute.
recurrence time (phrase): The number of steps it takes a process to return to the state it started in.
Recurrence time measures how long it takes to come back to state 1.
first-step recursion (phrase): A method that writes an expected value in terms of what happens after one step.
The first-step recursion gives an equation for the expected time.
boundary condition (phrase): A known starting value used to solve a set of equations.
The boundary condition here is that t1 equals 0.
algebra (noun): The branch of math dealing with symbols and equations.
Simple algebra solves the equation for t2.
sample path (phrase): One specific sequence of states a random process actually follows.
The sample path shows the chain reaching state 1 at time 3.
Markov chain (phrase): A random process that moves between states, where the next state depends only on the current one.
The two-state student model is a simple Markov chain.
transition probability (phrase): The chance of moving from one state to another in a single step.
The transition probabilities are 0.2, 0.8, 0.6, and 0.4.
recursive equation (phrase): An equation that defines a value in terms of itself at a later or earlier step.
The recursive equation links t2 to t1 and t2 itself.
weighted sum (phrase): A total where each part is multiplied by its own importance before adding.
The recursion is a weighted sum over the possible next states.
target state (phrase): The specific state a process is trying to reach.
State 1 is the target state in the first passage calculation.
Markov property (phrase): The rule that the future of a process depends only on its current state, not its past.
The recursion relies on the Markov property being true.
plug in (phrasal verb): To substitute a known value into a formula or equation.
We plug in the known transition probabilities to solve for t2.
drop out (phrasal verb): To disappear from an equation because its value is zero.
The t1 term drops out since t1 = 0.
expected value (phrase): The long-run average result of a random quantity.
t2 is the expected value of the number of steps to reach state 1.
algebraically (adverb): Using algebra, working with symbols and equations rather than numbers alone.
The equation is solved algebraically for a single unknown.
linear equation (phrase): An equation where the unknown appears only to the first power, with no multiplication between unknowns.
The recursion reduces to one linear equation in one unknown.
illustrate (verb): To make an idea clear using an example.
A sample path illustrates how the chain reaches state 1.
one-step (adjective): Involving only a single move from one state to the next.
The recursion is built from one-step transition probabilities.
notation (noun): A system of symbols used to write mathematical ideas.
Be comfortable with Markov chain notation before watching.
wrap up (phrasal verb): To finish something by summarizing the main points.
The lecture wraps up by summarizing the general recursion pattern.
pattern (noun): A repeated or general way something works.
The general pattern is one step plus the expected remaining time.
unknown (noun): A value in an equation that has not yet been found.
The equation reduces to one unknown, t2.
reach (verb): To arrive at or get to a particular state or point.
We compute how long it takes the chain to reach state 1.
return (verb): To come back to a place or state after leaving it.
Recurrence time measures how long it takes to return to state 1.

From the YouTube description

MIT 6.041SC Probabilistic Systems Analysis and Applied Probability, Fall 2013
View the complete course: http://ocw.mit.edu/6-041SCF13
Instructor: Kuang Xu

License: Creative Commons BY-NC-SA
More information at http://ocw.mit.edu/terms
More courses at http://ocw.mit.edu

← Lecture 18: Markov Chains III · Lecture 19: Weak Law of Large Numbers →