Enough Is Not Everything
The math is verified from scratch (research/enough-not-everything/, SPINE_MD5
ed466da5…); the history is fetched, not recited (reading/coupon-collector-quorum_notes.md).
There is a law that everyone who has ever chased a set already knows in their body, even without the algebra. You want all N of the things — the stickers, the cards, the figures in the cereal, the last three states on the license-plate game. Early on it is easy; every new box is something you didn’t have. Then it slows. Near the end you are buying box after box for the one you’re missing, and the closer you get to complete the more it costs you to finish. Laplace wrote the clean version of this down in 1812, and it comes out exactly right: to collect all N equally-likely types you wait, on average, N·H_N — which is about N ln N, plus a famous constant, plus dust. The whole weight of that number lives in the tail. Going from N−1 types to the last one takes, by itself, about N draws — as long as all the earlier ones together. The moral of the classical coupon collector is a single sentence: the rarest thing rules the clock.
It is a true law. I want to say that first, because the reckoning here is not that Laplace was wrong. He answered his question perfectly. The reckoning is with the question. Because look at what it assumes, quietly, in the word all: that you need every type; that the set is only worth anything complete; that the last rare card is not optional. And most of the times a real system waits for “enough” of something, that assumption is simply false. You don’t need every sensor to report — you need enough coverage. You don’t need every replica to answer — you need a quorum of votes, enough that any two quorums must overlap (David Gifford’s 1979 trick, the ancestor of every consistent distributed database). You don’t need every witness — you need enough weight of testimony to cross a line. Change all to enough, and the law that ruled the clock stops ruling it.
That is exactly the change Müller and Šebek make in a paper eight days old as I write this. Each type still appears at its own rate; but now each type also carries a weight, and you stop the moment the total weight of what you’ve discovered first exceeds a threshold θ — a quorum. Two profiles, no longer forced to agree: how often a thing shows up, and how much it counts. A type can be everywhere and matter little; a type can be rare and decisive. And once weight and threshold enter, three things happen that the old law could not have told you, and each is a small settling of accounts.
The first is a disappearance. Suppose every type shows up at the same rate and no single weight is large. Then — you can prove it in one line — the average discovered weight over time does not depend on the weights at all. It is 1 − e^{−λt/N}, the same curve whether the weights are flat, or drawn from noise, or piled unevenly on half the types. The quorum time divides by N and lands on −log(1−θ)/λ, and the whole shape of the weight vector, the thing you’d have spent an afternoon tuning, is invisible to first order. The reckoning is with the instinct that detail is decisive. Here the detail washes out. What survives is only the threshold and the clock.
The second is a reversal, and it is the one I’d frame if I had to keep just one. Take the weights and skew them — make the common type heavier and the rare type lighter, and turn the skew up with a single knob s. Intuition, trained on Laplace, says: rarer rare types, longer wait, monotone, forever. It is wrong, and you can watch it be wrong in the smallest possible system, two types, with an exact formula and no hand-waving. At low skew the two types are near-equal and neither alone can cross a quorum above one-half, so you need both, and the wait is the wait for the slower of the two. Push the skew up and the rare type gets rarer, the “slower of the two” gets slower still, and the expected time climbs — the classical curse, right on schedule. But it climbs to a cliff. At a precise amount of skew — s_θ = log₂(θ/(1−θ)) — the heavy type’s weight alone crosses the threshold, and in that instant the rare type stops being necessary. You don’t need it anymore. The expected time falls off a cliff and then keeps easing down, because now the only thing you’re waiting for is the common type, and you’ve been making it commoner all along. Rises, then falls. The coupon collector’s curse switches off exactly when you stop needing everything and only need enough. Global monotonicity — the whole moral of the classical law — is simply false the moment the stopping rule is a quorum.
The third is a phase transition, and it is where the fact gets deep. Line the weights up as a Zipf law, p = w ∝ i^{−s}, and let the system grow. For gentle skew (s < 1) the weight is spread over a macroscopic slice of the types; reaching the threshold still means seeing order-N of them; the time scales like N and — this is the beautiful part — the luck averages out. Run it again and again and the quorum time barely varies; its relative fluctuation shrinks toward zero. But for steep skew (s > 1) a handful of heavy types carry real weight no matter how large the system gets — the heaviest type’s share doesn’t vanish, it settles onto 1/ζ(s) and stays. Now quorum formation hangs on the random arrival of those few heavy types, and their luck never averages away. The quorum time stays genuinely random, heavy-tailed, forever. Below a critical skew the collective is deterministic; above it, it is at the mercy of a few. And the boundary, s = 1, is where the scale becomes N^θ·H_N — the harmonic number, Laplace’s own fingerprint, surfacing exactly at the seam between the two worlds.
So what is owed to the old law, in the end? Everything it claimed. Turn the threshold up to its limit — demand all of the weight, need every type — and the quorum integral collapses, term for term, back onto Flajolet’s formula for the non-uniform coupon collector, and for equal types back onto Laplace’s N·H_N, to the last digit. (I checked: at N=6 the 2026 formula and the 1812 answer agree at 14.70000000.) The new law does not overthrow the old one. It contains it, keeps it exact in the corner where you really do need everything, and departs only where most of life actually lives — where you need enough, and the last rare thing you were sure you couldn’t finish without turns out, past a certain point, to be something you never needed at all.
