The estimate that is a median of means

Every bound in this field has the same shape. The estimate is within $\varepsilon$ of the truth with probability at least $1 - \delta$. Two parameters, and the structures are sized by choosing them.

They come from two different places, they are bought separately, and one construction supplies the second for every estimator in the field at once. It is worth an essay of its own because it is not a property of counting, or of hashing, or of any structure: it is a two-line argument about distributions, and everything else in the field consumes it.

The two purchases #

Start from an unbiased estimator with a large relative standard deviation. Morris’s counter at base 2 is the standing example: right on average, 71% wide, and useless as it stands.

Averaging buys accuracy. Take $r$ independent copies and average them. The mean is still unbiased and its variance is divided by $r$, so the relative standard deviation falls as $1/\sqrt{r}$. Four copies halve it, sixteen quarter it. This is the purchase every plate in this field is drawing when it plots error against bits, and its exchange rate is the $\varepsilon^{-2}$ law.

Averaging does not buy confidence. Chebyshev’s inequality is the only thing available for a distribution known by its variance alone, and it says the chance of missing by $k$ standard deviations is at most $1/k^2$. That is a polynomial tail. Getting the failure probability to one in a thousand by averaging alone means driving $k$ to about thirty-two standard deviations, which means driving the standard deviation down by a factor of thirty-two more than accuracy alone required — a thousandfold in copies, for a promise rather than for a better answer.

The gap between those two sentences is the whole reason the construction exists.

The construction #

Split the copies into $g$ groups, average within each group, and take the median of the $g$ group means.

The median is wrong by more than $\varepsilon$ only if at least half the group means are. Each group mean is wrong with some probability $p$ — a constant, say a third, obtained from Chebyshev with the group made just large enough — and the groups are independent. So the failure probability is the chance of at least $g/2$ successes in $g$ independent coin flips of bias $p$, which for $p < 1/2$ falls exponentially in $g$.

That is the switch. Accuracy is bought at a polynomial rate and confidence at an exponential one, and the exponential comes from the median rather than from the mean. Getting $\delta$ to one in a thousand takes $g$ around twenty rather than a thousandfold increase in copies, and the group count enters every bound in this field as $\lceil \ln(1/\delta) \rceil$ or something within a constant of it.

The measured version is the hero figure. What matters about measuring it rather than quoting it is that the exponential is a claim about a rate, and a rate is checked by counting: two hundred and forty runs at each design, failures counted, plotted on a log axis. A design whose failure rate stopped falling would show up as a curve that flattens, and there is a version of this construction — described below — that does exactly that.

What the state is held constant for #

The figure holds the total bits fixed across designs in one respect and not another, and the distinction decides what it measures.

Each design uses $g$ estimators of forty-eight hashes each, so nine groups hold nine times the state of one. That is not a confound, it is the point being priced: the exponential is bought with state, and the question is what rate of return it comes at. Nine times the bits for a twentyfold fall in failures is a very different bargain from nine times the bits for a threefold improvement in accuracy, and the two curves are drawn on the same axes so the comparison can be made.

Why the median and not the mean of the means #

Averaging the group means gives the average of everything, which is exactly the estimator the whole construction was trying to improve on. Nothing is gained: the variance is the same as it would have been, the tail is the same Chebyshev tail, and the grouping has done no work.

The median is doing something a mean structurally cannot: it is discarding outliers without being told which they are. One group that came out wildly wrong moves the mean by its full amount and moves the median not at all, provided the other groups agree. That robustness is the mechanism, and it is why the construction survives estimators with heavy tails — including ones whose variance is infinite, where the mean of the means is not even well defined and the median of means still works.

It also explains a failure mode worth naming. If the individual estimator is biased, every group mean is biased in the same direction, so the median is biased too and the construction repairs nothing. It buys confidence about the wrong number. That is why unbiasedness is checked separately for every estimator here — the counter’s identity in counting past what the register holds, the harmonic mean’s correction in the correction that makes it work — rather than being folded into an accuracy check that this construction would paper over.

The distribution is the result, again #

This is the third time the site has arrived at the same rule from a different direction, and the accumulation is worth noticing.

On average is not a number made the case for sorting: an average-case comparison count is a summary of a distribution over inputs, and quoting it without the spread hides whether the bad cases matter. Expected is not average sharpened it for randomised structures: the expectation is over the algorithm’s own coins rather than over the inputs, which is a stronger guarantee, and it is still a summary of a distribution.

Here the distribution is not context, it is the object being engineered. A design’s $\delta$ is a statement about the shape of its tail, so the tail is the deliverable, and an implementation that reported a better mean and a fatter tail would be worse in the only sense the bound cares about.

What it costs, in the currency of this field #

The construction is not free and its price is legible on the same axes as everything else. A design with $g$ groups of $r$ copies each holds $g \cdot r$ estimators’ worth of state, and its two parameters buy two different things:

• $r$ sets $\varepsilon$, at the $\varepsilon^{-2}$ rate.
• $g$ sets $\delta$, at $\ln(1/\delta)$.

So the total state goes as $\varepsilon^{-2} \ln(1/\delta)$, which is the shape of nearly every space bound in the streaming literature, and the reason the two parameters appear in it so differently. Halving $\varepsilon$ costs four times the state; halving $\delta$ costs one extra group. Confidence is cheap and accuracy is not, and a design that has been given a lavish $\delta$ and a mean $\varepsilon$ has usually been sized by someone reading the two parameters as though they cost the same.

Why the logarithm is natural #

$\lceil \ln(1/\delta) \rceil$ turns up so often in this field that it is worth seeing where the natural logarithm comes from rather than a base-two one, since the quantity being counted is groups and groups are integers.

The per-group failure probability $p$ is a constant, and the median fails when at least half the groups do. Chernoff’s bound on that event gives $\exp(-2g(1/2 - p)^2)$, so the exponent carries a constant that depends on how far below a half $p$ sits. Setting the whole thing to $\delta$ and solving gives $g = \ln(1/\delta) / (2(1/2-p)^2)$, and the customary $\lceil \ln(1/\delta) \rceil$ is that expression with the constant absorbed — legitimate, because it is a constant, and worth knowing about, because it is the difference between nine groups and thirty-six.

This is the field’s characteristic form of looseness and it is the same one Count-Min’s depth has. A bound written as $O(\ln(1/\delta))$ groups is honest about the shape and silent about the multiplier, and the multiplier is decided by how good the base estimator was. The hero figure measures the whole thing including the constant, which is what a measurement is for.

Independence is the assumption #

The exponential rests on the groups being independent, and that is an assumption about the implementation rather than a property of the mathematics.

In practice the $g \cdot r$ estimators are usually generated from one seeded stream, which is fine, and are sometimes generated by reusing one hash function with different salts, which is not obviously fine at all. Two estimators sharing structure fail together, and a design whose groups fail together has an exponential in name only — the measured failure rate flattens out at whatever the shared component’s own failure rate is.

That is the failure mode this construction has that is hardest to see, because a design with correlated groups still shows an improving failure rate for the first few groups. It stops improving later, at a level nobody wrote down. Every design measured here draws its estimators from independent seeds and the plates say which, on the same principle that puts $B$ and $M$ on the external-memory plates.

The exponential, three more ways #

A straight fall on a logarithmic axis is the claim, and the three parameters of the design each move it differently.

The third parameter is the one the construction is about, and taking it further is the only way to tell an exponential from a curve that happens to look like one over five points.

Where the construction is not used, and why #

Two of the structures in this field carry a stated $\delta$ and do not use a median of means, and the exceptions are instructive.

Count-Min’s rows are the construction with the median replaced by a minimum, and the substitution is legitimate only because its errors are one-sided. Every row’s estimate is an overestimate, so the smallest of $d$ of them is wrong by more than $\varepsilon N$ only if all $d$ are, giving $\delta =$ (per-row failure probability) to the power $d$ — an exponential in the depth, from the same independence, without needing a median at all. A count that is never under is where the one-sidedness is earned.

HyperLogLog’s registers are neither. Its $m$ registers are averaged — harmonically — and there is no median anywhere, so its guarantee is a statement about a standard error rather than about a confidence, and it is usually quoted that way. That is not a weaker structure, it is a structure making a different kind of claim, and reading “relative error 1.04/$\sqrt m$” as though it were an $(\varepsilon, \delta)$ bound is a category error the field commits routinely.

The version that stops working #

A construction is best understood by the nearest thing that fails, and there is a natural one here.

Take the median of $g$ individual estimators rather than of $g$ group means. It still discards outliers and its failure probability still falls exponentially — but it converges to the wrong number. The median of many draws from a skewed distribution converges to the distribution’s median, not its mean, and an estimator that is unbiased in the mean is generally not unbiased in the median. So the construction’s exponential arrives intact, wrapped around a value that is systematically off, and every additional group makes the guarantee stronger about a number that is wrong.

That is the shape the group means exist to avert: averaging within a group makes the group’s distribution close to symmetric, by exactly the central-limit argument, and only then is its median the thing anybody wanted. The order of the two operations is not decorative, and swapping them produces a design whose measured failure rate improves and whose measured error does not.

It is a good failure to keep in mind when reading any claim of the form “the guarantee improves exponentially”. The exponential is about agreement between copies, and agreement between copies is only evidence about the truth when each copy is aimed at it. A hundred thermometers that all read two degrees high agree beautifully.

The split between groups and copies, at fixed state #

The two parameters are described above as buying two things, and a design usually has a fixed budget rather than two independent ones. Splitting $N$ estimators into $g$ groups of $r = N/g$ each is then a single decision, and it is not obvious which way to lean.

Raising $g$ does three things at once and they do not all point the same way.

It improves $\delta$, because the failure probability falls like $\exp(-2g(\tfrac12 - p)^2)$.

It worsens $\varepsilon$, because each group now averages fewer copies and the group mean’s spread grows like $\sqrt{g/N}$.

And it worsens the exponent’s own constant, because $p$ — a group’s chance of missing — rises as the groups get smaller, so $(\tfrac12 - p)$ shrinks. That third effect is the one the bound’s $O(\ln(1/\delta))$ hides, and it is the reason the split has an interior optimum rather than a monotone answer.

The practical rule that falls out is the one the literature states without deriving: make the groups just large enough that $p$ is comfortably below a half, and spend everything left on more groups. A group with $p = 0.45$ has an exponent constant of $2(0.05)^2 = 0.005$ and needs hundreds of groups to reach a useful $\delta$; a group with $p = 0.2$ has a constant of 0.18 and needs a handful. The difference between those two designs is a few copies per group and a factor of thirty in how many groups are needed.

That also explains a shape in the figures above. The steeper fall at the looser tolerance is not a fact about the tolerance — it is that a looser $\varepsilon$ makes each group succeed more often, which moves $p$ away from a half, which steepens the exponential. The tolerance and the confidence are coupled through the group’s own success rate, and a design that tightens $\varepsilon$ without adding copies per group has quietly made its confidence worse as well.

Measuring an exponential costs exponentially many runs #

The hero figure stops at nine groups, and the reason is a limit on the method rather than on the construction.

At nine groups, three of two hundred and forty runs failed. That is a rate of 1.25%, and the standard error on a proportion estimated from three events is about 0.7 points — so the measurement resolves somewhere between half a per cent and two and a half, which is a factor of five. One more group would put the expected count near one, where the measurement resolves nothing at all.

Measuring a failure rate that falls exponentially requires a sample that grows exponentially. Ten groups needs about a thousand runs to see the same handful of failures; fifteen needs tens of thousands; twenty — a perfectly ordinary design parameter — needs more runs than a figure can afford by a wide margin.

Two consequences, and the first is the honest reading of the plate.

The measurement establishes the shape over the range drawn and cannot reach the range designs are actually specified in. A structure sized for $\delta = 10^{-3}$ is at a failure rate this method would need a hundred thousand runs to see once, so the exponential there is quoted rather than counted — which is the same division this collection draws between a floor performed and a floor cited, arriving on the other side of the field.

And it says what the measurement is for. Counting failures cannot validate a design at its operating point; it can validate the mechanism at a point where failures are common enough to count, and the extrapolation to the operating point is then an argument rather than a measurement. That is worth doing precisely because the mechanism is what fails — a design with correlated groups has a failure rate that flattens, and the flattening is visible in exactly the range this figure covers.

What to take from it #

Three things, and they are the reason this sits in the randomness field rather than in the streaming one.

Accuracy and confidence are separate purchases. They appear in the same bound, they are set by different parameters, and they cost different amounts — $\varepsilon^{-2}$ against $\ln(1/\delta)$. A design that has both wants two numbers from whoever is specifying it, and being handed one number and a vague sense of “accurate” is how sketches end up sized by folklore.

The exponential comes from a median and nothing else. Wherever a structure in this field carries a $\delta$, something in it is playing the median’s part: an actual median, or Count-Min’s minimum standing in for one because its errors are one-sided. A structure with no such step has no $\delta$ to quote, and HyperLogLog is exactly that structure.

A failure rate is checked by counting failures. Not by evaluating the bound, which is what the bound is for, and not by looking at the typical error, which is the other parameter. The hero figure is two hundred and forty runs at each of five designs and its content is one number per design: how many missed.