Coupon Collector's Problem
Coupons in cereal boxes are numbered 1 through 5, and each box contains exactly one coupon drawn uniformly at random (with replacement). You need to collect one of each coupon to win a prize.
On average, how many boxes do you need to buy to complete the full set?
Hints
- Think about breaking the collection process into phases based on how many distinct coupons you already have.
- In each phase, getting a new coupon is a geometric waiting time. What is the success probability when you already have $k$ out of 5?
- The expected waiting time in each phase is $5/(5-k)$. Sum these expectations using linearity of expectation to get the total.
Worked Solution
How to Think About It: This is the classic coupon collector setup. The key insight is to decompose the collection process into phases. Phase 1 starts when you have 0 distinct coupons and ends when you get your first -- that takes exactly 1 box. Phase 2 starts when you have 1 distinct coupon and ends when you get a new one -- each box has a $4/5$ chance of being new, so you are waiting for the first success of a geometric with $p = 4/5$. And so on. Each phase is an independent geometric waiting time, so the total expected boxes is just the sum of the phase expectations.
Quick Estimate: With $n = 5$ coupons, the hardest part is the last coupon. You already have 4, so each box has only a $1/5$ chance of being the missing one -- that phase alone costs $5$ boxes in expectation. The second-hardest phase costs $5/2 = 2.5$, the third costs $5/3 \approx 1.67$, then $5/4 = 1.25$, and the first coupon costs $1$. Adding up: $1 + 1.25 + 1.67 + 2.5 + 5 = 11.42$. So roughly 11-12 boxes. For a quick sanity check: the well-known asymptotic formula for $n$ coupons gives $n \ln n + \gamma n \approx 5 \times 1.609 + 0.577 \times 5 \approx 10.93$, which is in the right ballpark (the exact harmonic sum is a bit higher).
Approach: Decompose the collection process into geometric waiting times and sum their expectations.
Formal Solution:
Define $T$ as the total number of boxes needed. Break $T$ into phases $T = T_1 + T_2 + \cdots + T_5$, where $T_i$ is the number of boxes bought during the phase where you go from $i-1$ distinct coupons to $i$ distinct coupons.
When you have $i-1$ distinct coupons, the probability that a new box contains a coupon you do not yet have is:
$$p_i = \frac{5 - (i-1)}{5} = \frac{6-i}{5}$$
Each $T_i$ is geometrically distributed with success probability $p_i$, so $E[T_i] = 1/p_i = 5/(6-i)$.
Summing over all phases:
$$E[T] = \sum_{i=1}^{5} \frac{5}{6-i} = \frac{5}{5} + \frac{5}{4} + \frac{5}{3} + \frac{5}{2} + \frac{5}{1}$$
$$= 5\left(1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5}\right) = 5 \cdot H_5$$
where $H_5 = 1 + 1/2 + 1/3 + 1/4 + 1/5 = 137/60$ is the 5th harmonic number.
$$E[T] = 5 \times \frac{137}{60} = \frac{137}{12} \approx 11.42$$
Answer: The expected number of boxes is $5 \cdot H_5 = 137/12 \approx 11.42$. More generally, for $n$ coupon types, the answer is $n \cdot H_n$, where $H_n$ is the $n$th harmonic number.
Intuition
The coupon collector problem is one of the cleanest illustrations of linearity of expectation in action. Instead of trying to track the full joint distribution of which coupons you have after $t$ boxes (a combinatorial nightmare), you decompose the process into independent geometric phases. Each phase has a simple expected duration, and the total is just the sum. The reason the answer grows like $n \ln n$ (for $n$ coupon types) is that the harmonic series $H_n = 1 + 1/2 + \cdots + 1/n \approx \ln n$ shows up naturally -- the last few coupons are disproportionately expensive to collect.
This pattern appears constantly in quant work. Any time you are waiting for a set of independent rare events to all occur (a market maker seeing quotes from every exchange, a monitoring system confirming all sensors are alive, a simulation hitting every corner case), the waiting time scales like $n \ln n$, not $n$. The practical takeaway: the last 20% of coverage takes roughly as long as the first 80%. That log factor is the cost of completeness.