The Coupon Collector Problem

In this section, our random experiment is to sample repeatedly, with replacement, from the population

D = {1, 2, \dots, m}

. This generates a sequence of independent random variables

X = (X_{1}, X_{2}, \dots)

, each uniformly distributed on

D

. We will often interpret the sampling in terms of a coupon collector: each time the collector buys a certain product (bubble gum or Cracker Jack, for example) she receives a coupon (a baseball card or a toy, for example) which is equally likely to be any one of

m

types. Thus, in this setting,

X_{i} \in D

is the coupon type received on the

i

th purchase.

Let

V_{n}

denote the number of distinct values in the first

n

selections, for

n \in N_{+}

. This is the random variable studied in the last section on the birthday problem. Our interest is in this section is the sample size needed to get a specified number of distinct sample values

For $k \in {1, 2, \dots, m}$ , let $W_{k} = min {n \in N_{+} : V_{n} = k}$ the sample size needed to get $k$ distinct sample values. $W_{k}$ takes values in the set ${k, k + 1, \dots}$ .

In terms of the coupon collector, this random variable gives the number of products required to get

k

distinct coupon types. We will be particularly interested in

W_{m}

, the sample size needed to get the entire population. In terms of the coupon collector, this is the number of products required to get the entire set of coupons.

In the coupon collector experiment, run the experiment in single-step mode a few times for selected values of the parameters.

The Probability Density Function

Now let's find the distribution of

W_{k}

. The results of the previous section will be very helpful

For $k \in {1, 2, \dots, m}$ , the probability density function of $W_{k}$ is given by $P (W_{k} = n) = (\binom{m - 1}{k - 1}) \sum_{j = 0}^{k - 1} (- 1)^{j} (\binom{k - 1}{j}) {(\frac{k - j - 1}{m})}^{n - 1}, n \in {k, k + 1, \dots}$

Details:

Note first that $W_{k} = n$ if and only if $V_{n - 1} = k - 1$ and $V_{n} = k$ . Hence $P (W_{k} = n) = P (V_{n - 1} = k - 1) P (V_{n} = k ∣ V_{n - 1} = k - 1) = \frac{m - k + 1}{m} P (V_{n - 1} = k - 1)$ Using the PDF of $V_{n - 1}$ from the birthday problem gives the result.

In the coupon collector experiment, vary the parameters and note the shape of and position of the probability density function. For selected values of the parameters, run the experiment 1000 times and compare the relative frequency function to the probability density function.

An alternate approach to the probability density function of

W_{k}

is via a recursion formula.

For fixed $m$ , let $g_{k}$ denote the probability density function of $W_{k}$ . Then

$g_{k} (n + 1) = \frac{k - 1}{m} g_{k} (n) + \frac{m - k + 1}{m} g_{k - 1} (n)$
$g_{1} (1) = 1$

Decomposition as a Sum

We will now show that

W_{k}

can be decomposed as a sum of

k

independent, geometrically distributed random variables. This will provide some additional insight into the nature of the distribution and will make the computation of the mean and variance easy.

For $i \in {1, 2, \dots, m}$ , let $Z_{i}$ denote the number of additional samples needed to go from $i - 1$ distinct values to $i$ distinct values. Then $Z = (Z_{1}, Z_{2}, \dots, Z_{m})$ is a sequence of independent random variables, and $Z_{i}$ has the geometric distribution on $N_{+}$ with parameter $p_{i} = \frac{m - i + 1}{m}$ . Moreover, $W_{k} = \sum_{i = 1}^{k} Z_{i}, k \in {1, 2, \dots, m}$

This result shows clearly that each time a new coupon is obtained, it becomes harder to get the next new coupon.

In the coupon collector experiment, run the experiment in single-step mode a few times for selected values of the parameters. In particular, try this with $m$ large and $k$ near $m$ .

Moments

The decomposition as a sum of independent variables provides an easy way to compute the mean and other moments of

W_{k}

The mean and variance of the sample size needed to get $k$ distinct values are

$E (W_{k}) = \sum_{i = 1}^{k} \frac{m}{m - i + 1}$
$var (W_{k}) = \sum_{i = 1}^{k} \frac{(i - 1) m}{(m - i + 1)^{2}}$

Details:

These results follow from [6] and standard results for the geometric distribution, since $E (W_{k}) = \sum_{i = 1}^{k} E (Z_{i})$ and $var (W_{k}) = \sum_{i = 1}^{k} var (Z_{i})$ .

In the coupon collector experiment, vary the parameters and note the shape and location of the mean $\pm$ standard deviation bar. For selected values of the parameters, run the experiment 1000 times and compare the sample mean and standard deviation to the distribution mean and standard deviation.

The probability generating function of $W_{k}$ is given by $E (t^{W_{k}}) = \prod_{i = 1}^{k} \frac{m - i + 1}{m - (i - 1) t}, | t | < \frac{m}{k - 1}$

Details:

This follows from [6] and standard results for the geometric distribution on $N_{+}$ , since $E (t^{W_{k}}) = \prod_{i = 1}^{k} E (t^{Z_{i}})$ .

Examples and Applications

Suppose that people are sampled at random until 40 distinct birthdays are obtained. Find each of the following:

The probability density function of the sample size.
The mean of the sample size.
The variance of the sample size.
The probability generating function of the sample size.

Details:

Let $W$ denote the sample size.

$P (W = n) = (\binom{364}{n}) \sum_{j = 0}^{30} (- 1)^{j} (\binom{39}{j}) {(\frac{39 - j}{365})}^{n - 1}$ for $n \in {40, 41, \dots}$
$E (W) = 42.3049$
$var (W) = 2.4878$
$E (t^{W}) = \prod_{i = 1}^{40} \frac{366 - i}{365 - (i - 1) t}$ for $| t | < \frac{365}{39}$

Suppose that a standard, fair die is thrown until all 6 scores have occurred. Find each of the following:

The probability density function of the number of throws.
The mean of the number of throws.
The variance of the number of throws.
The probability that at least 10 throws are required.

Details:

Let $W$ denote the number of throws.

$P (W = n) = \sum_{j = 0}^{5} (- 1)^{j} (\binom{5}{j}) {(\frac{5 - j}{6})}^{n - 1}$ for $n \in {6, 7, \dots}$
$E (W) = 14.7$
$var (W) = 38.99$
$P (W \geq 10) = \frac{1051}{1296} \approx 0.81096$

A box of a certain brand of cereal comes with a special toy. There are 10 different toys in all. A collector buys boxes of cereal until she has all 10 toys. Find each of the following:

The probability density function of the number boxes purchased.
The mean of the number of boxes purchased.
The variance of the number of boxes purchased.
The probability that no more than 15 boxes were purchased.

Details:

Let $W$ denote the number of boxes purchased.

$P (W = n) = \sum_{j = 0}^{9} (- 1)^{j} (\binom{9}{j}) {(\frac{9 - j}{10})}^{n - 1}$ , for $n \in {10, 11, \dots}$
$E (W) = 29.2897$
$var (W) = 125.6871$
$P (W \leq 15) = 0.04595$

7. The Coupon Collector Problem

Basic Theory

Definitions

The Probability Density Function

Decomposition as a Sum

Moments

Examples and Applications