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 types. The answer grows like , because the last few missing types are hard to find.
Let draws be independent and uniformly distributed over types, and let be the number of draws until every type has appeared at least once. Then , where is the number of draws taken to get the th new type once types are already collected. Each is geometric with success probability , so , where is the th harmonic number.
Key Formula
Where:
- = Number of draws needed to collect all n types
- = Number of equally likely types (coupons)
- = The nth harmonic number, 1 + 1/2 + ... + 1/n
- = Euler–Mascheroni constant, about 0.5772
How It Works
Split the collecting process into stages. Suppose you already have distinct types. Each new draw then gives an unseen type with probability , so the expected wait for that stage is . 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 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 distinct faces, a roll shows a new face with probability . The expected wait for that stage is the reciprocal of this probability.
Step 2: Add the stage expectations. This sum is , and .
Step 3: Compare with the approximation . It is already very close for .
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 draws to collect 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 draws, so the total is . For a die that total is 14.7, not 6.
