Probability Techniques

The Coupon Collector Problem

NeetQuant · August 2026 · 4 min read

A clean application of linearity of expectation and geometric waiting times, and a genuinely useful intuition about collection problems.

The problem

There are n distinct coupons. Each draw gives a uniformly random one. How many draws until you have all n?

The decomposition

Split the process by how many distinct coupons you already hold.

Suppose you have k distinct coupons. The chance a new draw is one you lack is (n - k)/n. So the number of draws to get the next new one is geometric with that success probability, and its expectation is n/(n - k).

By linearity, total expected draws:

E = n/n + n/(n-1) + n/(n-2) + ... + n/1 = n times (1 + 1/2 + ... + 1/n) = n H_n ≈ n ln n + 0.577 n

The intuition to keep

The last coupon is the expensive one. When you hold n - 1 of them, each draw has only a 1/n chance of helping, so that final coupon alone takes n draws on average - as long as the first half of the collection combined.

That is why collecting feels fine and then interminable. For n = 50, the expectation is about 225 draws, of which the last coupon alone accounts for 50.

Common variants

Expected draws to get half the coupons? Sum only the first n/2 terms. It comes to roughly n ln 2 ≈ 0.69n - fast, which is the flip side of the same asymmetry.

Unequal probabilities? Much harder and no clean closed form; if an interviewer raises it, the honest answer is to say so and describe the approach rather than pretend.

Two of each coupon? The leading term becomes n ln n + n ln ln n.

Variance

Worth knowing that the distribution is right-skewed with variance of order n^2. The mean is not a reliable guide to a typical bad run, which is the practical lesson whenever this shape appears in real systems.

Practise in expected value.

Keep practising

Practise quant interview questions free

Create a free account to attempt hundreds of questions with hints and answer checking, and to run the timed simulators.

Start practising free

Frequently asked questions

How many draws to collect all n coupons?
On average n times the n-th harmonic number, which is approximately n ln n + 0.577n. For 50 coupons that is about 225 draws, of which the final coupon alone accounts for 50.