Introduction to Probability · Problem 34

Combinatorics — Grinstead & Snell

Mathematics — Probability · inclusion-exclusion

Problem

Assume that every time you buy a box of Wheaties, you receive one of the pictures of the

n

players on the New York Yankees. Over a period of time, you buy

m \geq n

boxes of Wheaties. ((a)) Use Theorem 3.8 to show that the probability that you get all

n

pictures is

1 - \binom{n}{1}\left(\frac{n-1}{n}\right)^m + \binom{n}{2}\left(\frac{n-2}{n}\right)^m - \cdots + (-1)^{n-1}\binom{n}{n-1}\left(\frac{1}{n}\right)^m.

Hint: Let

E_k

be the event that you do not get the

k

th player's picture. ((b)) Write a computer program to compute this probability. Use this program to find, for given

n

, the smallest value of

m

which will give probability

\geq .5

of getting all

n

pictures. Consider

n = 50, 100,

and

150

and show that

m = n \log n + n \log 2

is a good estimate for the number of boxes needed.