The Probable Pen in the Cereal Box

Date: 11/25/1999 at 02:00:45
From: Darren Kuropatwa
Subject: Expected Value - The Cereal Box Problem

Hi, 

I'm a high school math teacher in Winnipeg, Manitoba. At Mike 
Cornell's website from the University of Illinois at Urbana-Champaign 
I came across an interesting activity I'd like to do with my class on 
expected value:

Fun with Probability! The Probable Pen in the Cereal Box
http://lrs.ed.uiuc.edu/students/mcornell/cerealbox/probability.html   

The problem goes like this: Breakfast cereals sometimes come with 
"prizes" inside. Let's say there are six prizes being offered - 
different colored pens. How many boxes of cereal do you have to buy 
until you have received six pens of different colors?

At the Web site, the answer provided is that the expected number of 
boxes is:

     6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1 = 14.7.

I've verified this experimentally, but I don't understand why it is 
the correct answer.

The way I see it, I expect to get 6 pens and, since a great many pens 
are randomly distributed in the boxes the probabilities should be 
independent. So, the probability of getting any one color of pen in 
any box is 1/6. Then the expected value should be something like:

     6*1/6 + 6*1/6 + 6*1/6 + 6*1/6 + 6*1/6 + 6*1/6 = 6

but that's obviously wrong. However, this line of reasoning brought me 
back to the proposed solution, which I rewrote like this:

       6*1/6 + 6*1/5 + 6*1/4 + 6*1/3 + 6*1/2 + 6*1/1
     = 6(1/6 + 1/5 + 1/4 + 1/3 + 1/2 + 1/1)

So my expected gain is 6 pens, but how can the probability of each 
event (getting a prize in a box of cereal) be dependent in this way? 
Surely the probability of getting a pen I want in the first box is 
6/6, in the second box 5/6, in the third 4/6 ands so on. Now I know 
that this product (6/6 * 5/6 * 4/6 * 3/6 * 2/6 * 1/6 gives the 
probability of getting six different colored pens in exactly six 
boxes. But why is the sum of the reciprocals of these probabilities 
the answer to the problem?

I don't know if I've given you a lucid explanation of the (lack of?) 
progress I've made in understanding this problem but a colleague and I 
have spent the whole day discussing it and neither of us has come up 
with a satisfactory way to explain why the solution is what it is - 
let alone teach it!

I hope you can help...

Regards,
Darren Kuropatwa

Date: 11/25/1999 at 06:00:14
From: Doctor Anthony
Subject: Re: Expected Value-The Cereal Box Problem

There are two ways to answer the question. One is by difference 
equations, which is quick and neat, and the other by considering sums 
of infinite series. I have given both methods below.

This situation is modeled exactly by throwing a die until all the 
numbers have turned up. As you know, you could theoretically throw the 
die ten billion, billion times without getting all the numbers. 
However the question is what the expected number of throws (the 
mean number of throws) is before all six numbers have turned up.

The first throw will certainly produce a new number. We must now find 
the expected number of throws to the next new number. This has a 5/6 
probability of being new, so we set up a difference equation as 
follows. Let 'a' be the expected number of trials to a second new 
number. We must make at least one trial, and we have a 1/6 probability 
returning to '1+a'. So

         a = (5/6)1 + 1/6(1+a)

     5/6 a = 1

         a = 6/5

For the third new number let b be the expected number of further 
trials. This time there is 2/6 = 1/3 probability of returning to b.

         b = (2/3)1 + 1/3(1+b)

     2/3 b = 1

         b = 3/2 = 6/4

and to the fourth new number we have

         c = (1/2)1 + 1/2(1+c)

     1/2 c = 1

         c = 2  = 6/3 

The pattern is now clear. The expected number of trials to 6 new 
numbers is:

     E(no. of trials) = 6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/2 + 6/1

                      = 6[1/6 + 1/5 + 1/4 + 1/3 + 1/2 + 1/1]

                      = 6 x 49/20

                      = 14.7

So on average you should get all six numbers by the 15th throw.


Alternative Method
------------------

The first throw must produce a new number. We now consider the 
expected number of throws to the second new number.

The probability of a new number is 5/6

E(throws) = 1(5/6) + 2(1/6)(5/6) + 3(1/6)^2(5/6) + 4(1/6)^3(5/6) + ...

          = (5/6)[1 + 2(1/6) + 3(1/6)^2 + 4(1/6)^3 + ... [to infinity]

To sum the series in brackets we proceed as follows:

Put x = (1/6) and we require the sum to infinity of [1+2x+3x^2+...]

Let       S = 1 + 2x + 3x^2 + 4x^3 + ...
         xS =      x + 2x^2 + 3x^3 + ...
     ------------------------------------   subtract
     (1-x)S = 1 +  x +  x^2 +  x^3 + ...    [to infinity]

     (1-x)S = 1/(1-x) 

          S = 1/(1-x)^2

            =  1/(1-1/6)^2

            =  1/(5/6)^2

            =  36/25

and so the expression (5/6)S = (5/6)(36/25) = 6/5

And so the expected further throws to get the second new number is 
6/5.

By similar arguments, the expected further throws to the third new 
number is 6/4, and to the fourth new number is 6/3, and so on.

Expected throws to all 6 numbers = 6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1

    or putting in reverse order  = 6[1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6] 

                                 = 6 x 49/20

                                 = 14.7

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/