Panini football stickers and the Coupon Collector Problem

Yesterday I was over at my sister’s, and her lad was excited because he had the new South Africa World Cup 2010 Panini sticker book. He had also bought four packets, each with five stickers in them, and I had the important job of unpeeling them so that he could put them in the album.

There are 638 stickers to collect in total and it made me wonder how many stickers you would expect to have to buy so that you had a complete set. I was interested in how many you would need to buy without doing swapsies with anybody and on the premise that there were an equal number of each sticker and that they were randomly distributed.

Be warned, there’s some maths up ahead.

This sort of problem has been modelled as the Coupon Collector’s problem by mathematicians and I’ll walk gently through the explanation to get to the answer to the problem applied to the World Cup football stickers album.

Step 1 – Probability of getting a new sticker

Now, the first sticker you take is absolutely guaranteed to not be one you have already got. The second sticker has a 637 in 638 chance of being a new sticker. Once you have this second sticker then the probability of the next sticker being different to the first two is 636 in 638 and so on . .. . . . . .until you have all but one of the stickers in your album to fill. Then, you have a 1 in 638 chance of any sticker being that last one you want.

Step 2 – Number of stickers we expect to buy to get a new one

So, we know we can work out the probability of getting a new sticker at any point. But we don’t want to know the probability of each sticker we open being a new one. What we actually want to know is how many stickers we should expect to open each time to get a new one.

This is actually quite easy. If you know the probability, call it p, of an event happening, then the expected number of times you should have to do something to get the outcome you want is 1/p.

To make sense of this then think of throwing a die. If you want to throw a 6 then you know that you have a 1 in 6 chance of throwing one. It makes sense that you should expect, on average, to throw a die 6 times until you get a 6.

So, to get the total number of stickers you should expect to buy altogether then you just add up the number of stickers you expect to buy to get the first, the second, the third . . . . . .right through to the 638th sticker.

Still with it?

Step 3 – Adding it all up

Turning this into numbers, this means that we want to work this sum out

1 + 638/637 + 638/636 + . . . . . . 638/2 + 638/1

And that, my friends, is an harmonic series, so it is. And, to estimate the sum of an harmonic series, and skipping some of the maths, we can use the equation

S = n ln(n)

In the equation above, applied to our example, S is the total number of stickers we should expect to have to buy, n is 638, the number of unique stickers we want to get, and ln(n) is the natural log of n. So

S = 638 x ln(638)

S = 638 x 6.46

S = 4120

And so, unless you swap, then you should expect to have to buy 4120 stickers, at a total cost of £412, to fill your Panini sticker album.

Which all goes to show, that it is far better to be sociable than rich.