There is a free gift in my breakfast cereal.
probability/coupon Added material
Problem
There is a free gift in my breakfast cereal. The manufacturers say that the gift comes in four different colors, and encourage one to collect all four (& so eat lots of their cereal). Assuming there is an equal chance of getting any one of the colors, what is the expected number of boxes I must consume to get all four? Can you generalise to n colors and/or unequal probabilities?
Show solution
The problem is well known under the name of "COUPON COLLECTOR PROBLEM".
The answer for n equally likely coupons is
(1) C(n)=n*H(n) with H(n)=1+1/2+1/3+...+1/n.
In the unequal probabilities case, with p_i the probability of coupon i,
it becomes
(2) C(n)=int_0^infty [1-prod_{i=1}^n (1-exp(-p_i*t))] dt
which reduces to (1) when p_i=1/n (An easy exercise).
In the equal probabilities case C(n)~n log(n). For a Zipf law,
from (2), we have C(n)~n log^2(n).
A related problem is the "BIRTHDAY PARADOX" familiar to people
interested in hashing algorithms: With a party of 23 persons,
you are likely (i.e. with probability >50%) to find two with
the same birthday. The non equiprobable case was solved by:
M. Klamkin and D. Newman, Extensions of the birthday
surprise, J. Comb. Th. 3 (1967), 279-282.
Additional material
In article <1994Jul18.192945.14645@bnlux1.bnl.gov>,
Shiping Zhang <ping@bnlux1.bnl.gov> wrote:
> My question is how to calculate, if possible/meaningful, the probability
> of getting all four by purchasing certain number of boxes. For example,
> if one purchases four boxes, the probability (my understanding)
> to get all four colors is .09375, or 24/256 (n!/(n^n)). What is the
> probability if one purchases 5 boxes, 6 boxes, ...? How to calculate
> the probability to get all n colors by purchasing m boxes? (It's obvious
> that if m<n, the probability is zero.)
The probabilities of having m colors after purchasing n boxes can be
calculated easily from the probabilities of having m-1 or m colors after
purchasing n-1 boxes. Let P(m,n) be the desired probability. Then
P(1,1) = 1, P(2,1) = P(3,1) = P(4,1) = 0
and \
P(1,n) = (1/4) * P(1,n-1) |
P(2,n) = (3/4) * P(1,n-1) + (1/2) * P(2,n-1) > n = 2, 3, ...
P(3,n) = (1/2) * P(2,n-1) + (3/4) * P(3,n-1) |
P(4,n) = (1/4) * P(3,n-1) + P(4,n-1) |
/
so we can fill in the probability table to whatever value of n we want.
n P(1,n) P(2,n) P(3,n) P(4,n)
- ------ ------ ------ ------
1 1 0 0 0
2 1/4 3/4 0 0
3 1/16 9/16 3/8 0
4 1/64 21/64 9/16 3/32
5 1/256 45/256 75/128 15/64
6 1/1024 93/1024 135/256 195/512
7 1/4096 189/4096 903/2048 525/1024
Since the last number, 525/1024, exceeds 1/2, you must buy 7 boxes to
have at least a 50 - 50 chance of having all four colors.
Now, if you are asking if there is a closed form solution for P(m,n) in
terms of m and n, the answer is "Yes," simply the solutions of the linear,
constant coefficient difference equations given above. In fact, you can
probably see the formulas for P(1,n) and P(2,n) by inspection. I'll leave
it to you to discover the formulas for P(3,n) and P(4,n).
-- Dave Dodson <dodson@convex.COM>
[ Editor: from the April 1997 thread "Coupon Collector archive entry",
which Chris Cole began by posting a question for Eric Farmer. ]
>I'm new to rec.puzzles; I found the index on Arlet Ottens' page some
>weeks ago. I have a question about the "coupon collector" problem (as
>stated in the archive index): how many boxes of cereal must you expect
>to consume to collect all 4 (or n) colors of toys if each color toy is
>equally likely?
>
>Putting these results together gives the correct solution, but I don't
>see a counting argument for the formula given in the archive solution:
>n*(1 + 1/2 + ... + 1/n). How is this formula derived?
>
>-- Eric Farmer <erf@ksu.ksu.edu>
Pretty easily, actually.
Suppose you already have n-1 prizes, and you're trying to get that last
one. Since the probability of finding it in a box is 1/n, you can
expect to buy n boxes before getting it. Suppose you already have n-2
prizes, and you're trying to get the last two prizes. Since the
probability of finding a prize you don't have in a box is 2/n, you can
expect to buy n/2 boxes before getting it. At that point, you'll have
n-1 prizes, and as above, you can expect to buy n boxes before getting
that. And if you already have n-3 prizes, you can expect to buy n/3
boxes before getting a new prize, and then n/2+n boxes after that.
Continuing the induction finishes the formula. Note that if you have
no prizes, you can expect to buy n/n = 1 boxes before you get a prize
you don't have, which makes a lot of sense.
-- Wei-Hwa Huang <whuang@ugcs.caltech.edu>
We're actually computing the expected number of boxes to consume to
collect all n colors of toys.
Let X be the number of boxes consumed to collect all n colors.
Let X_i be the number of boxes consumed after collecting i colors to
collect i+1 colors.
Then X = X_0 + X_1 + ... + X_{n-1}.
So E[X] = E[X_0] + E[X_1] + ... + E[X_{n-1}].
After you've collected i colors of toys, there are n-i colors left out
of n that will give you an i+1st color. So E[X_i] = n/(n-i).
So E[X] = n * ( 1/n + 1/(n-1) + ... + 1).
-- Randall M! Gee <gee@math.berkeley.edu>