Expected Value & Linearity
Conditional Expectation & Tower Property
Overview
Conditional expectation turns hard sequential problems into simple algebra. The key is the first-step decomposition: instead of thinking about the whole path, you ask 'what can happen in the very next step, and what is my expected position after that?' This converts an infinite-horizon problem into a finite system of equations. The tower property E[X] = E[E[X|Y]] is a theorem that formalizes this decomposition.
How to Recognize
- →Problem has natural stages or phases — condition on 'what happens first'
- →Expected duration/steps to reach a state
- →Can condition on the first step or first outcome
- →Problem looks like a random walk or sequential process
Step-by-Step Approach
- 1.Step 1: Identify the relevant states (what information determines the future?)
- 2.Step 2: Condition on what happens in the FIRST step
- 3.Step 3: E[X] = E[E[X|first step]] — law of total expectation
- 4.Step 4: Set up equations: E[X|state i] = 1 + Σⱼ P(go to j|in state i)·E[X|state j]
- 5.Step 5: Solve the system of linear equations
Key Formulas
Worked Examples
Problem
Flip a fair coin repeatedly. What is the expected number of flips until you've seen at least one head AND at least one tail?
Solution
States: Start (neither H nor T seen yet — but the first flip gives one of them).
After first flip: you've seen exactly one of {H, T}. Need the other.
From state 'need the other outcome': each flip has P(1/2) of giving what you need.
Expected additional flips from 'need other' state = geometric with p=1/2 → E = 2 additional flips.
Total expected flips = 1 (first flip) + 2 (expected flips to get the other) = 3? Let's verify.
Wait: first flip always gives you ONE type. Then you need the other, which takes Geometric(1/2) = 2 flips on average. Total = 1 + 2 = 3.
Answer
flips. After the first flip (cost 1), you need Geometric(1/2) = 2 more flips to see the other outcome.
Common Mistakes
- !
Setting up the recursion but forgetting the '+1' term for the current step cost.
- !
Not properly handling boundary conditions in the recursion (absorbing states have tᵢ = 0).
- !
Using E[E[X|Y]] = E[X] but forgetting the conditions when Y affects the range of X.
Practice Problems
Click "Show Answer" to revealExpected number of fair coin flips to see 3 consecutive heads (HHH)?
A frog is on lily pad 1. Each jump, it goes to any other pad (2–5) with equal probability. Pad 6 is the exit. What is the expected number of jumps to reach pad 6, if from pad 6 it has arrived?