Draw at random, with replacement, until you've seen every item at least once. Getting most of the set is quick — but the last few stragglers drag on, because you keep drawing duplicates of what you already have. The total averages N·ln NN·ln N, give or take. Doubling the set size more than doubles the draws, because each extra item also has to wait out all the duplicates of the others., and the final coupon alone costs about N draws. It's the mirror imageThe birthday problem asks when any two draws first match; this asks when every value has been drawn at least once — the same urn, the opposite question. of the birthday problem.
to collect every one of 50.
items collected →
| Collect | Draws needed |
|---|---|
50%half the set | 34 draws |
90%9 in 10 | 111 draws |
99%99 in 100 | 225 draws |
100%every one | 225 draws |
The curve barely lifts off the floor for most of the set, then turns vertical at the end: collecting the second half costs far more than the first, because almost every draw is a duplicate of something you've already got. That's why the last sticker in the album is the one you buy a hundred packs chasing.