🎟️ Coupon Collector Problem

Why collecting the final few coupon types takes surprisingly long.

Number of coupon types: N

N = 10

Number of boxes opened: n

n = 20

Part A — How long to collect all N coupons?

Suppose you have already collected k distinct coupon types.

There are therefore

N − k

coupon types that would count as a new coupon.

Therefore the probability that the next box gives a new coupon is

P(new coupon) = (N − k) / N

Waiting for a success with probability p takes 1 / p trials on average.

Hence the expected waiting time for the next new coupon is

N / (N − k)

Phase-by-phase waiting time

The important observation is that collecting coupons gets slower and slower. The final coupon appears with probability only 1/N on each draw, so the final coupon alone takes N draws on average.

Adding the expected waiting times:

Exact expectation

draws

Large-N approximation

≈ N(ln N + γ)

Part B — How many distinct coupons after n boxes?

Instead of tracking the entire collection process, consider one particular coupon type.

On one draw, the probability of not getting that coupon is

1 − 1/N

Therefore, after n independent draws, the probability of never seeing it is

Hence the probability that this coupon has appeared at least once is

1 − (1 − 1/N)ⁿ

P(not seen)

P(seen)

Expected distinct

Visual intuition

Green boxes represent approximately how many coupon types we expect to have seen.

Let Iᵢ = 1 if coupon type i has been observed, and 0 otherwise.

Dₙ = I₁ + I₂ + ··· + Iₙ

By linearity of expectation,

E[Dₙ] = E[I₁] + E[I₂] + ··· + E[I_N]

Every coupon has the same probability of having appeared, so

Why linearity of expectation is useful: the events “coupon 1 appeared”, “coupon 2 appeared”, etc. do not need to be independent. We can still add their expected indicator values.

Final Answers

Expected draws to collect everything:

E[T] = N H_N = N(1 + 1/2 + ··· + 1/N)

For large N,

E[T] ≈ N(ln N + γ)

Expected number of distinct coupons after n draws:

E[Dₙ] = N[1 − (1 − 1/N)ⁿ]