Updated 12 September 2026

Coupon collector’s problem

A cereal brand hides one of n distinct prizes in each box. You buy boxes one at a time, each containing an independent uniformly random prize. How many boxes do you need to collect all n prizes?

The expected number is $n H_n$, where $H_n$ is the $n$-th harmonic number:

What to notice

• The tail is long. Most runs cluster near the expected value, but some runs are much longer. The distribution is right-skewed because completing the last few coupons requires many “wasted” draws on already-collected prizes.
• Expected grows faster than n. At n = 10, you need about 29 draws. At n = 50, about 225. The asymptotic rate is $n \ln n$ — not linear, and not quite quadratic.
• The last coupon is the killer. When you have n−1 of n coupons, each draw has only a 1/n chance of being the missing one, so you wait n more draws on average for just the final piece.

The math

When you have already collected k distinct coupons, the probability of the next box giving a new one is (n−k)/n. The waiting time until the next new coupon is geometric with success probability (n−k)/n, and has expected value n/(n−k). Summing over k from 0 to n−1:

Expected duration is not a deadline

The draw-budget control calculates P(T≤m), the chance of completion by a chosen number of boxes. An expected duration of about 29.29 for n=10 does not mean completion is guaranteed by box 30. Move the budget to see how much extra room is needed for high completion probability.

The exact calculation tracks the number of distinct types seen: from k types, stay at k with probability k/n or advance to k+1 with probability (n−k)/n. This works because all types are equally likely. With unequal coupon probabilities, the identity of the missing types matters, so this small state model and the nHₙ formula no longer apply.

A rare coupon changes the bottleneck

Switch to Coupon 1 is ten times rarer. Its probability is 0.1/n; the other n−1 types share the remaining probability equally. At n=10, coupon 1 appears in 1% of boxes, and each other type in 11%. Waiting for coupon 1 alone takes 100 draws on average, so the expected time to finish the whole set must be at least 100. The uniform answer, 29.29, no longer describes this experiment.

The nonuniform calculation tracks two things: how many common types you have and whether coupon 1 has appeared. If k common types are collected, the probability of a new common type is (n−1−k) times its individual probability. A missing rare type adds another 0.1/n chance of progress. Otherwise the draw is a duplicate. The exact completion probability advances these state probabilities once per box; the expected duration sums geometric waits between discoveries. The histogram samples those same waiting stages without discarding long runs.

For two equally likely types, the first box always adds a type and the remaining wait has mean 2, giving E[T]=3. Completion by draw m≥1 has probability 1−2·(1/2)^m. This provides a small case you can verify by listing every sequence.

Reference

Random Services: the coupon collector problem develops the uniform waiting-stage model and completion distribution. The two-state-group recurrence above derives the specific nonuniform variant used here.