📖 Theory — harmonic numbers
N coupon types with
equal probability. Once you already hold k distinct
coupons, the chance a new draw is one you are missing is
(N − k) / N. The number of draws to get the next new
coupon is therefore geometric with mean
N / (N − k). Summing over k = 0 … N − 1
gives the expected total time
E[T] = N·(1/N + 1/(N−1) + … + 1/1) = N·H_N, where
H_N is the N-th harmonic number.
📐 The last coupon dominates ~ N·ln N
H_N ≈ ln N + γ (with the Euler–Mascheroni
constant γ ≈ 0.5772), the expectation is
E[T] ≈ N·ln N + γN. The biggest single contribution is
the very last coupon: when you are missing only one type, each draw
hits it with probability 1/N, so that final coupon
alone costs about N draws on average. This is the
"diminishing returns" effect — the coverage curve flattens out and
the long tail of completion times comes almost entirely from waiting
on the last one or two coupons.
🃏 Applications
N·ln N — much faster than the naive guess of
N draws.
About Coupon Collector's Problem
The Coupon Collector's Problem is a classic result in probability theory that asks: if each random draw yields one of N equally likely coupon types, how many draws are needed on average to collect at least one of every type? The exact expected number is E[T] = N · HN, where HN = 1 + 1/2 + 1/3 + … + 1/N is the N-th harmonic number. This simulation lets you watch the collection process in real time, trace the slowing coverage curve, and compare the empirical mean over hundreds of trials to the theoretical prediction.
The problem has practical relevance wherever random sampling must achieve complete coverage: filling sticker albums and trading-card sets, generating random test inputs that exercise every code path, measuring the diversity of random hashing schemes, and estimating the effort needed to sample every item in a population at least once.
Frequently Asked Questions
What is the expected number of draws to collect all N coupons?
The exact expectation is E[T] = N · HN, where HN is the N-th harmonic number (the sum 1 + 1/2 + 1/3 + … + 1/N). Because HN grows as ln(N) + γ (with Euler–Mascheroni constant γ ≈ 0.5772), this simplifies to the well-known approximation E[T] ≈ N · ln(N) + γ · N. For example, with N = 20 coupons the expected number of draws is about 71.9.
How do I use this simulation?
Use the N slider to choose how many distinct coupon types exist (2–50), then click Play run to watch one animated collection unfold: the grid lights up each type as it is first seen, and the coverage curve shows the fraction collected over time. Click Run 100 trials to batch-simulate many completions instantly and build the histogram, which should cluster around the green E[T] line. The Speed slider controls how many draws are processed per animation frame.
Why does the coverage curve flatten out near the end?
When you already hold k out of N types, each new draw hits a missing type with probability only (N − k) / N. As k approaches N, that probability shrinks toward 1/N, so each new unique coupon becomes much harder to find. The expected number of draws to go from k to k+1 is N / (N − k), which grows without bound as k → N. This "diminishing returns" effect is what flattens the coverage curve and creates the long right tail in the completion-time histogram.
How is the harmonic-number formula derived?
The derivation uses the linearity of expectation. After collecting k distinct coupons, the waiting time until the next new one is geometrically distributed with success probability p = (N − k) / N, so its mean is N / (N − k). Summing over k = 0, 1, …, N−1 gives E[T] = N/N + N/(N−1) + … + N/1 = N · (1 + 1/2 + … + 1/N) = N · HN. The variance is also known: Var[T] = N2 · Σ(1/k2) ≈ N2 · π2/6 for large N.
What are real-world examples of the Coupon Collector's Problem?
Panini sticker albums are the most familiar example: a 2018 World Cup album had 682 stickers, and collectors needed an average of about 4,832 sticker purchases to complete it (buying in packs of 5). In software engineering, random fuzzing must generate enough test inputs to reach every branch; with N branches the expected effort grows as N · ln(N). Network protocols that assign random IDs face the same birthday-problem dual: how soon a collision occurs versus how many IDs are needed to cover a set.
Is it a misconception that you need exactly N draws to collect N coupons?
Yes — that would only be true if you could guarantee no repeats, like drawing without replacement. With replacement (independent random draws), duplicates are inevitable. The expected total grows as N · ln(N), not N, because the final few coupons each require many repeated draws before the missing type appears. For N = 50, the expected draws is about 225, not 50. The histogram also reveals a long right tail, meaning occasionally many more than the average are needed.
Who first studied the Coupon Collector's Problem and when?
The problem has roots in 18th-century combinatorics. Abraham de Moivre studied related occupancy problems in his 1718 work The Doctrine of Chances. The modern formulation and harmonic-number solution became well-known through mid-20th century probability textbooks. The name "coupon collector" was popularized as physical coupon sets and trading cards became common consumer items in the early 20th century, making it a natural analogy for the abstract occupancy problem.
What related probability problems or simulations are connected to this topic?
The Coupon Collector's Problem is closely related to the Birthday Problem (which asks when a collision first occurs rather than when all slots are filled), occupancy problems in combinatorics, and random hash function analysis. It is the dual of coupon-collecting: one asks for the first repeat, the other asks for complete coverage. Related simulations include the Birthday Paradox, random walk coverage problems, and Monte Carlo integration, all of which involve waiting times in random processes.
How is the Coupon Collector's Problem used in computer science and engineering?
In software testing, the problem quantifies how many random test inputs are needed to achieve complete code-path coverage — a benchmark for random (fuzzing) versus systematic test generation. In distributed systems, it models how many broadcast messages are required before every node in a network has received at least one. Load balancers and hash tables use related occupancy analysis to predict when all buckets will be non-empty. The N · ln(N) bound also appears in randomized algorithms for set cover problems.
What happens when coupons are not equally likely or appear in groups?
When coupon types have unequal probabilities, the harmonic-number formula no longer applies. The expected completion time is instead determined by the rarest coupon: if the least likely type has probability pmin, the expected draws grow at least as fast as 1/pmin. This is studied under the "non-uniform coupon collector" and can be dramatically worse than the uniform case. When coupons arrive in packs (as with sticker albums), the problem becomes a variant with correlated draws, analyzed through generating functions and simulation, which reveals that pack structures can slightly increase or decrease the expected total cost depending on pack size and overlap rules.