Seyed Masoud Hosseini · Overview · Study log · Weekly summaries · Ideas · Search · Transcript · RSS feed

Probability · Lecture 23 of 76 · 7:15

The Coupon Collector Problem

Study guide

What this lecture covers

This recitation problem solves the classic coupon collector's problem: given a random draw each round from K equally likely categories (here, six possible grades), how many draws are expected before every category has appeared at least once? It builds on linearity of expectation and the geometric distribution from earlier in the course.

You'll see the standard trick of splitting a hard-to-analyze stopping time into a sum of simpler geometric random variables, then using linearity of expectation to add up their individual expectations without worrying about dependence between them.

Key ideas

Stopping time decomposition: define Y_i as the number of draws until the i-th new category appears, and X_i = Y_(i+1) - Y_i as the number of draws between consecutive new categories.
Telescoping sum: Y_K (the total time to see all K categories) equals the sum of the X_i differences, so E[Y_K] = E[sum of X_i].
Geometric distribution per stage: once i categories have been seen, each further draw succeeds (reveals a new category) with probability (K-i)/K, so X_i is geometric with that success parameter.
Expectation of a geometric variable: for success probability p, the expected number of trials to succeed is 1/p.
Linearity of expectation: E[sum of X_i] = sum of E[X_i], which holds even though the X_i are not independent of each other in a simple way.
Harmonic sum result: for K=6, the expected number of draws works out to 6 times a sum of reciprocals, giving approximately 14.7.
General scaling law: for general K, E[Y_K] = K * sum(1/i for i=1..K-1), which grows roughly like K * ln(K).

Before you watch

Know the geometric distribution and its expectation formula.
Be comfortable with linearity of expectation, including that it applies to dependent random variables.
This problem assumes you've seen discrete random variables and expectation from earlier lectures in the course.

Check your understanding

Why is X_i geometric with parameter (K-i)/K rather than a fixed parameter for every i?
Why does linearity of expectation apply here even though the X_i are not independent?
How does the expected time change if K doubles, based on the K * ln(K) scaling law?
What would change in this analysis if the categories were not equally likely?

Vocabulary

recitation (noun): A class session where students practice solving problems, often led by a teaching assistant.
This recitation works through the coupon collector problem step by step.
coupon collector problem (phrase): A classic probability question about how many random draws are needed to see every possible category at least once.
The coupon collector problem asks how long it takes to see all six grades.
draw (noun): One random pick or outcome from a set of possibilities.
Each draw gives one of six equally likely grades.
category (noun): A group or type that an outcome can belong to.
There are six categories, one for each grade.
stopping time (noun): A random point in a process where you decide to stop, based only on what has happened so far.
The stopping time here is the draw on which the last new category appears.
decomposition (noun): The act of breaking something complicated into smaller, simpler parts.
The decomposition splits the total wait into separate stages.
telescoping sum (noun): A sum where middle terms cancel out, leaving only the first and last parts.
The telescoping sum shows that the differences add up to the total time.
geometric distribution (noun): The probability pattern for the number of tries needed before the first success.
Each stage's waiting time follows a geometric distribution.
expectation (noun): The long-run average value of a random outcome.
We want the expectation of the total number of draws.
linearity of expectation (phrase): The rule that the average of a sum of random amounts equals the sum of their averages.
Linearity of expectation lets us add the stage times without worrying about dependence.
dependence (noun): A situation where one random outcome affects or is linked to another.
The stages show dependence, but linearity of expectation still works.
harmonic sum (noun): The sum of the reciprocals of whole numbers, like 1 + 1/2 + 1/3 and so on.
The final answer involves a harmonic sum of six terms.
reciprocal (noun): The result of dividing 1 by a number.
Each term in the sum is the reciprocal of a whole number.
scaling law (phrase): A general rule for how a quantity grows as another quantity grows.
The scaling law shows the expected time grows like K times the log of K.
trial (noun): One attempt or repetition of a random experiment.
Each trial in the geometric process is one more draw.
success probability (phrase): The chance that a single trial gives the wanted result.
The success probability drops as more categories have already been seen.
outcome (noun): The specific result of a random process.
Each draw's outcome is one of six grades.
simplify (verb): To make something easier to understand or solve.
Splitting the stopping time into stages simplifies the calculation.
distinct (adjective): Separate and different from each other.
The problem asks for the time to collect all K distinct coupons.
roughly (adverb): Approximately, not exactly.
For K=6, the expected number of draws is roughly 14.7.
grow (verb): To increase in size or amount.
The expected number of draws grows as K increases.
consecutive (adjective): Following one after another without a gap.
X_i counts the draws between consecutive new categories.
reveal (verb): To make something previously unseen become visible or known.
A successful draw reveals a new category.
classic (adjective): Well known and often used as a standard example.
The coupon collector problem is a classic result in probability.
split (verb): To divide something into separate parts.
The trick splits a hard problem into a sum of simpler pieces.
equally likely (phrase): Having exactly the same chance of happening as every other option.
The six grades are assumed to be equally likely.

From the YouTube description

MIT 6.041SC Probabilistic Systems Analysis and Applied Probability, Fall 2013
View the complete course: http://ocw.mit.edu/6-041SCF13
Instructor: Kuang Xu

License: Creative Commons BY-NC-SA
More information at http://ocw.mit.edu/terms
More courses at http://ocw.mit.edu

← Joint Probability Mass Function (PMF) Drill 1 · Lecture 7: Discrete Random Variables III →