How long until every one turns up

Six kinds of thing, equally likely, drawn one at a time with repetition allowed. How many draws before all six have been seen?

Six is the obvious guess and it is far too small — the last kind alone takes six draws on average. Thirty-six is the guess of somebody who has noticed that and overcorrected. The answer is 14.7, it is exact rather than simulated, and it comes apart into six separate waits that can be read off a picture.

The tall bar on the right is where all the intuition goes wrong. Five of the six waits are short — the sixth is as long as the other five put together, nearly.

Cutting the wait into pieces #

The whole method is one decision, taken before any arithmetic: instead of asking how long the collection takes, ask how long each new kind takes after the last one.

That splits the process into stages. In the stage where i kinds have been seen, a draw is useful when it produces one of the n − i unseen kinds, which happens with probability (n − i)/n. Draws happen until a useful one arrives, and then the next stage begins.

The stages are the bars. The total wait is their sum, and the fact that the sum of the waits is the wait for the sum is not obvious — it is linearity of expectation, which holds whether or not the stages are independent, and which is the single most useful fact in elementary probability precisely because it needs no independence to apply.

Here the stages happen to be independent as well, but the argument does not use that, and it is worth knowing which of the two is doing the work. Plenty of problems have stages that are hopelessly entangled and still submit to the same decomposition.

What one stage costs #

A stage ends on the first success in a run of independent attempts each succeeding with probability p. The expected number of attempts is 1/p, and this is the one piece of the argument that a picture cannot supply.

The cleanest derivation is self-referential and takes one line. Let T be the expected wait. The first attempt costs 1 and succeeds with probability p; if it fails, which happens with probability 1 − p, the situation is exactly what it was and a further T is expected. So T = 1 + (1 − p)T, and rearranging gives T = 1/p.

That is a recurrence with one unknown, and it is valid because the process is memoryless — the attempts do not know how many have already failed. Every wait on this page is of that form, so the stage where i kinds have been seen costs n/(n − i) draws.

For six kinds those are 6/6, 6/5, 6/4, 6/3, 6/2 and 6/1: one, then 1.2, then 1.5, then 2, then 3, then 6.

The smallest case, checked by hand #

Three kinds is the smallest case where anything happens, and it is small enough to be checked from the other end.

Let E be the expected number of further draws with nothing seen, F with one kind seen and G with two. From the state with two seen, each draw is useful with probability a third, so G = 3. From the state with one seen, a draw is useful with probability two thirds; the recurrence F = 1 + (1/3)F + (2/3)G gives F = 4.5. And the first draw is always useful, so E = 1 + F = 5.5.

That derivation never mentions harmonic numbers, never sums a series, and never uses linearity. It sets up three equations in three unknowns and solves them from the top down. It gives 5.5, which is what 3(1/3 + 1/2 + 1) gives.

The two routes are genuinely different and the figure runs both: it solves the chain backwards, as just done, and separately forms the harmonic sum, and asserts that the two agree to within a billionth. A discrepancy would mean one of them was wrong, and the pleasant part is that neither would be obviously the culprit.

The sum, and the series it turns out to be #

Add them. The total is n times the sum of the reciprocals 1/n + … + 1/2 + 1/1, which is n times the nth harmonic number.

The harmonic series already has an essay on this site, and it was written about a different question — whether the sum has a limit, which it does not. Here the same sum arrives as a cost, and its slow divergence becomes the statement that collecting everything is only slightly harder than collecting most of it.

The harmonic number is close to the natural logarithm plus a constant — the Euler–Mascheroni constant, 0.5772 — which turns the exact answer into a usable one: collecting n kinds takes about n(ln n + 0.5772) draws. For six that estimate gives 14.70, agreeing with the exact answer to four figures. For a hundred it gives 518.7 against an exact 518.7.

The reason the growth is logarithmic is Oresme’s fourteenth-century argument, and it is worth having in this context because it explains the shape of the collector’s answer. Doubling the number of kinds adds a fixed amount to the harmonic number, so it multiplies the total wait by a bit more than two. Collecting a hundred kinds costs 519 draws; collecting two hundred costs 1,176 — slightly more than double, never anything like four times.

An answer that is exact, and why that is unusual #

Almost everything in this essay is an exact rational number. The wait for six kinds is 6(1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6), which is 147/10 exactly, and 14.70 is that number written out rather than a rounding of something messier.

That is worth noticing because it is rare. Most questions of this kind — how long until a random walk returns, how likely a particular pattern is to appear — have answers that are either irrational or have no closed form at all. What makes this one exact is that the process was cut at exactly the places where the probabilities are constant, and a constant probability gives a rational expected wait.

The exactness also makes the approximation honest. Saying the answer is “about n ln n” is a statement about an exactly known quantity, so the error in the approximation can be computed rather than estimated: it is nγ plus a term that shrinks like a half, and the whole business is under control. Compare that with an approximation to a quantity nobody can write down, where the error is itself a research problem.

This is the same distinction the rearranged series turns on. An exact object can be approximated safely; an object known only through its approximations cannot be reasoned about the same way.

The last one is the expensive one #

The bars are a picture of an uneven cost, and the unevenness is extreme. Waiting for the final kind costs n draws, which for twelve is twelve — nearly a third of the total. The last two together cost eighteen of the 37.24. The first six cost 7.9 between them.

This is the practical content of the result and it is the part that matches experience. Getting most of a collection is quick and getting the last item is interminable, not because of any conspiracy but because at that point only one draw in n is useful.

It also explains why the total is n log n rather than n. If every stage cost about the same, the total would be proportional to the number of kinds. The stages do not cost about the same; the costs run from 1 to n, and their sum is the harmonic sum.

Why the sum is allowed to be run backwards #

The two computations in the last section are worth separating, because one of them scales and the other does not.

Solving the chain from the top down asks, at each state, what the expected remaining cost is, and expresses it in terms of the state after. That is a system of n equations, each involving two unknowns, and it can be unrolled in n steps. It works for any chain whose moves only ever go forward or stay put, and it does not care whether the probabilities are equal.

Cutting the wait into stages and adding is different: it treats the total as a sum of separate random quantities, each with its own expectation, and adds those. The justification is linearity, and the reason it is worth having is that it survives situations the equation-solving does not — when the stages can be identified but the chain cannot be written down.

Both are correct here and they agree, which is the point of doing both. The site’s habit of insisting on two independent computations is at its most useful exactly when both are short: two short derivations that agree is much stronger evidence than one long one, because short derivations fail in different ways than long ones do.

What the expectation does not say #

An expectation is one number about a distribution and it can be badly unrepresentative. Here it is fairly representative but not entirely: the collector’s wait has a long right tail, because the last stage is a geometric wait that occasionally goes on and on.

The variance can be computed the same way the mean was, by adding up the stages, and it comes out at about n²π²/6 — which means the standard deviation is about 1.28n, comparable to the whole last stage. For six kinds the expected wait is 14.7 with a spread of about 7.7. Anyone drawing six kinds and finishing in nine draws, or in thirty, has seen nothing unusual.

The appearance of π²/6 there is another of this site’s uninvited constants, arriving through the sum of reciprocal squares in exactly the way e arrived in the hat problem through the reciprocal factorials. The pattern is real: waits produce reciprocals, and sums of reciprocals are where the named constants live.

The other end of the same question #

Drawing from n kinds raises two natural questions and they have wildly different answers. How long until something repeats? About √n draws — which is why twenty-three people suffice for a shared birthday out of 365. How long until everything has appeared? About n log n draws — which for 365 kinds is a little over two thousand.

The gap between √n and n log n is enormous and it is the reason the two questions feel like they belong to different subjects. They do not. Both are questions about how many draws it takes before a particular pattern of coverage appears, and both are answered by cutting the process into stages and adding up the waits.

What the picture cannot show #

The bars are expectations and nothing else. No figure here draws a single run of the process, and a single run would look nothing like the bars — it would be a jagged thing with long flat stretches. Drawing one would be honest about the variability and dishonest about the answer, since one run says nothing.

The equal-likelihood assumption is invisible. Everything above assumes the n kinds are equally likely, and that assumption is doing an enormous amount of work. With unequal probabilities the answer is still a sum over stages, but the stages no longer have clean probabilities, the expression involves an alternating sum over every subset of the kinds, and the rare kind dominates everything. The wait for a collection in which one kind has probability a thousandth is at least a thousand draws whatever the others do.

Nothing here draws a distribution. The wait has one, and it is a genuinely interesting object — the chance of finishing in exactly k draws is an alternating sum of terms, and the whole distribution converges after rescaling to one of the standard extreme-value shapes rather than to a bell curve. A figure of that would be a different essay; the point worth carrying is that the sum of a handful of very unequal waits does not look like the sum of many equal ones, and the central limit theorem is not available.

And the drawing stops at sixteen kinds because the bars stop being legible, while the interesting regime is the one where n is large and the log matters. The figures show the mechanism at a size that fits on a page; the n log n behaviour is a statement about sizes no page holds.

Where the ladder goes next #

The decomposition used here — cut a process into stages, find the expected cost of each, add — is the standard method, and its power is that the stages may overlap, interfere and depend on one another without invalidating the sum. The rung above this one is where that freedom gets used: problems in which the stages are so entangled that no other method works, and linearity gets an answer anyway.

The other direction leads to the process rather than its total. The collector is a walk through states — nothing seen, one seen, two seen — that only ever stays put or moves forward one, which makes it the simplest interesting example of a rule that forgets where it came from. That essay takes the same machinery and asks a different question of it: not how long until the walk finishes, but where it spends its time when it never finishes at all.

There is a third route out, towards what happens when the draws are not independent or not equal. Sampling without replacement makes the whole question trivial — n draws, exactly — and the interesting cases lie between, where a draw makes a repeat slightly less likely without forbidding it. Those are the cases where the clean decomposition fails and something like the pigeonhole bound has to be used instead, giving an inequality where this essay had an equality.

And there is the constant. The gap between the harmonic number and the logarithm is 0.5772 and nobody knows whether it is rational. It is one of the few constants in ordinary use whose basic nature is an open question, and it arrived here as the difference between two things a collector might reasonably compute.