Math 365 Coupon Collector’s Problem
Submit your R script to tleise@amherst.edu by next Tuesday (a handwritten submission is also fine
for this lab).
The objective of this lab is to study a famous problem in probability, the coupon collector’s problem,
and its connection to Poisson processes.
1
Coupon Collector’s Problem: Geometric Distribution Approach
A young baseball fan wants to collect a complete set of 262 baseball cards. The baseball cards are
available in a completely random fashion, one per package of chewing gum, which the fan buys
twice a day. How long on average will it take the fan to get a complete set?
More generally, we can ask how many coupons do we expect to buy before obtaining a complete
collection of N distinct coupons? For example, if the set of coupons for N = 4 is represented by
{a, b, c, d}, then a possible sequence of coupons bought on each day could be a, a, d, b, d, a, d, b, c, so
that we had to buy 9 coupons to obtain a complete set of the 4 distinct coupons.
Let X be the number of coupons bought in order to collect all N distinct coupons, and let Xk
be how many more coupons we bought to obtain a new coupon once our collection contains k − 1
distinct coupons (the total number of coupons bought may get quite large, with many repeats of
the same coupons). Clearly X1 = 1. On each draw, the probability of collecting a new coupon,
given that we already have k − 1 different coupons, is pk = (N − (k − 1))/N . That is, Xk follows
N
a geometric distribution and E(Xk ) = p1k = N −k+1
. Note that this means when we’ve collected
N − 1 different coupons, we expect to still have to buy N more coupons before getting that last
coupon needed to complete the full collection! The total expected number of coupons we must buy
to complete the collection is
N
E(X) = E(X1 ) + · · · + E(XN ) = 1 +
X1
N
N
+ ··· +
+N =N
.
N −1
2
n
(1)
n=1
Exercise 1 According to this analysis, how many packages of gum should the fan expect to buy to
complete her collection of 262 distinct baseball cards? How many days will this take on average?
Exercise 2 Modify equation (1) to calculate the expected number of days to collect a full set,
given that the collector buys m coupons per day.
Exercise 3 Run simulations of the coupon collector problem to generate the distribution of the
random variable X. Compare the sample mean from the simulation with the theoretical mean (1).
# coupon collector simulation
nbought <- function(N) {
coupons <- matrix(0,1,N) # initially have no coupons
for (k in 1:100000) { # collect until complete collection x <- sample.int(N, 1, replace = TRUE)
coupons[x] <- 1 # mark that coupon type as collected
ifelse(sum(coupons)==N,return(k),-1)
} }
N <- 7 # set to desired number of different coupons
y <- sapply(matrix(N,10000,1),nbought)
hist(y,main=paste("Coupon collector, mean=",mean(y)), breaks=30)
2
Coupon Collector’s Problem: Poisson Process Approach
Now suppose there are N distinct coupons and we buy at a rate of m coupons/day (one at a time,
chosen randomly). Let T be the waiting time for obtaining a complete set of coupons. We can
model waiting for a particular coupon type to be collected as a Poisson process with rate parameter
λ = m/N , so we have N independent Poisson processes to model the waiting time for collecting
the N different coupons.
Exercise 4 What is the probability that we have to wait no longer than t days to collect a particular
coupon?
Exercise 5 Given that each coupon process is independent of the others, what is F (t) = P{T ≤ t}?
Exercise 6 We can calculate the expected value of T by integrating t times the density function
f (t) = F 0 (t):
Z ∞
Z ∞
E(T ) =
tf (t) dt =
(1 − F (t)) dt.
0
0
The 2nd formula is obtained using integration by parts. Use the substitution u = 1 − e−mt/N on
the 2nd formula and the geometric sum formula
N
−1
X
1 − uN
=
uk
1−u
k=0
to evaluate this integral. Compare to the formula in Exercise 2.
Math 365 Coupon Collector’s Problem
of 2
Report
Tell us what’s wrong with it:
Thanks, got it!
We will moderate it soon!
Free up your schedule!
Our EduBirdie Experts Are Here for You 24/7! Just fill out a form and let us know how we can assist you.
Take 5 seconds to unlock
Enter your email below and get instant access to your document