One experiment, several questions
Imagine that each of independently selected people has one of possible birthdays, each equally likely. We ignore leap days and seasonal variation. The resulting sequence is a model, not a claim that real birthdays satisfy these assumptions. We might ask whether two people share a birthday, how many different birthdays occur, or how many people are needed before every birthday has appeared. These questions use the same mechanism but require different random variables.
More generally, let be independent and uniform on , where is a positive integer. The first draws form an ordered sequence; each of the sequences has probability . Write for the number of distinct categories among the first draws and for the first draw by which all categories have appeared. A category can be repeated, and order matters when counting the underlying sequences, even though ignores order.
The first collision
Theorem 31.1.1
(No repeated category)
For ,
for this probability is zero. The empty product at is one. The probability of at least one collision is the complement.
Proof
(Count or condition sequentially)
There are choices for the first draw, for the second if it differs from the first, and so on. Multiplication counts the ordered sequences with no repetition. Dividing by the equally likely sequences proves the formula. Equivalently, after distinct categories have appeared, the next draw avoids them with probability . If , the pigeonhole principle makes a collision certain.
The complement is useful because a collision can happen in many overlapping ways: one pair may match, or several pairs may match. Adding pair-match probabilities directly double-counts outcomes with more than one matching pair. For much smaller than , the logarithm of the no-collision probability is approximately , since for small . This is an approximation, not an exact formula; it explains why a substantial collision chance can arise when is of order , well before reaches .
Worked example 31.1.2
(Twenty-three people and 365 days)
Take and . Multiplying the factors , , gives
so the probability of at least one shared birthday is about . The approximation gives , close to the exact value because is small compared with . In this model, people already give a better-than-even chance of a collision, although is far below .
How many categories are represented?
Let be one if category appears among the first draws, and zero otherwise. Then , and at , by definition.
Theorem 31.1.3
(Mean and variance of the number of occupied categories)
For , put and, when , . Then
For , for , so its variance is zero.
Proof
(Indicators and their covariances)
Category is absent from all independent draws with probability , so . Linearity of expectation does not require the indicators to be independent, and summing over gives .
For and distinct , both categories are absent with probability . By inclusion and exclusion, , hence . Expanding the variance of the sum into variances and covariances proves the formula.
The covariance term matters: the indicators share the same fixed number of draws. It is nonpositive here, because implies .
Worked example 31.1.4
(Three draws from three categories)
There are equally likely sequences. All three categories appear in sequences, so . Exactly one appears in three sequences, hence ; the remaining probability is . Therefore
and . The expectation formula gives the same answer: .
Counterexample mode
Equal marginal probabilities do not give the occupancy formula
Suppose instead that is a single uniform draw from , with . Both draws are individually uniform, but they are dependent. A collision occurs with probability one, rather than , and almost surely. The earlier formulas require independence as well as uniformity.
Waiting until every category appears
Define as the smallest with . Once distinct categories have been collected, the probability that the next independent draw is new is . Let count the draws from that moment through the first new category, including the successful draw. Conditional on the history up to that moment, is geometric with success probability , so its conditional and unconditional mean is . Every category is eventually seen almost surely: for any fixed category the chance it is still missing after draws is , and there are finitely many categories.
Theorem 31.1.5
(Coupon collector expectation)
Under the independent uniform model,
Proof
(Separate the waiting stages)
The waiting stages partition the draws through the final new category, so holds pathwise. The mean of a geometric random variable on with success probability is , so . By linearity,
after substituting .
Proof X-ray
Why the last categories dominate
The key move is to measure time from one new category to the next, instead of tracking the whole set of collected categories. Within stage only one number matters, the fraction of categories still missing, and the independent uniform draws make that stage a geometric wait whatever happened before. This is the one place where the model is used.
Linearity then closes the argument; independence between the is true here but is not needed for the expectation. The harmonic sum shows where the time is spent: the first half of the categories costs at most draws each on average, while the last missing category alone costs . This is why the total exceeds for and grows like .
For , the three stage means are , , and , so . This does not say that collection always finishes on draw or : is random and can be arbitrarily large.
Worked example 31.1.6
(Collecting all six faces of a die)
For a fair die, and the stage means are . Their sum is
The last stage alone contributes , and the last two contribute , more than half of the total. The degenerate case is consistent with the formula: , and indeed because the first draw already shows the only category.
Common mistakes
Common mistake
(Adding the pair-match probabilities)
For people and days there are pairs, each matching with probability . Their sum, , is the expected number of matching pairs, not the probability of a collision, which is about . The sum counts an outcome with several matching pairs several times. It is an upper bound for the collision probability, and the complement formula gives the exact value.
Common mistake
(Treating the occupancy indicators as independent)
With , independence would give . The covariance term is not negligible, and the correct variance is , about half as large.
Practice and solutions
Quick check
(Four independent uniform draws are made from five categories. Find the probability of a collision and the expected number of distinct categories.)
Use the no-collision product and the formula for .
Solution · Answer
The no-collision probability is , so the collision probability is . The expected count is .
Quick check
(With , find the distribution and mean of the additional number of draws needed after the first category has appeared.)
Each later draw finds the other category with probability .
Solution · Answer
Each subsequent draw independently finds the other category with probability . For , the probability that the wait is is ; its mean is . The first draw has already occurred and is excluded from this wait, so .
Quick check
(A colleague calculates as because the second draw is new with probability . Explain the error and give the correct value.)
Ask what the first draw contributes.
Solution · Answer
The first draw contributes one new category with certainty, not with probability . The second contributes a new category with probability , so . The indicator formula gives the same result: .