The Coupon Collector Problem

Expected time to collect all n distinct coupons is nHₙ, derived by summing expected waiting times across phases.

1. The idea

Suppose there are $n$ distinct coupon types, and each draw is uniformly one of the $n$ types (with replacement). The coupon collector problem asks for the expected number of draws needed to see every type at least once.

Split the process into $n$ phases based on how many distinct types have been collected so far. In phase $i$ (having $i - 1$ distinct types already), each draw is a 'new type' with probability $\frac{n - i + 1}{n}$ , so the number of draws in that phase is geometric with that success probability.

Summing the expected phase lengths gives $n H_{n}$ where $H_{n} = 1 + \frac{1}{2} + \dots + \frac{1}{n}$ is the $n$ -th harmonic number, which grows like $n ln n$ .

2. Why it matters

The coupon collector recursion is a template for any 'collect all distinct outcomes' question, and its $n ln n$ growth rate is a useful benchmark intuition for hashing and sampling problems.

3. Core mathematics

Phase i waiting time

E [T_{i}] = \frac{n}{n - i + 1}

Geometric with success prob (n-i+1)/n.

Total expected time

E [T] = i = 1 \sum n \frac{n}{n - i + 1} = n j = 1 \sum n \frac{1}{j} = n H_{n}

Harmonic number growth

H_{n} \approx ln n + γ

4. How to recognize it

Think of this when…

Draws are uniform with replacement from n distinct categories
The goal is to see every category at least once
The problem splits naturally into phases based on distinct types collected so far

5. Worked example

Worked example

A cereal box has one of $n = 4$ toy types, chosen uniformly at random and independently each time you buy a box. Find the expected number of boxes needed to collect all 4 toys.

1
Phase $i$ starts after collecting $i - 1$ distinct toys; the success probability of drawing a new one is $(4 - i + 1) /4$ .
$E [T_{i}] = \frac{4}{4 - i + 1}$
2
Compute each phase: $E [T_{1}] = 4/4 = 1$ , $E [T_{2}] = 4/3$ , $E [T_{3}] = 4/2 = 2$ , $E [T_{4}] = 4/1 = 4$ .
$E [T] = 1 + \frac{4}{3} + 2 + 4$
3
Sum the phases.
$E [T] = 1 + 1.333 + 2 + 4 = \frac{25}{3} \approx 8.33$
Answer: $E [T] = 4 H_{4} = 25/3 \approx 8.33$ boxes

6. Common mistakes

Forgetting that later phases have smaller success probability and thus dominate the total expected time
Mixing up $n / i$ with $n / (n - i + 1)$ when indexing phases
Applying linearity to the phases without recognizing each phase is itself a geometric random variable
Approximating $H_{n}$ as $ln n$ for small $n$ where the approximation is inaccurate

7. Quick check

For n = 2 coupon types, what is the expected number of draws to collect both?

8. Practice

5 QuantSolve questions use this concept.

Practice this concept

9. Related methods

Recursive Expectation / First-Step Analysis Linearity of Expectation

Create a free account to save lesson progress.