The Coupon-Collector Problem

Cereal boxes each contain one of $n$ equally likely collectible toys, chosen independently at random each time. How many boxes, on average, do you need to buy before you have all $n$ toys? The intuition "about $n$ boxes" is badly wrong — the real answer grows noticeably faster, and the reason why is the useful part.

Setting it up with linearity of expectation

Break the collection into stages. Say you're in "stage $i$" for as long as you have exactly $i-1$ distinct toys and are waiting for a new one (a toy you don't already have). Stage 1 runs from the start until your first toy. Stage $n$ is the wait for the very last missing toy.

Each stage is a geometric wait. In stage $i$, you already have $i-1$ of the $n$ toys, so each new box is a "success" (a toy you don't have) with probability $\dfrac{n-i+1}{n}$. The expected number of boxes to wait for one success, when each trial succeeds with probability $q$, is $1/q$. So the expected length of stage $i$ is $\dfrac{n}{n-i+1}$.

Add up the stages. Total expected boxes $= \sum_{i=1}^{n} \dfrac{n}{n-i+1} = n\left(\dfrac{1}{n} + \dfrac{1}{n-1} + \cdots + \dfrac{1}{1}\right) = n \cdot H_n$, where $H_n$ is the $n$-th harmonic number.

Worked example

With $n=50$ distinct toys, how many boxes do you expect to need to complete the set?

$H_{50} \approx \ln 50 + 0.577 \approx 3.912 + 0.577 = 4.489$. Expected boxes $\approx 50 \times 4.489 \approx 224$. Completing a set of 50 needs roughly 224 boxes on average — more than four times the naive guess of 50 — because the last few missing toys are each individually rare events once most of the set is already collected.

The same tail-dominated shape shows up whenever a strategy needs to "see everything at least once" — testing every code path, sampling every rare regime in a backtest, or a market maker needing every symbol in a universe to trade at least once before a model is fully calibrated. The last few cases are always disproportionately expensive.