Vol. I a living index of named laws · est. mmxxvi no ads · no tracking
The Law Tomeindex of named laws

The Coupon Collector's Problem

also known as — The collector's problem, Completing the set
"Collecting the whole set takes far longer than the last few items, because the final ones almost never turn up."
In plain English

What does The Coupon Collector's Problem mean?

The coupon collector's problem asks how many random draws it takes to collect a complete set of distinct items when each draw yields one of the items uniformly at random. If there are n different coupons, the expected number of draws to collect them all is n times the nth harmonic number, which for large n is close to n times the natural logarithm of n. The striking feature is how the tail dominates: the early coupons arrive fast, but the last few are agonisingly slow, since once only one is missing each draw has just a one-in-n chance of being the one you need. It is the mathematics of why finishing a sticker album costs so much more than starting one.

In symbols

What is the formula for The Coupon Collector's Problem?

W = \{ u \in L^p ([0, T]; X_0) | \dot{u} \in L^q ([0, T]; X_1) \}.
The defining formula as recorded on Wikidata. W = \{ u \in L^p ([0, T]; X_0) | \dot{u} \in L^q ([0, T]; X_1) \}.
Run the numbers

The Coupon Collector's Problem calculator

How many random draws to collect the whole set: n times the nth harmonic number.

E = n (1 + 1/2 + ... + 1/n)

n
Number of distinct coupons
Expected draws —
Draws per coupon —

Computed live from E = n (1 + 1/2 + ... + 1/n) — the law's own arithmetic, nothing fitted or predicted.

Reliability

Rated Empirical: grounded in studies or measurable evidence. The other 608.

How it works

How does The Coupon Collector's Problem work?

The total wait is a sum of independent geometric waits, one for each new coupon. After you already hold some coupons, the chance that a draw brings a genuinely new one shrinks as the missing set shrinks: with k distinct coupons in hand, a new one appears with probability n minus k over n, so the expected wait for it is n over n minus k. Adding these waits from the first coupon to the last gives n times the harmonic sum, one plus a half plus a third and so on down to one over n. The last term, waiting for the final coupon, alone contributes an expected n draws, which is why the endgame is so long.

Figure illustrating The Coupon Collector's Problem
The Coupon Collector's Problem — Cmglee · CC BY-SA 3.0 · source
Where you'll see it

What are examples of The Coupon Collector's Problem?

Fifty coupons For a set of 50 coupons the expected number of draws to complete it is about 225, more than four times the set size, most of it spent chasing the last handful.
Sticker albums Completing a Panini-style football album of several hundred stickers bought in random packs takes, on average, far more packs than there are stickers, the coupon collector's tail in everyday life.
Coverage testing Estimating how many random test runs are needed to exercise every code path, or how many samples to observe every species, is the same calculation.
Types & variants

What are the types of The Coupon Collector's Problem?

The Gumbel tail§

Erdős and Rényi showed the completion time, once centred and scaled, converges to a Gumbel distribution, so the collection time is concentrated around n log n with a heavy right tail.

Unequal coupons§

If some coupons are rarer than others, the expected completion time only grows, since the rarest items come to dominate the wait, which the uniform formula does not capture.

Why it matters

Why does The Coupon Collector's Problem matter?

The coupon collector's problem is a canonical result in probability with a long practical reach, into card and sticker collecting, software test coverage, ecological species estimation, cache and hashing analysis, and DNA sequencing coverage, wherever one must draw at random until every category is seen. Its central lesson, that completing the set costs vastly more than getting most of it and that the growth is n log n rather than linear, is a durable corrective to the intuition that the last piece should be no harder than the first. It also anchors the analysis of the last-item bottleneck in many randomised systems.

Working with it

How do you apply The Coupon Collector's Problem?

  • Expect the tail to dominate — budget for the last few items, since waiting for the final coupon alone takes on average as many draws as the whole set has coupons.
  • Scale as n log n — remember that collecting all of n items grows faster than linearly, so doubling the set more than doubles the expected effort.
  • Beware unequal odds — treat the clean formula as a best case, since rarer items make real completion much slower than the uniform result suggests.
Where it breaks down

What are the limits of The Coupon Collector's Problem?

The standard result assumes each draw is independent and every coupon equally likely, an idealisation. When coupons have unequal probabilities, as promotions often arrange, completion takes strictly longer, because the rarest items dominate the wait, and the simple n-times-harmonic formula understates the true effort. The result is about the expected time and its distribution, which has a heavy right tail, so individual attempts vary widely around the average and a run can take far longer than n log n. It also assumes the set size n is fixed and known, and draws are with replacement from a stable pool.

What it doesn't say

What are common misconceptions about The Coupon Collector's Problem?

It does not grow linearly with the number of items; the expected time is about n times the log of n, which is super-linear, so a bigger set is disproportionately harder. It does not say the last coupon is as easy as the first; the final one takes on average n draws by itself. And the clean formula assumes uniform, independent draws, so it is a lower bound on the effort when real-world items are unequally common.

Is it real?

Is The Coupon Collector's Problem real?

Yes, as far as the evidence goes. The Coupon Collector's Problem is rated Empirical here: it rests on studies or measurements rather than on a saying.

Rated from two sources. 609 of the 1,116 entries carry this rating. How the scale works.

Seldom printedin printed books: one of 194 names in its band, of 903 measured
35 of 49entries in statistics & probability carry the same rating

The best-known laws are the least likely to rest on measurement.

Origin

Where did The Coupon Collector's Problem come from?

A classic problem of elementary probability with roots in the work of de Moivre and Laplace, given its modern distributional treatment by Paul Erdős and Alfréd Rényi in the 1960s.

How the name spread

When did people start saying “The Coupon Collector's Problem”?

18002019
How often “Coupon Collector 's Problem” appears in printed English, which takes hold around 1962 and peaks around 1967. This tracks the phrase and not the idea. A law is usually older than the name for it. Source: Google Books Ngrams.
Known elsewhere as

What is The Coupon Collector's Problem called in other languages?

  • GermanSammelbilderproblem
  • Spanishproblema del coleccionista de cupones
  • Frenchproblème du collectionneur de vignettes
  • ItalianProblema del collezionista
  • Japaneseクーポン・コレクター問題
  • PortugueseProblema do colecionador de cupons
  • Russianзадача собирателя купонов
  • Chinese贈券收集問題

8 languages, as recorded on Wikidata. These are names the idea already goes by, not translations we made. The whole index by language.

Sources

Sources & further reading

  1. 1Coupon collector's problem, Wikipedia. — the n-times-harmonic expectation, the geometric mechanism, the variance bound, and the Erdős-Rényi Gumbel limit.secondary
  2. 2Coupon Collector Problem, Brilliant Math & Science Wiki. — the expected value and the per-stage geometric derivation.secondary

Everything above traces to en.wikipedia.org and brilliant.org: two secondary sources, accounts of the original rather than the original itself, which has not been located for this entry. Nothing is written from memory, and the method is written down. Spot an error or a better source? Suggest a fix.

What we checked

  • 1,116entries in the tomeListed one by one on the browse page.
  • 1,116of them citing a sourceOpen any entry: its sources sit at the foot of the page.
  • 2,489source references in allEach is named, and linked wherever the source is online.