Counting past what the register holds

A counter that can reach $n$ needs $\lceil \log_2(n+1) \rceil$ bits, and there is no argument about it: the register has to hold a different value for each count, and $n+1$ values need that many bits. For ten million events that is twenty-four bits.

Robert Morris had eight, on a machine in 1977 that had eight to spare, and needed to count events that would run into the millions. What he wrote instead is three lines long, holds five bits, and is the oldest structure in this field by two decades.

Keep a register $c$, starting at zero. On each event, increment $c$ with probability $2^{-c}$ and otherwise leave it alone. At the end, report $2^c - 1$.

Why the estimate is unbiased, and it is one line #

The claim is that $\mathbb{E}[2^c - 1] = n$ exactly, at every $n$, for every run length — not asymptotically and not approximately. It is worth doing because the argument is three symbols long and because it explains the shape of the algorithm.

Consider $\mathbb{E}[2^{c}]$ after each event. Given the current $c$, the register goes to $c+1$ with probability $2^{-c}$ and stays at $c$ otherwise, so

$$\mathbb{E}[2^{c_{new}} \mid c] = 2^{c}\left(1 - 2^{-c}\right) + 2^{c+1}\cdot 2^{-c} = 2^{c} - 1 + 2 = 2^{c} + 1.$$

The probability of the step and the size of the step cancel exactly, and the expectation of $2^c$ rises by one per event whatever $c$ happens to be. Starting from $2^0 = 1$, after $n$ events $\mathbb{E}[2^c] = 1 + n$, so $\mathbb{E}[2^c - 1] = n$.

That cancellation is the design. The register is not counting events, it is counting doublings, and the increment probability is chosen so that each doubling is worth exactly as many events as it represents. Any other probability breaks the identity, and the general form makes the dial visible: increment with probability $a^{-c}$ and report $(a^c - 1)/(a-1)$, and the same one-line argument gives $\mathbb{E}[a^{c}]$ rising by $a-1$ per event and the estimate unbiased again.

What it costs, and the number is small #

At base 2 the register reaches roughly $\log_2 n$, so it needs $\log_2 \log_2 n$ bits. For ten million events $c$ ends up near twenty-three, and holding twenty-three needs five bits against the exact counter’s twenty-four.

On the twenty-thousand-event stream measured here the largest $c$ observed over three hundred runs at base 2 was seventeen, which is five bits, against fifteen for the exact counter. That is a factor of three, and it is the smallest saving this field offers — the interesting property is not the ratio at one $n$ but that the ratio grows without limit. Doubling the stream adds one bit to the exact counter and, on average, nothing at all to Morris’s.

The 71% nobody quotes #

Unbiased is a weak property, and Morris’s counter is the standing example of how weak. The estimate is right on average over runs and any individual run is nowhere near.

The variance of $2^c - 1$ after $n$ events is $n(n-1)/2$, so the relative standard deviation is about $1/\sqrt{2} = 70.7\%$, independently of $n$. Over three hundred runs at $n = 20{,}000$ the measured figure is 70.3%, which is the prediction to within the noise of three hundred draws.

Seventy per cent is not an accuracy anybody would design for. A single run of the base-2 counter reporting eight thousand is entirely consistent with a true count of twenty thousand, and a caption quoting one such run would be quoting something close to noise. This is exactly the shape expected is not average is about, arriving in a place where the distinction decides whether the structure is usable: the expectation is perfect and the structure is not.

Which is why the textbook version is usually presented as a curiosity, and why the curiosity is only half the algorithm.

What the dial reaches, at both ends #

The predicted relative standard deviation is $\sqrt{(a-1)/2}$, so pushing the base towards one should keep buying accuracy for bits without limit — and the check is whether the measured points stay on the line where the increments become almost continuous.

And the other end of the same dial is where the design stops being worth anything, which the arithmetic says before the plate does: the saving is in bits of register, and a short stream has few to save.

The base is the dial #

Replacing 2 with a base $a$ closer to one makes the counter increment more often, so $c$ grows faster, so the register needs more bits — and each increment represents fewer events, so the estimate is finer. The variance works out to $(a-1)\,n(n-1)/2$, giving a relative standard deviation of $\sqrt{(a-1)/2}$: at $a = 2$ that is 70.7%, at $a = 1.1$ it is 22.4%, at $a = 1.02$ it is 10%.

The measurements agree, and the point of taking them is that the agreement is not automatic. A counter implemented with the increment probability at one base and the estimate arithmetic at another still runs, still fits its register, and reports a number with no relationship to the stream — which is the realistic form of the bug, because the base appears in two places and changing one of them is a one-line edit. The gate has that sabotage in it and requires the unbiasedness check to refuse it.

Read down the last two columns and the exchange rate is there: 10% error costs nine bits where 70% costs five, and the exact answer costs fifteen. Halving the error costs about two bits each time, which is the same $\varepsilon^{-2}$ law every structure in this field obeys, arriving here in its cheapest possible setting — a single register, no hashing, and no assumption about the keys because the counter never looks at them.

What a register value means #

It is tempting to read $c$ as a compressed version of the count, and the reading that actually explains the behaviour is different: $c$ is the number of times the counter has been surprised.

Each increment is a rarer and rarer event by construction. Going from $c$ to $c+1$ takes, in expectation, $a^{c}$ events, so the register spends most of its life not moving. Over twenty thousand events at base 2 the register moves about fifteen times and stays put nineteen thousand nine hundred and eighty-five times. Almost every event costs a draw and produces nothing.

That is where the variance comes from, and it is worth locating precisely because it is not the usual place. The counter is not noisy because each increment is imprecise; each increment is exactly worth what the estimate says it is. It is noisy because the last increment is worth as much as everything before it put together. At base 2 the estimate is $2^c - 1$, so a single extra step doubles the answer and a single missing step halves it — and whether that last step happened is one coin flip. A structure whose output is decided by the most recent doubling has a relative error of order one, and no amount of running it longer changes that.

Lowering the base fixes exactly this. At $a = 1.02$ a single step moves the estimate by 2%, so the last step is worth 2% rather than 100%, and the register has to record fifty times as many steps to reach the same count. The bits and the error are the same quantity read two ways.

Concentration, and why the mean is the wrong summary #

The variance gives a standard deviation; what a caller needs is a probability that a particular run is badly wrong. Chebyshev’s inequality turns the first into the second, weakly: with relative standard deviation $\sigma$, the chance of missing by more than $k\sigma$ is at most $1/k^2$. At base 2 that is a guarantee of “within a factor of about three, nine times in ten”, which is not usable for anything.

There are two escapes and this field uses both. The first is to lower the base, which drives $\sigma$ down at a cost in bits — the trade this essay measures. The second is to run several counters and combine them, which drives the failure probability down at a cost in bits without touching $\sigma$ at all, and which turns out to be the general construction behind every guarantee in the field. The measured version of the second is in the estimate that is a median of means, and the two are worth keeping apart in the mind: one buys accuracy and the other buys confidence, and a bound quoting both is quoting two separate purchases.

The off-by-one that no measurement here can see #

The estimate is $2^c - 1$ and not $2^c$. Dropping the minus one is a plausible slip: it makes the estimate high by exactly one at every $n$, always.

At $n = 100{,}000$ that is a bias of one part in a hundred thousand sitting inside a spread of 70.7%. Separating it from zero at four standard errors of the mean would need about $8 \times 10^{10}$ runs. It is a real defect, it is provably present, and no measurement this site could afford will ever detect it.

That is worth stating plainly on a site whose method is measurement. The rule here is not that everything must be measured — it is that nothing may be asserted without a test it could fail, and the test can be an argument as well as a run. The minus one is earned by the derivation above, which is checkable in a way a hundred billion runs are not, and the gate asserts the thing that is measurable: that the trials needed to see the bias are astronomical, so that if someone later tightens the unbiasedness tolerance to a level the bias would trip, the check says so rather than failing mysteriously.

Where the randomness comes from, and what it costs #

Each event costs one draw. On this site a random bit is a counted resource — counting the coin flips introduced the fourth counter for exactly this reason — and Morris’s counter is an unusual consumer of it: the randomness budget is $\Theta(n)$ draws for a structure whose entire output is five bits.

There is a cheaper implementation for the base-2 case that is worth naming, because it shows what the draw is actually for. Incrementing with probability $2^{-c}$ is the same as flipping $c$ coins and requiring all heads, so an implementation can draw $c$ bits and test them, or — better — draw a geometric variate and skip ahead. Neither changes the distribution and both change the bit budget, which is the same shape as the two reservoir algorithms: identical output, different appetite for entropy.

The skip-ahead version is the more interesting of the two, because it makes the counter’s cost structure match its state. While $c$ is at fifteen the counter is going to sit still for about thirty-two thousand events, and drawing a geometric variate says so in one step instead of thirty-two thousand. A counter implemented that way spends $\Theta(\log n)$ draws in total rather than $\Theta(n)$ — it does not even have to look at most of the events, only to know how many went by — and the estimate it produces is drawn from exactly the same distribution.

That is worth holding onto because it is the first appearance of a pattern the field repeats. A structure’s state, its accuracy, its randomness budget and its per-item work are four separate quantities, they are not tied together, and an algorithm can be improved along one of them without moving the others at all. The measurements in this field keep them apart deliberately: the plates report bits and error, and the per-item hash and draw counts are recorded beside them rather than folded in.

Almost mergeable, and the obstruction is the register #

Every other structure in this field is asked whether two of them combine, and the counter’s answer is the most interesting of the set: the algebra works and the register cannot hold the result.

Two counters over two streams hold $c_1$ and $c_2$, with $\mathbb{E}[a^{c_i}] = 1 + (a-1)n_i$ each. For a merged counter to be unbiased about $n_1 + n_2$ it needs $\mathbb{E}[a^{c}] = 1 + (a-1)(n_1+n_2)$, which is exactly

$$a^{c} \;=\; a^{c_1} + a^{c_2} - 1$$

That is a closed form, it needs nothing but the two register values, and it is right. The trouble is that $\log_a(a^{c_1} + a^{c_2} - 1)$ is not an integer, and a register holds integers. Two base-2 counters both at fifteen would need a merged register at $\log_2(2^{16}-1) = 15.99997$, and rounding it to sixteen or to fifteen breaks the identity that the whole structure rests on.

So the counter is mergeable in expectation and not representable, which is a failure mode none of the other structures in this field has — a maximum of two registers is a register, a sum of two cells is a cell, and only here does the correct answer fall between two states.

The repair is the algorithm’s own trick applied a second time. Round randomly: take the floor with the probability that makes the expectation come out right, and the ceiling otherwise. Since $a^{\lfloor c \rfloor} \le a^{c_1} + a^{c_2} - 1 \le a^{\lceil c \rceil}$, such a probability always exists and is one division to compute. The merged counter is then exactly unbiased again, and it has paid for it in variance — the rounding is one more coin flip whose outcome moves the estimate by a whole step, which at base 2 is a factor of two.

Two things follow that are worth having.

The variance cost is the base again. A randomised rounding at base 2 adds a step worth 100% of the estimate; at base 1.02 it adds one worth 2%. So the same dial that makes the counter accurate makes it mergeable cheaply, and the base-2 counter — the one everybody quotes — is the setting at which merging is most expensive.

And it explains why the descendants merge cleanly. A HyperLogLog register merges by maximum, which is closed on integers and needs no rounding at all; that is what exact mergeability is bought with. The counter’s estimator is a sum in the transformed domain and the register is a logarithm of it, and a sum of logarithms is not a logarithm of an integer — which is one sentence explaining why the structure that came first is the one that does not combine.

Two things it is not #

It is not a compressed counter. Nothing here is reversible and there is no encoding involved. A compressed counter with five bits would still have to distinguish only thirty-two counts; this one distinguishes thirty-two scales, and gives up on distinguishing anything inside a scale. The distinction is the same one the coding field draws between a lossless coder and a summary, arriving in a setting where the object being summarised is a single integer.

It is not a sample. The counter does not look at a subset of the events and extrapolate; it looks at every one of them and makes a decision about each. Which is why it has no notion of a sampling rate and no dependence on the order the events arrive in, and why its error does not shrink when the stream gets longer — the thing being estimated grows at exactly the rate the estimator’s precision does not.

What it is actually for #

Approximate counting in five bits is not a problem many programs have. The reason the structure is here is that everything later in this field is a variation on the identity above.

A HyperLogLog register is a Morris counter with the coin replaced by the hash of the key, which is what makes it count distinct keys rather than events — the same key hashes the same way, so it cannot advance the register twice. A Count-Min cell is a counter with the randomness moved from the increment to the address. The median-of-means construction in the estimate that is a median of means exists precisely to fix the 71%, and it fixes it for every estimator in the field at once, using an argument that has nothing to do with counting.

And the register is the first place the field’s central sentence can be checked rather than believed: the state is a fixed number of bits, chosen before the stream starts, and the answer is whatever those bits can support. Five bits support 71%. Nine bits support 10%. Fifteen bits support the truth, and the stream is allowed to be as long as it likes only in the first two cases.