Recursive Expectation / First-Step Analysis

Condition on the first move and write equations linking the states.

What is it?

Define the expected remaining time (or win probability) from each state, then express each one through the states reachable in one step.

Waiting for patterns, random walks and gambler's ruin all reduce to a small linear system.

Think of it when a process restarts or moves between a few states until it stops.

Think of this method when…

From any state, one step costs 1 and moves to another state; expectations satisfy $e_{s} = 1 + \sum_{t} p_{s t} e_{t}$ .

e_{s} = 1 + t \sum p_{s t} e_{t}, e_{absorbing} = 0

What is the expected number of fair coin flips until two heads in a row?

1
States: $e_{0}$ (no progress) and $e_{1}$ (last flip was H).
2
Equations: $e_{0} = 1 + \frac{1}{2} e_{1} + \frac{1}{2} e_{0}$ and $e_{1} = 1 + \frac{1}{2} \cdot 0 + \frac{1}{2} e_{0}$ .
3
From the first, $e_{0} = 2 + e_{1}$ ; substitute into the second.
$e_{0} = 3 + \frac{1}{2} e_{0} \Rightarrow e_{0} = 6$
Answer: $6$

A frog on a line moves left or right with equal probability. Starting at 1, what is the chance it reaches 3 before 0?

20 QuantSolve questions are tagged with this method.