In this section, our random experiment is to sample repeatedly, with replacement, from the population . This generates a sequence of independent random variables, each uniformly distributed on :
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 types. Thus, in this setting, is the coupon type received on the purchase.
Let denote the number of distinct values in the first selections, for . 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 distinct sample values, for . Thus, let
In terms of the coupon collector, this random variable gives the number of products required to get distinct coupon types. Note that the set of possible values of is . We will be particularly interested in , 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.
Now let's find the distribution of . The results of the previous section will be very helpful
Argue that if and only if and .
Use Exercise 2 and a conditional probability argument to show that
Use the result of the last exercise and the distribution of from the last section to show that
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 with an update frequency of 10 and note the apparent convergence of the relative frequency function to the probability density function.
An alternate approach to the distribution of the sample size needed to get distinct values is via a recursion formula.
Let Use a conditional probability argument to show that
We will now show that can be decomposed as a sum of 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 , let denote the number of additional samples needed to go from distinct values to distinct values.
Argue that
Exercise 7 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 large and near .
Use the results of Exercise 7 to show that
In the coupon collector experiment, vary the parameters and note the shape and location of the mean/standard deviation bar. For selected values of the parameters, run the experiment 1000 times with an update frequency of 10 and note the apparent convergence of the sample mean and standard deviation to the distribution mean and standard deviation.
Use the Result of Exercise 7 to show that the probability generating function of is
Suppose that people are sampled at random until 40 distinct birthdays are obtained.
Suppose that a standard, fair die is thrown until all 6 scores have occurred.
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.