The Coupon Collector's Problem: Why the Last Sticker Is Always the Hardest

You are trying to complete a sticker album. The album has $n$ different stickers, and every random pack you buy contains one sticker, chosen uniformly at random from the $n$ possibilities. How many packs, on average, do you need to buy before you have collected at least one of each?

This is the coupon collector’s problem, one of the oldest and most useful problems in probability theory. The answer has a clean closed form, an even cleaner asymptotic form, and a moral that is familiar to anyone who has ever tried to complete a Panini World Cup album: the last few items take far longer than the first few. This article is about that asymmetry, the math behind it, and why the same formula appears in surprising places.

The expected number of draws

Let $T$ be the random number of draws needed to collect all $n$ distinct items. The trick to computing $\mathbb{E}[T]$ is to break the wait into stages. Stage $i$ begins the moment you collect your $i$ -th distinct item, and ends when you collect your $(i+1)$ -th distinct item. Let $T_i$ be the length of stage $i$ , so $T = T_0 + T_1 + T_2 + \dots + T_{n-1}$ .

During stage $i$ , you already have $i$ distinct items, so the probability that any single draw gives you a new one is

$p_i = \frac{n - i}{n}.$

The number of draws until the next new item is a geometric random variable with success probability $p_i$ , whose expected value is $1/p_i$ . So

$\mathbb{E}[T_i] = \frac{n}{n - i}.$

Summing over all $n$ stages:

$\mathbb{E}[T] = \sum_{i=0}^{n-1} \frac{n}{n - i} = n\left(\frac{1}{n} + \frac{1}{n-1} + \cdots + \frac{1}{2} + \frac{1}{1}\right) = n\,H_n,$

where $H_n = 1 + \tfrac{1}{2} + \tfrac{1}{3} + \cdots + \tfrac{1}{n}$ is the $n$ -th harmonic number. The expected number of packs needed to complete the album is exactly $n$ times the $n$ -th harmonic number — a clean and memorable formula.

For large $n$ the harmonic number has the asymptotic expansion $H_n \approx \ln n + \gamma$ , where $\gamma \approx 0.5772$ is the Euler–Mascheroni constant, so

$\mathbb{E}[T] \approx n \ln n + \gamma n.$

Substituting: for a six-sided die ( $n = 6$ ), the expected number of rolls to see every face at least once is $6 \cdot H_6 = 6(1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6) = 14.7$ . For an album of $100$ stickers, you should expect about $518.7$ pack purchases. For an album of $500$ stickers — about the size of a typical World Cup album — the expected number balloons to roughly $3{,}397$ packs.

The slow finish

The most striking feature of the formula is hidden in the sum. Look again at the contribution from each stage:

$\mathbb{E}[T_i] = \frac{n}{n - i}.$

When $i = 0$ (you have nothing yet, every draw is new), this is just $1$ . When $i = 1$ (you have one item), this is $n/(n-1) \approx 1$ . The first few stages each take essentially one draw. But when $i = n - 1$ (you are missing only one item), the expected wait is $n/1 = n$ . The expected wait grows from $1$ to $n$ as the album fills up, and the very last item alone takes, on average, the same number of draws as the first half of the album combined.

For a six-sided die: getting your first new face takes $1$ roll, your second takes $6/5 = 1.2$ rolls on average, the third takes $1.5$ , the fourth $2$ , the fifth $3$ , and the sixth $6$ . The sixth face alone accounts for $6 / 14.7 \approx 41\%$ of the total expected rolls.

This is the mathematical reason it always feels like the last sticker takes forever. It really does take forever, relative to all the previous ones put together. The plot below shows how the expected total $\mathbb{E}[T]$ grows with the number of distinct items $n$ .

The curve climbs in a recognisably $n \log n$ shape. For $n = 100$ stickers the expected total is just under $519$ packs; for $n = 200$ stickers it would be roughly $1{,}176$ . Doubling the number of stickers more than doubles the expected work, by exactly the logarithmic factor.

A second view: indicator variables

There is an even slicker proof. For each item $j = 1, 2, \dots, n$ , let $X_j$ be the number of draws between the moment item $j$ is first drawn and the moment all $n$ items have been collected — counting only draws while item $j$ is the “still-missing” one. By a clever counting, the total number of draws equals $\sum_{i=0}^{n-1} \mathrm{Geom}(p_i)$ exactly as above, and the calculation rolls through identically.

Both perspectives illuminate why $n \ln n$ is the right scaling. The harmonic sum $H_n$ grows logarithmically because $\sum 1/k$ has the same growth as $\int dx/x = \ln x$ . Multiplying by the factor $n$ — the size of the alphabet from which you are sampling — gives the $n \log n$ rate.

How much do the numbers vary?

The expectation tells you the average, but how much does the actual number of packs vary from one collector to another? The variance of $T$ is

$\mathrm{Var}(T) = n^2 \sum_{k=1}^n \frac{1}{k^2} - n\,H_n \;\approx\; \frac{\pi^2 n^2}{6},$

using the famous Basel-problem identity $\sum 1/k^2 = \pi^2/6$ in the limit. The standard deviation is therefore of order $n \cdot \pi/\sqrt{6} \approx 1.28 n$ — comparable in size to the mean for moderate $n$ , but much smaller than the mean for large $n$ (where the mean is $n \log n$ , dominating the linear standard deviation).

So while individual results spread by about $\pm n$ around the mean, the relative spread shrinks like $1/\log n$ . For $n = 100$ , the mean is around $519$ packs and the standard deviation is about $128$ — you can be reasonably confident that you will spend somewhere between $400$ and $700$ packs.

Why it matters

The coupon collector’s formula is the simplest illustration of a phenomenon — the long tail of completion — that appears throughout applied probability. The same $n \log n$ scaling controls the running time of randomised algorithms with “balls and bins” structure, the convergence time of certain Markov chains, the number of random samples needed to cover all parts of a configuration space in Monte Carlo simulation, and the expected complexity of certain graph traversal algorithms.

In software testing, the coupon collector’s problem models how long random input generation takes to exercise every possible code path; the formula explains why fuzz testing requires far more time than naïve estimates suggest. In biology, the expected time to collect every gene through random mutation has the same shape. In machine learning, the expected number of training samples needed to encounter every class at least once in a multi-class classification problem follows the same law.

The deeper lesson is about the price of completeness. Going from $90\%$ done to $100\%$ done is dramatically harder than going from $0\%$ to $90\%$ — by a logarithmic factor, in a way that the harmonic sum makes precise. The mathematics matches the lived experience of every sticker collector since the practice was invented in the nineteenth century. The last sticker really is the hardest. And by the time you finally find it, you will have spent about as long on it as on the entire first half of the album, exactly as the harmonic numbers predict.

Frequently asked

Where does the name 'coupon collector' come from?

From a 19th-century marketing practice. Companies would include collectible coupons or trade cards inside product packaging — cigarette cards, gum cards, tea cards — and consumers would buy more units of the product trying to complete a set. The mathematical question of how many purchases it takes was first analysed by de Moivre and Laplace in the 18th century, then revisited by many mathematicians since. The name stuck even though the modern version of the problem is more often phrased in terms of dice rolls, Panini football stickers, or memory testing.

Why is the last item so hard to find?

Because once you have collected n−1 of the n distinct items, only 1 of every n random items is new to you — the rest are duplicates. So the expected number of additional draws to get the last item is n. By comparison, when you have collected only n/2 items, half of every draw is new, so the wait per new item is just 2. The wait grows from 1 at the start to n at the end, and the final stretch dominates the total. About half of all your draws will be spent acquiring the final few items.

What is the precise expectation formula?

If there are n distinct items, each appearing independently and uniformly at random in each draw, the expected number of draws to collect all of them is E[T] = n · H_n, where H_n = 1 + 1/2 + 1/3 + ⋯ + 1/n is the n-th harmonic number. For large n this is approximately n·ln(n) + γ·n + 1/2, where γ ≈ 0.5772 is the Euler–Mascheroni constant. The variance is approximately π²n²/6, so the typical fluctuation around E[T] is on the order of n.

Where else does the formula n·ln(n) show up?

Everywhere harmonic numbers appear. The expected depth of a randomly built binary search tree is also Θ(log n), with the constants related to H_n. The running time of quicksort with random pivots is Θ(n·log(n)), again with the proportionality constant being a sum of reciprocals. In algorithm analysis the harmonic-number formula is so common that the resulting Θ(n·log(n)) running time is often considered a natural complexity class on its own. The fact that the coupon collector's expected wait is also n·log(n) is part of this same family of phenomena.

The Coupon Collector's Problem: Why the Last Sticker Is Always the Hardest

The expected number of draws

The slow finish

A second view: indicator variables

How much do the numbers vary?

Why it matters

Frequently asked

Continue reading

The Birthday Paradox: Why 23 People Is All You Need

Hidden Markov Models: Inferring the Unobserved State From the Observed One

The Kelly Criterion: How Much to Bet When You Have an Edge

Keep exploring