Expected Payoff of a Capped Coin-Flip Game
Samuel flips a fair coin repeatedly until he gets tails. Let $n$ be the total number of flips (including the final tails). His payoff is $\min(64, 2^n)$ dollars.
What is Samuel's expected payoff?
Hints
- The payoff $2^n$ grows at the same rate as the probability $(1/2)^n$ shrinks. What does that mean for each term in the expectation?
- Split the sum at the point where the cap $64 = 2^6$ kicks in. For $n \leq 6$, each term in the expectation simplifies to exactly 1.
- For $n \geq 7$, the payoff is constant at 64. Sum the geometric tail $\sum_{i=7}^{\infty} (1/2)^i = 1/64$ and multiply by 64.
Worked Solution
How to Think About It: The payoff doubles with each flip ($2, 4, 8, \ldots$) but is capped at $64 = 2^6$. So for the first 6 flips, the payoff grows exponentially, and after that it is flat at 64. The key structural observation: for flips $n = 1$ through $6$, each outcome contributes exactly the same amount to the expected value, because the probability $(1/2)^n$ exactly cancels the payoff $2^n$. Once the cap kicks in, you are just collecting $64$ times a small tail probability. This is a truncated version of the St. Petersburg paradox -- the cap is what makes the expectation finite and manageable.
Quick Estimate: Each of the first 6 flips contributes $(1/2)^n \times 2^n = 1$ dollar. That gives 6 dollars. The probability of reaching flip 7 or beyond is $(1/2)^6 = 1/64$, and the payoff is capped at 64, so that tail contributes $64 \times (1/64) = 1$ dollar. Quick answer: $6 + 1 = 7$. Done.
Approach: Split the expectation at the cap boundary $n = 6$ and sum separately.
Formal Solution:
The number of flips $n$ follows a geometric distribution: $P(n = i) = (1/2)^i$ for $i = 1, 2, 3, \ldots$
The expected payoff is:
$$E[\text{Payoff}] = \sum_{i=1}^{\infty} P(n = i) \cdot \min(64, 2^i)$$
Split at $i = 6$, since $2^i \leq 64$ for $i \leq 6$ and $2^i > 64$ for $i \geq 7$:
$$E[\text{Payoff}] = \underbrace{\sum_{i=1}^{6} \frac{1}{2^i} \cdot 2^i}_{\text{uncapped region}} + \underbrace{\sum_{i=7}^{\infty} \frac{1}{2^i} \cdot 64}_{\text{capped region}}$$
The first sum:
$$\sum_{i=1}^{6} \frac{2^i}{2^i} = \sum_{i=1}^{6} 1 = 6$$
The second sum:
$$64 \sum_{i=7}^{\infty} \frac{1}{2^i} = 64 \cdot \frac{1/2^7}{1 - 1/2} = 64 \cdot \frac{1}{64} = 1$$
Answer: The expected payoff is $\boxed{7}$ dollars.
Intuition
This problem is a finite version of the St. Petersburg paradox. In the original paradox, the payoff is $2^n$ with no cap, so every outcome contributes exactly 1 dollar to the expectation and the sum diverges to infinity -- a "fair" game that no rational person would pay a large amount to play. The cap at 64 truncates the paradox: you get 6 dollars from the uncapped terms (one per flip) plus 1 dollar from the entire capped tail. The reason every uncapped term contributes exactly 1 is the perfect cancellation between the exponentially growing payoff and the exponentially shrinking probability -- a hallmark of geometric-payoff games.
In practice, this structure shows up whenever you price a capped payout on a multiplicative process. The uncapped portion gives you a clean closed form (often just counting terms), while the tail is just the cap times the survival probability. Recognizing this split immediately -- rather than grinding through the full infinite sum -- is the kind of shortcut that saves time in an interview.