Mathwords logoMathwords

Coupon Collector's Problem — Definition, Formula & Example

The Coupon Collector's Problem asks how many random draws you need, on average, to collect at least one of every type when each draw is equally likely to be any of nn types. The answer grows like nln⁡nn \ln n, because the last few missing types are hard to find.

Let draws be independent and uniformly distributed over nn types, and let TT be the number of draws until every type has appeared at least once. Then T=∑i=1nTiT = \sum_{i=1}^{n} T_i, where TiT_i is the number of draws taken to get the iith new type once i−1i-1 types are already collected. Each TiT_i is geometric with success probability pi=n−i+1np_i = \frac{n-i+1}{n}, so E[T]=nHnE[T] = n H_n, where HnH_n is the nnth harmonic number.

Key Formula

E[T]=n∑k=1n1k=nHn≈nln⁡n+γn+12E[T] = n\sum_{k=1}^{n}\frac{1}{k} = nH_n \approx n\ln n + \gamma n + \tfrac{1}{2}
Where:
  • TT = Number of draws needed to collect all n types
  • nn = Number of equally likely types (coupons)
  • HnH_n = The nth harmonic number, 1 + 1/2 + ... + 1/n
  • γ\gamma = Euler–Mascheroni constant, about 0.5772

How It Works

Split the collecting process into stages. Suppose you already have i−1i-1 distinct types. Each new draw then gives an unseen type with probability n−i+1n\frac{n-i+1}{n}, so the expected wait for that stage is nn−i+1\frac{n}{n-i+1}. Linearity of expectation lets you add the stage expectations even though the stages have different lengths. The early stages finish almost instantly. The final stage alone takes nn draws on average.

Worked Example

Problem: You roll a fair six-sided die repeatedly. On average, how many rolls does it take to see all six faces at least once?
Step 1: Treat each new face as a stage. After you have seen ii distinct faces, a roll shows a new face with probability 6−i6\frac{6-i}{6}. The expected wait for that stage is the reciprocal of this probability.
66, 65, 64, 63, 62, 61\frac{6}{6},\ \frac{6}{5},\ \frac{6}{4},\ \frac{6}{3},\ \frac{6}{2},\ \frac{6}{1}
Step 2: Add the stage expectations. This sum is 6H66H_6, and H6=4920H_6 = \frac{49}{20}.
1+1.2+1.5+2+3+6=6⋅4920=14.71 + 1.2 + 1.5 + 2 + 3 + 6 = 6\cdot\frac{49}{20} = 14.7
Step 3: Compare with the approximation nln⁡n+γn+12n\ln n + \gamma n + \frac{1}{2}. It is already very close for n=6n = 6.
6ln⁡6+0.5772(6)+0.5≈14.716\ln 6 + 0.5772(6) + 0.5 \approx 14.71
Answer: It takes 14.7 rolls on average to see all six faces. The last new face alone accounts for 6 of those rolls.

Why It Matters

In computer science courses, the same sum bounds how many random hash probes or random test inputs you need to hit every bucket or case. It also predicts how many packs you must buy to complete a set of trading cards, and it explains why the final few cards cost so much.

Common Mistakes

Mistake: Assuming you need about nn draws to collect nn types, or treating every stage as equally hard.
Correction: Repeats become more likely as your collection grows. With one type left, the expected wait alone is nn draws, so the total is nHnnH_n. For a die that total is 14.7, not 6.

Related Terms