Thought Toys · Chance · Exhibit 42
Draw a random sticker from a fixed set, over and over, hoping to complete the set. The first new one comes almost immediately. The very last one can take, in expectation, as long as collecting nearly everything else combined.
The coupons — lit when collected0 / 100
Draws so far vs. distinct coupons collected this runexpected
n = 100 coupon types
—
Every draw picks one of n coupon types uniformly at random — you might get a duplicate. The amber grid lights each type the first time it appears; the chart tracks draws-so-far against how many distinct types you've collected. Early on the two climb together — almost every draw is new. But the dashed theoretical curve bends over hard near the top — the closer you get to finishing, the more of your draws are wasted re-rolling coupons you already own. The last coupon alone takes n draws in expectation — the same order of magnitude as the entire rest of the collection put together.
Drag n down to 10 and hit "Draw until done" a few times: the very last coupon regularly eats most of the run. Drag it up to 300 and the effect looks gentler in absolute terms, but it never goes away — the last five coupons, out of however many hundred, still cost a share of the total effort that's dozens of times larger than their 5-out-of-n headcount would suggest.
improve/verify/42-coupon-collector.js): a 20,000-trial
Monte Carlo matches n·H(n) within 2% for several n; the mean
wait for the very last coupon alone matches n within 3%; the last-5-coupons share of total
effort, H(5)/H(n), is 78% at n=10, 44% at n=100, and
still 30% at n=1000 — always far above the naive "5 out of n" proportional guess.
Negative controls: a deterministic full cycle through every type exactly once takes
exactly n draws, not n·H(n) — the entire gap is the price of
random re-drawing, not of merely needing n distinct items; and skewing the draw
probabilities away from uniform makes the expected total larger, never smaller — uniform
probabilities are provably the best case, confirming the blowup is a real property of random collection,
not an artifact a cleverer distribution could avoid.
Also in Chance: Genetic drift →
← the cabinet · Thought Toys — a cabinet of explorable explanations. Exhibit 42.