Coupon Collector

Problem. There are $n$ distinct coupon types. Each purchase yields a uniformly random type. How many purchases are needed to collect all $n$?

The answer

$\mathbb{E}[T]=n{H}_n=n{\sum }_{i=1}^n\frac{1}{i}\approx n\ln n+\gamma n+\frac{1}{2},$

with $\gamma \approx 0.5772$ (the Euler-Mascheroni constant).

The derivation — by linearity

Split the process into phases: phase $i$ runs from having $i-1$ distinct coupons to having $i$.

In phase $i$, a purchase is “new” with probability $\frac{n-i+1}{n}$, so the expected length of that phase is $\frac{n}{n-i+1}$ (a geometric random variable). By linearity of expectation:

$\mathbb{E}[T]={\sum }_{i=1}^n\frac{n}{n-i+1}=n{\sum }_{j=1}^n\frac{1}{j}=n{H}_n.■$

double couponCollector(int n) {
    double e = 0;
    for (int i = 1; i <= n; i++) e += 1.0 / i;
    return n * e;
}

$n$	$\mathbb{E}[T]$
6 (a die)	14.7
52 (a deck)	236
100	519
365	2 364
1000	7 486

Concentration

$\mathrm{Pr}[T>n\ln n+cn]\le e^{-c},$

so the collection time is sharply concentrated around $n\ln n$. Being twice the mean is already exponentially unlikely. The variance is $\frac{{\pi }^2}{6}{n}^2-O(n\log n)$, so the standard deviation is $\Theta (n)$ — small relative to the mean $n\ln n$.

Variants

Variant	Expected purchases
Collect all $n$	$n{H}_n$
Collect $m$ of $n$	$n(H_n-H_{n-m})$
Collect $k$ copies of each	$n\ln n+(k-1)n\ln \ln n+O(n)$
Non-uniform probabilities $p_i$	${\int }_0^{\infty }\left(1-{\prod }_i(1-e^{-p_{i}t})\right)dt$ — no simple closed form
Buy in packs of $k$ distinct coupons	roughly $\frac{n}{k}\ln n$
Expected distinct coupons after $t$ purchases	$n\left(1-(1-\frac{1}{n}{)}^t\right)$
Probability all collected by time $t$	inclusion-exclusion: ${\sum }_k(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(1-\frac{k}{n}{)}^t$

The expected distinct after $t$ draws formula is the one that appears most in problems — it is the “balls into bins” occupancy result, and it follows from linearity again (each coupon is missing with probability $(1-1/n{)}^t$).

The contrast with the birthday paradox

Two questions about the same process, with very different answers:

Question	Threshold
When does the first collision occur?	$\approx 1.18\sqrt{n}$ draws (birthday)
When are all values seen?	$\approx n\ln n$ draws (coupon collector)

$\sqrt{n}$ versus $n\ln n$ — the two ends of the same occupancy process, and worth keeping straight. Collisions start almost immediately; completion takes far longer than the naive $n$.

Where it appears in algorithms

Setting	Coupon collector bound
Randomised algorithms needing every element sampled	$O(n\log n)$ rounds
Random walks covering a graph	the cover time — $\Theta (n\log n)$ for a complete graph
Hashing: rounds until every bucket is hit	$n\ln n$
Randomised load balancing	related occupancy bounds
Testing: random inputs to hit every branch	$n\ln n$
Random restarts until every basin is tried	$n\ln n$
Gossip / epidemic protocols	$O(\log n)$ rounds to inform everyone

Cover time is the natural generalisation: the expected time for a random walk to visit every vertex. It is $\Theta (n\log n)$ for the complete graph, $\Theta (n^2)$ for a path or cycle, and $O(n^3)$ for any connected graph (Aleliunas et al.).

The $\ln n$ factor is unavoidable

The $\log$ is not an artefact of the analysis. With $n\cdot c$ draws for a constant $c$, the probability that a specific coupon is still missing is $(1-1/n{)}^{cn}\approx e^{-c}$, so about $n{e}^{-c}$ coupons remain — which only reaches $O(1)$ when $c\approx \ln n$.

Why it is worth knowing

It is the cleanest application of linearity of expectation over phases, and the $n\ln n$ answer is a bound that appears whenever a randomised process must touch every element. Paired with the birthday $\sqrt{n}$, it gives you the two ends of the occupancy spectrum, which covers most probabilistic estimates you will need.

See also: Expected Value Techniques · Birthday Paradox · Probability