How long until every type appears?
Think of randomized tests that independently sample one of cases. The question is how many draws are needed before every case has been sampled at least once. The answer describes coverage only if the sampling model is accurate.
Definition 8.1.1
(Collection time and waiting times)
Suppose each independent draw returns one of types uniformly, with replacement and equal probabilities on every draw. The collection time is the number of draws needed to see all types. After distinct types have appeared, for , let be the number of additional draws until the next new type, counting the successful draw. Then , and .
Theorem 8.1.2
(Expected collection time)
Under the model above, , where .
Proof
(Geometric waiting times)
After distinct types have appeared, the probability that the next draw is new is . Conditional on the history when the th distinct type appears, future draws are still independent uniform draws, so is geometric with success probability and mean . Consequently
The first equality counts every draw in exactly one waiting period. Linearity of expectation does not require the waiting times to be independent. Their expectations are finite because every success probability is positive.
Proof X-ray
Why each waiting time depends only on a count
The decomposition cuts the run at the moments a new type appears, so every draw belongs to exactly one . The one non-routine point is that, after the th new type, the chance of another new type depends only on how many types have been seen, not on which ones. This is exactly where equal probabilities are used, and it is why each is geometric. Independence of the draws gives a fresh start at each cut. Linearity of expectation then adds the means without any claim about dependence among the , and finiteness is automatic because every success probability is at least .
An expectation is not a deadline
A mean alone does not say that collection is complete by that time. We can bound the probability of a long wait.
Theorem 8.1.3
(Tail bound for the collection time)
For every integer ,
Consequently, for , every integer gives .
Proof
(Union bound over the missing types)
A particular type is missing after draws with probability . If , at least one type is missing, so the union bound over the types gives the first inequality. The second follows from . For the consequence, gives .
The missing-type events overlap, so the bound may be loose; the proof does not assume that they are independent. The result is a sufficient high-probability bound, not a promise for every run, and it concerns the same ideal independent uniform sampling model. At the union bound exceeds one, which is harmless but uninformative.
Worked examples
Worked example 8.1.4
(Two types)
For , the first draw always shows one type. Each later draw then finds the missing type with probability , so the mean is . Two draws can suffice, but they do not always do so: , since the second draw must differ from the first.
Worked example 8.1.5
(Three types)
For , the waiting times have means , and , so . The event requires three different draws, and of the equally likely sequences qualify, so .
Worked example 8.1.6
(A sufficient number of draws for ten types)
For and failure probability at most , take . The bound then gives . This is a sufficient number of draws, not necessarily the least integer that works.
Worked example 8.1.7
(An exact tail for two types)
For and , the failure probability is : all three draws must show the same type. The union bound is exact here because the two missing-type events cannot both occur after a nonempty sequence of draws.
Why the assumptions matter
If one type has probability zero, it is never collected. If types have unequal positive probabilities and draws are still independent, a particular type is missing with probability , and a valid union bound is . But the waiting probability depends on the set already seen, not just on its size, so the uniform formula need not apply. Correlated draws can invalidate even the product expression for a missing type.
Counterexample mode
Unequal probabilities change the mean
A tempting claim is that whatever the type probabilities. Take with probabilities and . If the first draw is the common type, which has probability , the missing type is the rare one and needs further draws on average. If the first draw is the rare type, the missing type is the common one and needs further draws on average. Hence
The step that breaks is that the success probability of the next draw now depends on which types have been seen, not only on how many. Equal probabilities are the hypothesis that restores .
Common mistakes
Common mistake
(Reading the mean as a deadline)
For the mean is , yet . In fact for every , so there is no finite number of draws that is certain to suffice. The mean says where the distribution is centered, not where it stops.
Common mistake
(Reading the union bound as the exact probability)
For and the union bound gives , but the exact value is . The three missing-type events overlap: a sequence of three equal draws makes two types missing at once, and the union bound counts it twice.
Exercises
Quick check
(For , compute and .)
Describe the event in terms of the first two draws.
Solution · Answer
The second draw differs from the first with probability , so . The event means all three draws match, which has probability .
Quick check
(For , compute .)
Count the sequences of three draws that show three different types.
Solution · Answer
All three draws must differ. Of the equally likely sequences, qualify, so the probability is .
Quick check
(How many draws suffice according to the bound for and failure probability at most ?)
Use and round up.
Solution · Answer
Take . This is a sufficient bound, not necessarily the least possible integer.
Quick check
(Why does not require independent missing-type events?)
Which general inequality is this?
Solution · Answer
It is the union bound, which holds for arbitrary events. Independence of the draws is used separately, to calculate each missing-type probability.