Counting a population by its repeats

The birthday problem starts from a known year of 365 days and asks how many people it takes before two share a birthday. The answer, twenty-three for an even chance and about twenty-five on average, is surprising because it is so small: about the square root of the number of days, not a large fraction of it.

That square root can be read in the other direction. Suppose the number of days is unknown — it is the number of species in a forest, the number of words a writer knows, the number of distinct visitors to a website, the number of fish in a lake — and the only thing available is a stream of random draws from it. Each time a draw repeats one already seen, the stream has measured something about the size of what it is drawing from. The birthday problem says a repeat should come after about the square root of the size; so a repeat that comes after $T$ draws suggests a size of about $T^2$, and every further repeat sharpens the estimate.

One repeat, one wide guess #

The figure turns each room into a measurement. When the $T$-th person enters and shares a birthday with someone already there, $T(T - 1)/2$ pairs of people have been checked and exactly one has matched. If each pair matches with chance $1/N$, the natural estimate of $N$ is the number of pairs per match, $T(T - 1)/2$. Averaged over twenty thousand rooms it comes out at 365 to within a fraction of a per cent: the estimate has no systematic error.

But it is very noisy. A room in which the first match comes at the fourth person says the year has six days; a room in which it comes at the fortieth says 780. The histogram is skewed and wide, with a tenth of the rooms below 45 and a tenth above 820. A single repeat measures the population only to within a factor of several — which is still remarkable, given that it took only about two dozen draws to make, but it is not a census.

The noise has a clean explanation. The estimate rests on a single event, the first match, and the timing of a single rare event has a spread comparable to its average. Any estimate based on one occurrence is this rough; the same is true of estimating how common a disease is from the first case in a village, or how large a city is from the first time a stranger is met twice. The remedy is to keep drawing and count every match.

The shape of the histogram, piled up at small estimates with a long tail to the right, also has a reason. The first match comes after a number of people $T$ that is spread around $\sqrt{N}$ like a bell with a long right side, and the estimate is roughly $T^2/2$. Squaring stretches the right side of any spread much more than the left: a room whose first match comes at twice the typical time gives an estimate four times the typical one, while a room whose match comes at half the time gives a quarter. So the median room underestimates the year — its estimate is 253 for a true 365 — exactly the 253 pairs among twenty-three people, since the median room is the one whose first match comes at the twenty-third person — and the average is rescued by the few rooms that wait a long time. The famous twenty-three, read backwards, is a median estimate of the year that is a third too small. A ruler graduated in squares exaggerates every error on the long side, and the first figure is that exaggeration drawn.

Counting every matching pair #

After $k$ draws there are $k(k - 1)/2$ pairs of draws, and some number $C$ of them came out the same. The estimate $\hat N = k(k - 1)/2C$ uses every match, and its accuracy improves as the matches accumulate.

The typical error halves every time the number of draws doubles. That is faster than the usual rate of statistics, where doubling a sample shrinks errors only by a factor of $\sqrt2$, and the reason is that the information is in the pairs, whose number grows as the square of the sample. The number of matches is roughly a Poisson count with mean $k^2/2N$, its relative error is about one over the square root of that mean, and so the relative error in $\hat N$ falls like $\sqrt{2N}/k$: in proportion to $1/k$, not $1/\sqrt{k}$. The dashed line in the figure is that prediction, with the constant $0.67$ that converts a standard deviation into a typical error, and the measured points sit on it.

At 3,200 draws from 10,000 kinds — a sample a third the size of the population, most of whose members have been seen at most once — the estimate is good to three per cent. Nobody has listed the population; the repeats have measured it.

Unbiased in the pairs, not in the estimate #

There is a subtlety in which quantity is estimated without bias, and it explains the skew of the first figure. The number of matching pairs has an exact expectation: each of the $k(k - 1)/2$ pairs matches with chance $1/N$, so $\mathbb{E}[C] = k(k - 1)/2N$, whatever the dependence between pairs. That makes $C$ an unbiased estimate of $k(k-1)/2N$, and so $2C/k(k - 1)$ is an unbiased estimate of $1/N$ — the chance that two draws match.

The estimate of $N$ itself is the reciprocal, and taking a reciprocal does not commute with averaging. When $C$ is small and variable, $1/C$ is pulled upwards by the occasions on which $C$ comes out low — the average of a convex curve lies above the curve of the average — so $k(k-1)/2C$ overestimates $N$ on average, and when $C$ can be nought the estimate is not even defined. The first figure avoids the problem by stopping exactly at the first match, which makes $T(T - 1)/2$ a different statistic with its own unbiasedness; the pair-count figure avoids it by drawing until matches are plentiful. Chapman’s correction to the capture–recapture estimate, adding one to each count, is the same repair applied to the two-sample case.

The general lesson is that the natural quantity in these problems is the rate of repeats, not the size. The rate is estimated without bias by counting; the size is its reciprocal, and inherits all the trouble of dividing by a small, noisy number.

The square root, as a price #

How many draws does a given accuracy cost, as the population grows?

An estimate within ten per cent needs about a hundred matches, since the relative error is about one over the square root of the number of matches; a hundred matches need about $\sqrt{200N}$ draws — the figure’s constant, 91, is what a typical rather than a standard error requires. For a hundred thousand kinds that is about three thousand draws. Seeing every kind at least once — the coupon collector’s problem — needs $N \ln N$, about 1.2 million draws for the same population. The ratio between the two grows without limit: the larger the population, the more a census costs relative to an estimate.

This is the birthday problem as an economy. Matches are cheap because they are about pairs, and pairs are plentiful; a census is expensive because it is about individuals, and the last few individuals are the hardest to meet. Anyone who needs to know how large something is, rather than what is in it, should count repeats.

Mark, release, recapture #

Ecologists have counted animals this way since the nineteenth century, in a version that splits the draws into two samples.

Catch $a$ fish, mark them, release them, and let them mix. Catch $b$ more and count how many are marked, $m$. If the second catch is a fair sample, the marked fraction in it, $m/b$, should match the marked fraction of the lake, $a/N$, so $N \approx ab/m$. That is the Lincoln–Petersen estimate, used by C. G. J. Petersen on fish in Danish fjords in the 1890s and by Frederick Lincoln on ducks in the 1930s. Chapman’s correction, adding one to each count, removes most of its bias when the overlap is small, and the figure’s average of 2,001 against 2,000 shows it working.

It is the birthday problem with the pairs split across two rooms. The overlap $m$ counts the cross pairs — one fish from each catch — that are the same fish, among the $ab$ cross pairs available; each is the same fish with chance $1/N$; so $m \approx ab/N$. The single-sample estimate counted pairs within one sample; this one counts pairs across two. Both measure a population by how often it repeats itself, and both cost about the square root of what they measure.

It is also the two-list version of the problem that four lists solve sooner: there the question was how long the lists must be to expect one match, here it is what the number of matches between two lists of known length says about the space they were drawn from. The arithmetic is the same arithmetic run in opposite directions.

Repeats in a sequence that is not random #

The same reading applies to a deterministic sequence, and there it measures something less obvious. The middle-square generator on four-digit numbers repeats after 43.7 steps on average, where a random map on ten thousand values would repeat after about 125. Read as a population estimate, $T^2/2$, the middle square behaves like a random map on about a thousand values, not ten thousand: its effective size is a tenth of its nominal size. The census of its cycles explains why — a fifth of its seeds fall into the single value zero and most of the rest into a few short loops — but the repeat rate alone, without any census, would have detected that the generator’s state space is effectively much smaller than its digits suggest.

That is how collision counts are used in testing generators of random numbers and hash functions. A generator whose outputs repeat sooner than the birthday bound predicts has an effective output space smaller than its nominal one, by exactly the factor the repeats measure, and the two constants that do not walk at random in Pollard’s method were caught the same way: their sequences repeated at a different rate from a random map’s. A repeat count is a measurement of size that does not care whether the thing measured is a lake of fish, a codebook or an algorithm.

When the kinds are not equally common #

Every figure so far drew from kinds equally likely. Real populations are not like that. A few species of bird are seen constantly and most rarely; a few words make up most of any text. What do the repeats measure then?

The pair-count estimate no longer finds the number of kinds. It finds 41, for a population of 2,000. The reason is that two random draws match with chance $\sum p_i^2$ — the probability that both land on the same kind, summed over kinds — and the estimate $\hat N$ is the reciprocal of that. When the shares are equal it is the number of kinds. When they are not, it is the effective number: how many equally common kinds would produce the same rate of repeats. A population dominated by a few common kinds repeats as if it were small, and the unevenness that brings a birthday match sooner is the same unevenness that makes the repeats undercount.

That is not a failure of the method; it is a statement of what the method measures. Ecologists call $1/\sum p_i^2$ the inverse Simpson index and use it as a measure of diversity in its own right, and it is the right number for some questions — how many kinds a typical observer effectively deals with — and the wrong one for others.

The surprising connection: the singletons measure the unseen #

To count the rare kinds, a different statistic is needed, and it comes from Bletchley Park. During the Second World War, Alan Turing and I. J. Good were estimating how much of the German naval cipher’s codebook remained unseen, from the frequencies of the cipher groups already intercepted. Their answer, published by Good in 1953, is disarmingly simple: the share of the population not yet seen is about the share of the draws that were seen exactly once.

The figure confirms it: of 3,000 draws, 15.8 per cent were singletons, and the true share of probability on kinds not yet seen is 15.8 per cent. The argument is that a kind seen once is a kind that only just made it into the sample; the kinds not seen at all are like it, a little rarer, and their total share is estimated by how much of the sample came from kinds at the edge of being missed. The rarest kinds — the ones that dominate the coupon collector’s wait — are exactly the ones this estimate is about.

So the two ends of the count measure two different things. The repeats measure the crowded kinds, through $\sum p_i^2$, and the singletons measure the missing ones. Between them they describe a population that nobody has listed: how concentrated it is, and how much of it lies beyond what has been seen.

Real animals are not independent draws #

Every draw here is independent and the population fixed. Real samples are not: animals that were caught once may be shier or bolder the second time, visitors to a website return in patterns, and a forest’s species change while it is surveyed. Each departure biases the estimates in ways the figures cannot show, and practical methods spend most of their effort correcting for them.

The uneven population is one shape. The figure uses shares falling like one over rank, a common shape for words and species. Other shapes give other relations between the number of kinds, the effective number and the unseen share, and the Good–Turing estimate is accurate when the unseen kinds are individually rare — which it is for this shape and not for every one.

No method recovers the number of kinds from a small sample of a very uneven population. Kinds rare enough never to appear leave no trace at all, and any estimate of how many there are rests on an assumption about the shape of the tail. The figures show the effective number and the unseen share, which can be estimated; the total count of kinds, in general, cannot.

Still open: how many words Shakespeare knew #

The sharpest form of the problem is a famous example. Bradley Efron and Ronald Thisted asked in 1976 how many words Shakespeare knew, from the 884,647 words of his works, of which 31,534 are distinct and 14,376 appear only once. The singletons suggest that a new work would contain many words not in the canon, and when a newly attributed poem was found in 1985, their method predicted how many new words it should contain — and the prediction matched, which was taken as evidence for the attribution.

How many words Shakespeare knew in total, however, cannot be estimated without assumptions, and Efron and Thisted’s lower bound of about 35,000 more is a statement about what the data force rather than an estimate of the vocabulary. The general question — from a sample of a population with an unknown long tail, how many kinds are there — has no solution without a model for the tail, and the theory of what can and cannot be estimated, and with what error, has been developed in recent decades without closing it. Counting by repeats measures everything about a population except, in general, how many things are in it.