Recursive Expectation (First-Step Analysis)

Set up an equation for E[X] by conditioning on the first step of a random process, then solve algebraically.

1. The idea

First-step analysis conditions on the outcome of the very first random step and expresses the target expectation in terms of itself. If the process 'restarts' after a failed step, the resulting equation for $E [X]$ is often linear and directly solvable.

This works because many processes (waiting for an event, gambler's ruin, repeated games) are memoryless in structure: after any unsuccessful step, the future looks exactly like the original problem, just with an extra step already used.

The technique generalizes cleanly to accumulating rewards along the way, not just counting the number of steps.

2. Why it matters

First-step analysis is the standard tool for expected number of trials, expected rewards accumulated before an event, and gambler's-ruin-style recursions — a recurring interview category.

3. Core mathematics

Self-referential setup

E [X] = 1 + p \cdot 0 + (1 - p) E [X]

Example: geometric waiting time, solved for E[X].

General recursion

E [X] = first outcome i \sum P (i) (cost (i) + E [X ∣ restart or continue after i])

4. How to recognize it

Think of this when…

A process repeats until some event occurs (a specific roll, a win, an arrival)
After a 'failure', the situation is identical to the start
You are asked for expected number of steps, rolls, or flips, or an accumulated reward along the way

5. Worked example

Worked example

A fair die is rolled repeatedly until a 6 appears. Each non-6 roll adds its value (1 through 5) to a running total, and rolling a 6 ends the process without adding to the total. Find the expected final total.

1
Let $T$ be the expected total. Condition on the first roll: with probability $1/6$ it's a 6 and the process stops with nothing added; with probability $5/6$ it's uniform on ${1, \dots, 5}$ , adding that value and restarting.
$T = \frac{1}{6} (0) + k = 1 \sum 5 \frac{1}{6} (k + T)$
2
Simplify the sum: $\sum_{k = 1}^{5} k = 15$ , and there are 5 such terms each contributing $T$ .
$T = \frac{1}{6} (15) + \frac{5}{6} T$
3
Solve for $T$ .
$T - \frac{5}{6} T = \frac{15}{6} ⟹ \frac{1}{6} T = \frac{15}{6} ⟹ T = 15$
Answer: $T = 15$ — matches expected number of non-6 rolls (5) times the average added value (3)

6. Common mistakes

Forgetting to add the reward/cost of the current step before recursing
Setting up the recursion with the wrong restart probability
Not simplifying the self-referential equation correctly before solving for $E [X]$
Ignoring absorbing states (like rolling the target number) and letting the recursion continue indefinitely

7. Quick check

A coin with $P (heads) = p$ is flipped until heads appears. What is the expected number of flips?

8. Practice

3 QuantSolve questions use this concept.

Practice this concept

9. Related methods

Recursive Expectation / First-Step Analysis Conditional Expectation

Create a free account to save lesson progress.