The coupon collector
Tonight's idea
An album has 50 stickers. Each packet holds one, equally likely to be any of the 50, independently of the rest. How many packets to fill the album?
Split the hunt into stages. Holding \(k\) different stickers, a packet is useful with probability \((50 - k)/50\). Open packets until one is useful, then move on.
How long is a stage? If a trial succeeds with probability \(p\), call the expected number of trials \(T\). The first trial is used whatever happens; with probability \(1 - p\) it failed and you are back at the start, facing \(T\) more on average. So
\(T = 1 + (1 - p)\,T\), hence \(T = 1/p\).
A 1-in-10 chance takes 10 tries on average (a geometric waiting time). Expected values add, so the total is the sum of the stages:
\[E = \frac{50}{50} + \frac{50}{49} + \cdots + \frac{50}{1} = 50\left(1 + \frac12 + \cdots + \frac{1}{50}\right) = 50\,H_{50},\]
where \(H_n = 1 + \tfrac12 + \cdots + \tfrac1n\) is the \(n\)th harmonic number. For \(n\) stickers, \(E = n H_n\).
\(H_{50} \approx 4.499\): about 225 packets, 50 of them for the last sticker. \(H_n\) grows like \(\ln n + 0.577\) (see infinite series), so the cost grows like \(n \ln n\), and the tail is where the money goes.
Watch one: all six faces of a die
Roll a die until every face has appeared. Six stickers, one per packet. Stage lengths: the first roll always counts, \(6/6 = 1\). Then a new face has probability \(5/6\), wait \(6/5 = 1.2\). Then \(6/4 = 1.5\), \(6/3 = 2\), \(6/2 = 3\), and finally \(6/1 = 6\) rolls for the last face.
\[E = 1 + 1.2 + 1.5 + 2 + 3 + 6 = 14.7 = 6 H_6.\]
The first three faces take only \(1 + 1.2 + 1.5 = 3.7\) rolls; the last face alone takes six. Try it with a real die and a tally: most runs land between 10 and 20.
Your turn
- An album has 10 stickers. Find the expected number of packets, as an exact fraction and a decimal. How many of those packets, on average, go on the last two stickers?
- For the 50-sticker album, find the expected number of packets to collect the first 25 stickers, and the expected number to collect the remaining 25. (\(H_{25} \approx 3.816\), \(H_{50} \approx 4.499\).)
- Use \(H_n \approx \ln n + 0.5772\) to estimate the cost of the 50-sticker album and compare with \(50 H_{50} = 224.96\). Then estimate the cost of a 500-sticker album.
- A set has just two stickers, but the first appears in 90% of packets and the second in 10%. Find the expected number of packets to complete the set. Compare with \(2 H_2 = 3\) for a fair pair, and say exactly where the derivation of \(n H_n\) breaks.
Stretch: after the average, still not done
After \(m\) packets, a particular sticker is still missing with probability \((1 - \tfrac1{50})^m\), so the expected number of missing stickers is \(50 \times 0.98^m\). Evaluate this at \(m = 225\). Then find the smallest \(m\) for which the expected number missing is at most \(0.1\). What does this say about the average 225?
Answers
- \(10 H_{10} = 10 \times \tfrac{7381}{2520} = \tfrac{7381}{252} \approx 29.29\) packets. The last two stickers take \(\tfrac{10}{2} + \tfrac{10}{1} = 15\) of them: over half the total for a fifth of the album.
- First 25: \(\tfrac{50}{50} + \cdots + \tfrac{50}{26} = 50(H_{50} - H_{25}) \approx 50 \times 0.683 = 34.2\) packets. Remaining 25: \(50 H_{25} \approx 190.8\) packets. The second half costs more than five times the first.
- \(50(\ln 50 + 0.5772) = 50 \times 4.489 \approx 224.5\), against 224.96; the error is \(50 \times \tfrac{1}{100} = 0.5\), the \(1/(2n)\) gap in the figure. For 500 stickers, \(500(\ln 500 + 0.5772) \approx 3{,}396\) packets, nearly seven times the album size.
- The first packet gives one sticker. With probability \(0.9\) it is the common one, and the rare one then takes \(1/0.1 = 10\) packets on average; with probability \(0.1\) it is the rare one, and the common one takes \(1/0.9\). So \(E = 1 + 0.9 \times 10 + 0.1 \times \tfrac{10}{9} \approx 10.1\) packets, more than three times the fair 3. The derivation used "a new sticker has probability \((n-k)/n\)", which assumes every missing sticker is equally likely; here the stage length depends on which sticker is missing.
Stretch. \(50 \times 0.98^{225} \approx 0.53\): after the "average" number of packets you are missing about half a sticker on average, so a sizeable share of collectors are not finished. For \(50 \times 0.98^m \le 0.1\) you need \(m \ge \ln(0.002)/\ln(0.98) \approx 307.6\), so \(m = 308\). The mean is pulled up by long unlucky tails; the typical collector finishes a little before 225, and the unlucky ones well after.