First-Step Analysis

Medium4–5 hrsMarkov ChainsExpected ValueRecurrenceConditional Expectation

Overview

First-step analysis (also called first-passage analysis) is the standard technique for computing expected times in Markov chains. The idea: condition on what happens in the FIRST step, then use the fact that after the first step, you're in a new state with a known expected time. This creates a system of linear equations. The key steps are: (1) list the minimal set of states needed to describe the problem, (2) write the recurrence, (3) solve. The most common error is missing a state or getting transition probabilities wrong.

How to Recognize

→'How many flips until you see HH (or some pattern)?'
→'Expected number of dice rolls until sum exceeds N'
→'Expected rounds in a game that repeats with some probability'
→State-based problems where each step looks identical to the original
→Game restarts or partially resets based on outcomes

Step-by-Step Approach

1.Identify ALL distinct states the system can be in
2.Let Eᵢ = expected steps/value from state i
3.Write Eᵢ = (1 + weighted sum of Eⱼ for all j you can go to from i)
4.Set up the system of equations — usually 2–4 unknowns
5.Solve the linear system; verify by plugging back in

Key Formulas

E_i = c_i + \sum_j P(i \to j)\, E_j \quad

(first-step equation for state

i

)

E[\text{HH}] = 6, \quad E[\text{HTH}] = 10, \quad E[\text{HT}] = 4

E[\text{rolls to get all faces}] = 6\left(\frac{1}{6}+\frac{1}{5}+\frac{1}{4}+\frac{1}{3}+\frac{1}{2}+\frac{1}{1}\right) = 6H_6 = 14.7

Worked Examples

0Quick Example

Expected flips to see HH: States = {start, H, HH(done)}. E_start = 1 + ½E_H + ½E_start → E_start = 2 + E_H. E_H = 1 + ½·0 + ½E_start. Solve: E_start = 6.

Problem

A fair coin is flipped repeatedly. What is the expected number of flips until you see two consecutive heads?

Solution

States: S₀ = start (or just saw T), S₁ = just saw H, DONE = saw HH.

From S₀: flip H (prob ½) → go to S₁; flip T (prob ½) → stay in S₀.

From S₁: flip H (prob ½) → DONE; flip T (prob ½) → go to S₀.

Equations: E₀ = 1 + ½E₁ + ½E₀ → ½E₀ = 1 + ½E₁ → E₀ = 2 + E₁.

E₁ = 1 + ½·0 + ½E₀ = 1 + ½E₀.

Substitute: E₀ = 2 + 1 + ½E₀ → ½E₀ = 3 → E₀ = 6.

Answer

$E[\text{flips to see HH}] = 6$ . Verify: if E₀=6, then E₁ = 1 + 3 = 4. Makes sense: if you just saw H, you're 4 flips away on average.

Common Mistakes

!
Not identifying all states. For HH you need 3 states (not 2) because 'just saw H' and 'just saw T/start' behave differently.
!
Getting transition probabilities wrong when a failed pattern restarts you in a non-zero state. E.g., for HHH: after seeing HH and then getting T, you go to 'just saw T', not 'start with HH done'.
!
Forgetting to add the +1 (cost of the current step) on the right side of the equation.
!
Solving for the wrong state — always solve for the starting state E₀, not an intermediate one.

Practice Problems

Click "Show Answer" to reveal

A fair coin is flipped until you see either TT or TH. What is the expected number of flips?

Hint: Note: TT stops the game, and TH stops the game. Any T leads to a state where the next flip ends it. What about H first?

Two players alternate rolling a fair die. Player 1 wins if they roll a 6; Player 2 wins if they roll a 6. Player 1 goes first. What is P(Player 1 wins)?

Hint: Let p = P(Player 1 wins from the start). After P1 misses, it's P2's turn — by symmetry, from here P2 wins with probability p. So P1 wins = ?

A drunk person starts at position 0 and each step moves +1 or -1 with equal probability. What is the expected number of steps to reach ±N?

Hint: Let Eₓ = expected steps from position x (with |x| < N). By symmetry around 0, write recurrence for Eₓ in terms of Eₓ₋₁ and Eₓ₊₁.

Back to Study Plan

Martingales & Optional Stopping Gambler's Ruin