Completing a collection
A Socratic walk-through of completing a collection — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why does collecting the last few stickers in a set take longer than collecting all the rest?
A child fills a hundred-sticker album. The first fortnight is exhilarating: nearly every packet brings something new. Then it slows. By the end, whole weeks pass for one sticker, and the last few seem actively withheld.
The natural suspicion is that the manufacturer prints them short. Set that aside for a moment and ask a cleaner question: if every sticker were printed in exactly equal numbers and every packet drawn at random, would the ending still drag?
Reasoning it through
REASONING #Ask what changes as the album fills. Nothing about the packets — each is a fresh uniform draw from the hundred. What changes is you. When you hold 20 stickers, 80 of the hundred are useful, so a packet is new with probability 80 in 100. When you hold 99, exactly 1 is useful, and a packet is new with probability 1 in 100.
Now turn a probability into a waiting time. If each independent packet is a success with probability p, how many do you expect to open before the first success? On average 1 divided by p. That is the whole engine of this problem, and it is worth pausing on: waiting time is the reciprocal of probability, and reciprocals blow up as the probability approaches zero.
So put the two together. Holding k of n stickers, the chance a packet is new is (n - k) / n, and the expected wait for the next new one is n / (n - k). Sum that across every stage from an empty album to a full one, and the expected total is n multiplied by the sum 1 + 1/2 + 1/3 + … + 1/n — the harmonic number.
Check it on a case small enough to hold in your head. With 4 stickers: 4 x (1 + 1/2 + 1/3 + 1/4) = 4 x 25/12, which is 25/3, about 8.3 packets for 4 stickers. Note that the first sticker costs 1 packet and the last costs 4 — a set of four already has an ending four times slower than its beginning.
For a hundred stickers the harmonic number is about 5.187, giving roughly 519 packets. Now split that total up, because the shape of it is the answer to the question. Reaching your first 50 stickers costs about 69 packets. Getting from 50 to 90 costs about 157. The final ten cost about 293 — more than the first ninety combined. And the very last sticker alone costs 100 on average, a fifth of the whole campaign for one card.
Is there a compact way to say how this grows? Yes: the harmonic number is close to the natural logarithm of n plus about 0.577, so the expected total is near n times the logarithm of n. For a hundred stickers that estimate gives 518, against the exact 519. The logarithm grows very slowly, which means the cost per sticker grows slowly too — the collection is not exponentially hard, it is just heavily back-loaded.
The analogy
THE ANALOGY #Think of fishing a lake stocked with a hundred differently tagged fish, where every fish you catch is measured, recorded and thrown back. Early on almost every catch is a tag you have not recorded. By the time you have ninety-nine tags, you are casting repeatedly into a lake in which ninety-nine hundredths of the fish are already known to you, and only one in a hundred casts tells you anything.
every fish in the lake is genuinely equally catchable, whereas real sticker sets are printed and distributed in ways nobody guarantees to be uniform — and as we will see, once one item is scarcer than the others, the mathematics of the ending changes character rather than merely stretching.
Clarifying the model
THE MODEL #Three refinements hold this together.
The slowdown needs no villain. This is the point most worth taking away. Uniform printing, honest randomisation, and the ending still costs more than the whole beginning. Difficulty at the end is not evidence of manipulation, and a collector who infers a conspiracy from it is reasoning from a real observation to an unnecessary cause.
But the uniformity hypothesis is doing real work, and it is the one that fails in practice. Suppose one sticker is printed with probability one in a thousand rather than one in a hundred. Then the expected wait for that sticker alone is about a thousand packets, and it dominates the entire total — the neat harmonic sum is replaced by a single term. This is also what would refute the plain model on real data: if collectors of a given album routinely take several times the predicted number of packets, and their difficulty concentrates on the same few stickers rather than on whichever ones they happen to lack, the uniform assumption is wrong. Concentration on the same identifiable stickers is the discriminating observation. Ordinary randomness spreads the pain evenly across collectors; scarcity does not.
Independence is also assumed, and real distribution violates it in the collector's favour. Packets contain no internal duplicates, and boxes are often filled with deliberately spread contents, both of which speed collection relative to the model above. Trading helps more still: several collectors pooling duplicates finish far sooner than each alone.
It is also worth setting this beside its mirror image, the birthday problem in this collection. Both draw repeatedly from the same urn of n items. The birthday question asks when the first repeat appears, and the answer is after about the square root of n draws. This one asks when the repeats finally stop being all you get, and the answer is n times the logarithm of n. Repetition starts almost immediately and completion takes almost forever — two very different numbers from one identical experiment, which is why intuition trained on one misleads badly on the other.
A picture of it
THE PICTURE #How to readThe whole circle is the roughly 519 packets a complete album is expected to cost. Each slice is the expected number of packets spent while crossing one stretch of the album, not the number of stickers gained — so the largest slice, the final ten stickers, is ten stickers costing 293 packets, while the smallest slice is fifty stickers costing 69. Compare the slices rather than reading them as progress: half the album arrives inside the small wedge, and more than half the effort goes into the last tenth.
What became clearer
WHAT CLEARED #The ending drags because waiting time is the reciprocal of probability, and the probability of a useful packet falls to one in n as the album fills. Summing those reciprocals gives a harmonic number, so completion costs about n times the logarithm of n, back-loaded so severely that the last ten stickers of a hundred cost more than the first ninety together. No scarcity is required to produce that experience — which is precisely why the experience is such poor evidence of scarcity, and why the test for real scarcity has to look at whether different collectors get stuck on the same stickers.
Where to go next
ONWARD #- How pooling and trading between collectors changes the expected completion time.
- The distribution around the mean, not just the mean: how variable the finishing point actually is.
- The same mathematics in software testing and ecology, where it estimates how many distinct bugs or species remain unseen.
Key terms
TERMS #| Term | What it means |
|---|---|
| Coupon collector's problem | the classical name for this question: how many uniform random draws are needed to see all n items. |
| Harmonic number | the sum 1 + 1/2 + … + 1/n, close to the natural logarithm of n plus 0.577. |
| Expected waiting time | for independent trials each succeeding with probability p, the mean number of trials to the first success is 1/p. |
Every term the collection defines is gathered in the glossary.