Coupon Collector's Problem: Why It Takes N ln N Draws to Finish

The problem

Suppose a cereal brand puts one of N different collectible coupons in every box, chosen uniformly at random and independently each time. How many boxes do you expect to buy before you own all N? This is the coupon collector problem, one of the oldest instructive questions in discrete probability, and it shows up in software testing (how many random inputs before every branch fires), genome sequencing coverage, and hash-table load estimates.

The trick is to split the process into N stages. Stage i begins the moment you own exactly i-1 distinct coupons and ends the moment you draw your i-th distinct one. During stage i, a draw is a 'success' (a new coupon) with probability p_i = (N-i+1)/N, since N-i+1 of the N types are still missing.

Why the answer involves a harmonic number

The number of draws inside stage i is a geometric random variable with success probability p_i, so its expectation is 1/p_i = N/(N-i+1). Summing over all N stages and re-indexing k = N-i+1 gives the exact expected total:

E[T] = ∑_(i=1..N) N / (N - i + 1)
     = N · ∑_(k=1..N) 1/k
     = N · H_N,   where H_N = 1 + 1/2 + 1/3 + ... + 1/N

H_N, the N-th harmonic number, has no closed form but grows like ln N + γ (the Euler-Mascheroni constant, ≈ 0.5772). So the expected number of boxes is E[T] ≈ N·ln N + γN + 1/2 - for N=50 that's about 225 boxes to complete a set of 50, roughly 4.5x the number of distinct items.

Variance and the tail

The last coupon dominates the variance: its stage has success probability 1/N, so waiting for it alone takes N draws in expectation and has variance close to N². The overall variance of T is asymptotically π²/6 · N², meaning the standard deviation scales with N itself, not with √N as in most sums of independent terms - a direct result of the last few coupons being disproportionately rare and slow to find.

This is why the completion-time histogram in the demo has a long right tail even though the mean is well predicted by N·H_N: a small but real fraction of runs get unlucky on the very last coupon and take dramatically longer than average.

The double-Dixie-cup and Erdos-Renyi refinements

A related question - how many draws until you own m copies of every coupon (not just one) - is the double Dixie cup problem, solved by Newman and Shepp; its expected value is N ln N + (m-1) N ln ln N + O(N) for fixed m. Erdos and Renyi later sharpened the single-copy result into a concentration statement: T/(N ln N) converges in probability to 1, and the fluctuations around N ln N converge to a Gumbel distribution - the same extreme-value law that governs the maximum of many independent random variables, since completing the set is really a race to find the single slowest-to-appear coupon.

Simulating it

function trial(N) {
  const seen = new Set();
  let draws = 0;
  while (seen.size < N) {
    seen.add(Math.floor(Math.random() * N));
    draws++;
  }
  return draws;
}
// average many trials(N) and compare against N * H_N

The simulation on this page runs exactly this loop thousands of times per second, fills a live grid as each coupon type is first seen, and overlays the running empirical average against both closed-form predictions (N·H_N exactly, and the N·ln N + γN approximation) so you can watch the Monte Carlo estimate converge.

Frequently asked questions

Try it live

Everything above runs in your browser — open Coupon Collector and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.