The one that hardly ever comes up

The collector’s answer is 14.7 draws for six kinds, it is exact, and it comes from cutting the wait into six stages and adding. That decomposition rests on something the essay states and then leaves: the six kinds are equally likely.

Drop that and almost everything goes.

Two and a half times as long, from an unevenness most people would call moderate. And the six stages that produced 14.7 are no longer available, for a reason worth being precise about.

Why the stages stop working #

The equal case decomposes because a stage’s rate depends only on how many kinds are missing. With four of six seen, a draw is useful with probability $2/6$, whichever two are missing, so the wait in that stage is $6/2$ and the total is $6(1 + \tfrac12 + \cdots + \tfrac16)$.

With unequal chances that sentence is false at its first comma. With four of six seen, the chance a draw is useful is the sum of the two missing kinds’ probabilities — which depends on which two are missing, and that depends on how the first four arrived. So the process is still a walk that only ever stays put or moves forward, and the state how many have been seen is no longer enough to describe it.

Linearity of expectation is not what failed. Linearity holds regardless; the wait is still the sum of the stage waits and the expectation of the sum is still the sum of the expectations. What failed is that the stage waits are no longer geometric with a known rate, so there is nothing to put in the sum.

The repair is to decompose along a different axis, and the one that works is over kinds rather than over stages.

The alternating sum #

Write $T$ for the wait and $T_i$ for the first time kind $i$ appears. Then $T = \max_i T_i$, and a maximum is not a sum — which is where linearity stops helping and inclusion–exclusion starts.

For a maximum of non-negative quantities,

$$E\!\left[\max_i T_i\right] \;=\; \sum_{\emptyset \neq S} (-1)^{|S|+1} \, E\!\left[\min_{i \in S} T_i\right],$$

and the minima are easy: the first time any kind in $S$ appears is a geometric wait at rate $p_S = \sum_{i\in S} p_i$, so $E[\min] = 1/p_S$. That gives

$$E[T] \;=\; \sum_{\emptyset \neq S \subseteq \{1,\dots,m\}} \frac{(-1)^{|S|+1}}{\sum_{i \in S} p_i},$$

an exact formula with $2^m - 1$ terms. For six kinds that is sixty-three; for fifty it is a thousand million million, which is the formula’s whole problem.

And it is numerically appalling long before it is large. The terms alternate in sign and the largest of them can be many times the answer, so the sum is a cancellation of big numbers into a small one — the arithmetic hazard the quadratic formula runs into with two terms instead of sixty-three, and the repair is the same in kind: find an expression that does not subtract.

The same number, as an integral #

There is a second exact expression with none of those problems, and the two agreeing is what makes either trustworthy.

$$E[T] \;=\; \int_0^\infty \left(1 - \prod_{i=1}^m \left(1 - e^{-p_i t}\right)\right) dt.$$

The derivation takes two steps. First, for a non-negative quantity, the expectation is the integral of the probability of exceeding each value — the area under the survival curve. Second, the wait is Poissonised: imagine the draws arriving at the times of a Poisson process of rate one, so that kind $i$ arrives at the times of an independent process of rate $p_i$. Then the chance kind $i$ has not appeared by time $t$ is $e^{-p_i t}$, the kinds are independent, and the probability everything has appeared is the product.

Poissonisation is the move worth carrying. Drawing one at a time makes the kinds dependent — if this draw was a red, it was not a blue — and putting the draws at the times of a Poisson process makes them exactly independent, which is what lets the product be written down. The expected number of draws and the expected time come out the same because the process has rate one.

Every figure here computes both expressions and requires them to agree. That is not decoration: an alternating sum with a sign in the wrong place produces a plausible number and no symptom at all.

What the answer is mostly made of #

That figure is the practical content. The wait for the rarest kind alone is a lower bound on the wait for everything, because everything includes it — and when one kind is much rarer than the rest, that bound is nearly the answer.

Which gives a rule of thumb worth more than the formula: the wait is about $1/p_{\min}$ plus a correction of the order of the wait for the rest. The formula’s sixty-three terms are computing a correction to a number visible in one bar.

It also says which measurements matter. Estimating a collector’s wait requires knowing the rarest kind’s chance accurately and the others’ hardly at all — and the rarest kind’s chance is exactly the one that is hardest to estimate, since it is the one least often observed.

What the unevenness costs, as one number #

There is a compact way to say how much an uneven collection costs, and it is worth having because it turns the four figures into a single reading.

For a fixed number of kinds, the wait is at least $m H_m$ — the equal-case answer — and the excess over it is governed by how spread the probabilities are. A useful summary of that spread is the effective number of kinds, $1/\sum_i p_i^2$, which is $m$ when the kinds are equal and falls toward one as the distribution concentrates.

The five collections drawn here have effective numbers of $6.00$, $5.14$, $3.46$, $5.19$ and $4.02$, against an actual count of six in every case. Their waits are $14.70$, $20.22$, $35.46$, $52.52$ and $23.97$ — and the two orderings do not match at all. The collection with the second highest effective number has by far the longest wait, and the one with the lowest effective number is only third. The effective number does not predict the wait, because it measures how the mass is spread and the wait is set by the thinnest part of the tail, which by definition carries almost none of it. The five kinds’ rarest-alone waits are $6.0$, $12.0$, $22.0$, $51.0$ and $14.7$, and those are in the right order.

That mismatch is the most useful thing on this page for anybody who has a distribution in hand. Every standard summary of a distribution’s unevenness — variance, entropy, effective count, Gini — weights the common outcomes heavily, and none of them sees the rare ones sharply enough to say what this question needs. The statistic that answers it is $\min_i p_i$, and it is the statistic nobody reports.

Equal is the best case #

All four figures show the same relation and it is a theorem: for a fixed number of kinds, the expected wait is smallest when the kinds are equally likely, and any unevenness makes it larger.

The reason is convexity. In the integral form the quantity being integrated is $1 - \prod(1 - e^{-p_i t})$, and for fixed $t$ that is a Schur-convex function of the probability vector — it increases whenever the distribution is made more uneven in the majorisation sense. Integrating preserves that, so the whole wait does too.

It is worth separating the two things people mean by harder. The equal case is the best case, so no distribution is easier; and it is also, in the usual sense, not the typical case, since a real collection of anything is nearly never flat. So the textbook answer is a floor rather than an estimate, and the collections people actually meet are on the wrong side of it, often by a large factor.

The asymptotic that replaces the harmonic sum #

For equal chances the answer is $n H_n \approx n(\ln n + \gamma)$, and the whole shape of the result is in that logarithm. There is a corresponding statement in the unequal case and it is worth having, because it explains what the logarithm was doing.

For $m$ kinds with probabilities $p_i$, the wait satisfies

$$\max_i \frac{1}{p_i} \;\le\; E[T] \;\le\; \frac{1}{p_{\min}}\left(\ln m + 1\right),$$

the lower bound being the rarest kind alone and the upper bound coming from a union bound of exactly the kind the equal case’s tail estimate uses, which needs no independence and is loose only when several of the events are likely at once. The two differ by a logarithm of the number of kinds — so the rarest kind’s wait determines the answer to within a logarithmic factor, always, whatever the rest of the distribution does.

That is a much stronger statement than the equal case’s, and it is the reason the equal case is the one with the interesting arithmetic. When every kind is equally rare, the maximum of $m$ waits is genuinely $\ln m$ times a single one — the logarithm is the cost of taking a maximum over $m$ comparable things — which is the same logarithm the harmonic series is, arriving as a maximum rather than as a sum. When one kind is much rarer than the others, the maximum is just that one, and the logarithm has nothing to be about.

The same alternating sum, met before #

The inclusion–exclusion expression is worth setting beside the one place such a sum has already appeared, because the two are the same manoeuvre applied to opposite quantities and the comparison says what such a sum is for.

Counting the permutations that leave nothing where it was is an alternating sum over subsets of the positions: the ones fixing at least this set, minus the ones fixing at least that, and so on. It converges to $n!/e$, and $e$ arrives because the sum is the exponential series truncated.

Here the same structure appears because the event everything has been seen is an intersection, and the complement of an intersection is a union — which is what inclusion–exclusion is for. Both sums are computing the size of a union from the sizes of intersections, and in both the intersections are the easy quantities.

What is different is the arithmetic. The hat sum’s terms fall like $1/k!$ and it converges within six terms; this one’s terms are $1/p_S$ over every subset, they do not fall, and the whole thing is a cancellation. So the same identity is a computation in one case and a definition in the other, and which it is depends entirely on whether the intersections shrink.

That is worth keeping as a test. An inclusion–exclusion formula is a good formula when the terms decay and a bad one when they do not, and nothing in the identity itself says which case one is in.

Where it is used, and where the assumption bites #

Vaccination and coverage surveys. Reaching every subgroup of a population with a programme is a collector’s problem in which the groups are unequal by construction, and the last per cent costs a disproportionate share of the effort for exactly the reason above: the wait is set by the least-reached group, not by the average.

Software testing and fuzzing. Covering every branch of a program by random inputs is a collector’s problem, and the branches are wildly unequal — some are taken by nearly every input and a few by almost none. The equal-chance estimate of how long a fuzzing run needs is not conservative; it is optimistic by whatever factor the rarest branch is rarer, which can be several orders of magnitude.

Species estimation. Counting how many species are in an ecosystem from a sample is this problem run backwards, and the standard estimators — Chao’s, and the Good–Turing frequency estimate — exist precisely because the unseen kinds are the rare ones and the sample says almost nothing about them. Good and Turing’s work on it at Bletchley was about which letter sequences had not yet been seen, which is the same question, and the same shortfall a sample cannot see from the other direction.

Cache and database sampling. How long before every distinct key has been touched, in a workload whose key frequencies follow a power law, is this question with the $1/k$ distribution of the third figure — and the answer is governed by the tail, which is the part of a workload that is hardest to measure.

In all three the pattern is the same: the quantity that decides the answer is the one the data says least about.

Two kinds is small enough to do by hand #

The general formula is sixty-three terms and the whole mechanism is visible at two, so it is worth running the smallest case completely.

Two kinds, with chances $p$ and $1-p$. Inclusion–exclusion has three terms:

$$E[T] \;=\; \frac1p + \frac1{1-p} - \frac11 \;=\; \frac{1}{p(1-p)} - 1.$$

At $p = \tfrac12$ that is $3$, which is the equal-case answer $2H_2 = 2(1 + \tfrac12)$. At $p = \tfrac1{10}$ it is $\tfrac{100}{9} - 1 = 10.1$, against a rarest-kind bound of $10$ — so at two kinds the rare one is almost exactly the answer, with a correction of $0.1$.

The formula’s shape is already the general one. It blows up like $1/p$ as the rare kind gets rarer, it is minimised at $p = \tfrac12$ by a convexity visible in the denominator, and the subtraction of the last term is the cancellation that gets worse with more kinds. Everything this essay says about six kinds is checkable here in a line.

It also shows what the Poissonised form does. The integral expression at two kinds is $\int_0^\infty (1 - (1-e^{-pt})(1-e^{-(1-p)t}))\,dt$, which expands to $1/p + 1/(1-p) - 1$ on integrating term by term — the same three terms, arrived at without any inclusion–exclusion, because the product’s expansion is the alternating sum. The two expressions are one expression, and which is usable depends only on whether the product is expanded before or after integrating.

The bars are not the answer and do not add to it #

Every bar is $1/p_i$, and the total printed above them is not their sum. The bars are the waits for each kind separately and the answer is the expected maximum, which is smaller than the sum and larger than any one bar. A reader adding the bars gets a number about three times too big, and the figure gives no visual account of where the answer falls between the two.

Nothing here draws a distribution of the wait. The wait has a distribution with a long right tail, as in the equal case, and a single number describes it badly. The figure shows one number per collection and says nothing about how much a particular collector’s experience varies around it.

And the six-kind restriction is severe. Sixty-three subsets is what an alternating sum can be run over; for fifty kinds the sum is unusable and the integral is the only route, and the figures are drawn at a size where the wrong method still works. The interesting sizes are the ones where it does not.

Still open here: estimating what was not observed #

The unequal collector has an exact answer in two forms and a sharp bound. What it does not have is a way to compute the answer from a sample rather than from the probabilities, and that is the version every application needs.

Given a run of draws, estimating the total wait requires estimating the rarest kinds’ probabilities, and the rarest kinds are precisely the ones that have appeared once or not at all. Good–Turing’s estimate — that the total probability of unseen kinds is about the fraction of the sample seen exactly once — is the standard tool and is a genuinely surprising statement; how accurate it is, and what happens when the distribution has a heavy tail, remains an active question.

The other direction is one the equal case answered and this one has not. The equal collector’s wait has a limiting distribution — the Gumbel, since it is a maximum — and for unequal chances the limit depends on the shape of the tail, with several regimes and no single answer.

When a decomposition stops being available #

The habit is about noticing which assumption a method was using.

Cutting the collector’s wait into stages is presented as an application of linearity, and linearity is not what it needs — linearity holds always. What it needs is that the state how many are missing determines the rate, and that is a property of equal chances rather than of expectation.

The repair decomposed along a different axis and paid for it: sixty-three terms, alternating, instead of six. That is the usual price. A decomposition that works is a decomposition whose pieces do not depend on each other in the way that matters, and when the obvious one stops working, the question is which quantity is now carrying the dependence — here, which kinds are missing rather than how many.