Charged for the variance, not the range

Ten thousand coins are tossed, each landing heads with probability one in a thousand. The expected number of heads is 10. What is the chance of 30 or more?

Hoeffding’s inequality, the bound no single input can move it far built and drawn without putting back extended to finite urns, answers: at most $e^{-2 \cdot 20^2/10000} = e^{-0.08} \approx 0.92$. That is true and useless. The actual probability, computed exactly from the binomial distribution, is about $2.5 \times 10^{-7}$ — one in four million. The bound is wrong by a factor of nearly four million, and in the wrong direction for anyone who hoped to use it.

The bound is not being careless. Hoeffding’s inequality uses one fact about each coin: its value lies between 0 and 1. A coin that lies between 0 and 1 might be a fair coin, and for ten thousand fair coins a deviation of 20 from the mean really is ordinary. The bound has to hold for that coin too, so it cannot say anything sharper about this one. What it is missing is the variance. A coin that lands heads once in a thousand has variance about $0.001$, against $0.25$ for a fair one, and a bound that knew the variance could use it.

There is a quick way to see that the variance is the missing ingredient. The oldest bound on this shelf, Chebyshev’s from how far from the average a thing can be, uses the variance and nothing else, and it decays only like the inverse square of the deviation — the weakest decay of any bound in common use. For the rare coins it says the chance of being 20 or more from the average is at most $\sigma^2/20^2 = 9.99/400 \approx 0.025$. That is a hundred thousand times too large, but it is still thirty-seven times smaller than Hoeffding’s answer. A polynomial bound that knows the variance beats an exponential bound that does not, at a deviation of twenty, because the exponential one is decaying from the wrong starting point.

The two bounds this essay is about combine the two ingredients: the exponential decay that Hoeffding’s argument produces, and the variance that Chebyshev’s uses. They are older than Hoeffding’s — Sergei Bernstein’s dates from the 1920s — and they are what anyone estimating a rare probability actually needs.

Three bounds and the truth, for ten thousand rare coins #

Write $\sigma^2$ for the variance of the whole sum — here $10000 \times 0.001 \times 0.999 = 9.99$ — and $b$ for the most any single term can exceed its own average, which is at most 1. Bernstein’s inequality says that the chance of exceeding the average by $t$ is at most

$$\exp\!\left(-\frac{t^2}{2(\sigma^2 + bt/3)}\right).$$

At 30 heads, $t = 20$, this gives $6.1 \times 10^{-6}$. Bennett’s inequality, from 1962, is a little sharper, $\exp(-\sigma^2 h(bt/\sigma^2)/b^2)$ with $h(u) = (1 + u)\ln(1 + u) - u$, and gives $2.3 \times 10^{-6}$. The exact answer is $2.5 \times 10^{-7}$. Both bounds are within a factor of about ten to twenty-five of the truth, where Hoeffding’s was within a factor of four million.

The figure shows the whole range, from the average up to 50 heads. Hoeffding’s line barely leaves the top of the chart — for $t = 40$ it still promises 0.73. Bernstein’s and Bennett’s curves fall with the exact one, parallel to it on the logarithmic scale, which means they capture its rate of decay and miss only a factor in front. That factor is the price of a bound that knows two numbers about each coin instead of its whole distribution.

Where the variance enters the argument #

The derivation is short enough to follow, and it shows exactly where the variance goes in. Let $X$ be one term, with average 0, variance $v$ and no value above $b$. The function $(e^{x} - 1 - x)/x^2$ is increasing, so for every value $X$ can take, $e^{\lambda X} \le 1 + \lambda X + X^2\,(e^{\lambda b} - 1 - \lambda b)/b^2$. Taking averages, the middle term vanishes because $X$ averages to zero, and the last becomes the variance times a fixed factor:

$$\mathbb{E}\,e^{\lambda X} \le 1 + \frac{v}{b^2}\left(e^{\lambda b} - 1 - \lambda b\right) \le \exp\!\left(\frac{v}{b^2}\left(e^{\lambda b} - 1 - \lambda b\right)\right).$$

Hoeffding’s lemma, at the same step, bounds the generating function by $e^{\lambda^2 (\text{range})^2/8}$, and the range is all it sees. Here the variance multiplies the whole expression. For independent terms the generating functions multiply, so the variances add into $\sigma^2$; then Markov’s inequality applied to $e^{\lambda S}$, with $\lambda$ chosen to make the result as small as possible, gives Bennett’s inequality exactly. Bernstein’s follows from it by the elementary estimate $h(u) \ge u^2/(2 + 2u/3)$.

Nothing in the argument is specific to coins. It needs independence, a ceiling on each term, and the variances, and it delivers a bound whose shape is set by the ratio of the deviation to the variance-over-ceiling.

Two regimes, and the point where they meet #

Bernstein’s exponent is a fraction with two terms in the denominator, and which term dominates decides what kind of tail the bound describes.

When $t$ is much smaller than $3\sigma^2/b$, the $bt/3$ term is negligible and the exponent is $t^2/(2\sigma^2)$ — exactly the exponent of the normal distribution with the same variance. In that range Bernstein’s bound says the sum is as concentrated as a Gaussian, which is what the central limit theorem suggests and what Hoeffding’s bound would say if the coins were fair.

When $t$ is much larger, the $\sigma^2$ term is negligible and the exponent becomes $3t/(2b)$: linear, not quadratic. The tail decays exponentially rather than like a Gaussian. The crossover sits where the two terms of the denominator are equal, at $t = 3\sigma^2/b$ — here about 30 heads above the mean of 10.

The linear regime is not a weakness of the bound. It is true. The exact exponent, black in the figure, also bends away from the parabola, and for large $t$ it grows like $t \ln t$, the Poisson rate — because ten thousand rare coins are, to high accuracy, a Poisson count with mean 10. The normal curve’s exponent, extrapolated out there, overshoots the true one — at $t = 100$ it is 500 against a true 170 — so a normal approximation would understate the probability of 110 heads by a factor of $e^{330}$. The tail is not a bell made the same point about sums of ordinary coins; here the variance-aware bounds make it visible without computing the exact tail at all. Bennett’s exponent, $\sigma^2 h(t/\sigma^2)$, grows like $t \ln t$ too, and it tracks the exact curve across the whole range.

The variable with the heaviest tail, given two numbers #

Why these particular formulas? The Chernoff method, the route to every exponential bound here, reads a tail off the moment generating function $\mathbb{E}\,e^{\lambda X}$. A bound that knows only a term’s variance and its ceiling must use a generating function that is valid for every variable with that variance and that ceiling. The best such bound is the largest generating function in the class, and the question is which variable has it.

The search has the same shape as the one in the bound is the answer to a search, where Chebyshev’s inequality turned out to be the exact maximum of a tail over all distributions with a given mean and variance, attained by a distribution on three points. Here the quantity being maximised is a generating function rather than a tail, and the extra constraint is the ceiling, and the maximiser needs only two points.

The figure compares four variables with the same mean, variance and ceiling: a symmetric $\pm\tfrac12$, a uniform spread, a three-point variable on $-1$, $0$ and $1$, and a lopsided two-point variable that is usually slightly negative and occasionally equal to the ceiling. The lopsided one wins at every $\lambda$, and it is not close at large $\lambda$. Its generating function has a closed form, $(\sigma^2 e^{\lambda b} + b^2 e^{-\lambda\sigma^2/b})/(b^2 + \sigma^2)$, and Bennett and Hoeffding both proved it is the largest in the class. The Chernoff method applied to it gives the sharpest bound available from those two numbers; Bennett’s inequality relaxes it slightly into the closed form above, and Bernstein’s relaxes that into a simple fraction.

The extremal variable explains the two regimes. It spends most of its time slightly below average and occasionally jumps to the ceiling, so a sum of many copies behaves like a count of rare jumps. Small deviations come from the jumps’ number fluctuating around its mean, which is Gaussian; large ones come from an unusual number of jumps, which is Poisson. A coin that lands heads once in a thousand is exactly this variable, shifted by its mean: $1 - p$ with probability $p$, $-p$ otherwise, with ceiling $1 - p$ and variance $p(1-p)$. That is why the bound is so good for it — the worst case the bound guards against is the case at hand.

What ignoring the variance costs, as events get rarer #

The question can be asked for every rarity at once. Suppose the average of $n$ coins with heads probability $p$ is to be kept below $2p$ — twice its expected value. The true chance of failing falls exponentially in $n$, at a rate given by the relative entropy between the two coins, the quantity the tail is not a bell called the rate function. Every bound proves some smaller rate, and the ratio of the proved rate to the true one says how many more trials the bound demands than the truth requires.

For Bennett’s bound the ratio is essentially 1 for every small $p$: since the coin is the extremal variable, Bennett’s rate and the true rate agree to within a fraction of a percent. Bernstein’s loses 3%. Hoeffding’s rate is $2p^2$ while the true rate is about $0.386p$, so its share is about $5p$ — half a percent at $p = 0.001$, a twentieth of a percent at $p = 0.0001$. To prove the same confidence, Hoeffding’s bound asks for roughly $1/(5p)$ times as many coins: 193 times as many for a one-in-a-thousand event.

At $p = \tfrac14$ the gap has almost closed, because a coin that lands heads a quarter of the time has a variance, $0.1875$, not far below the $0.25$ that Hoeffding’s bound assumes. The variance matters in proportion to how far it falls short of the range, and for rare events it falls short by nearly everything.

Estimating a one-in-a-thousand chance #

The practical form of the question is a sample size. A chance of one in a thousand — a failure rate, an adverse reaction, a defect — is to be estimated to within half of itself, $\pm 0.0005$, with 95% confidence. How many independent trials are needed?

The exact binomial answer is about 15,400 trials. The normal approximation gets almost exactly the same number, 15,351, but guarantees nothing — it is an approximation, and in the tail of a skewed count it can err in either direction. Bennett’s and Bernstein’s bounds, which are guarantees, ask for 34,065 and 34,395: a little over twice the exact number, which is what it costs to know only a variance and a ceiling rather than the distribution. Hoeffding’s bound asks for 7,377,759.

That last number does not depend on $p$ at all. Hoeffding’s bound needs $\ln(2/\delta)/(2\varepsilon^2)$ trials to pin any average to within $\varepsilon$, whether the true chance is one in a thousand or one in two. It is the right number for a fair coin and roughly 480 times too many for this one. A planner who used it would run a study for years that needed weeks, and one who used the normal approximation would have no guarantee at all. The variance-aware bound is the one that is both safe and affordable.

The same regime explains a rule that medical statisticians use for events that have not yet been seen. If none of $n$ independent trials shows the event, then $3/n$ is a 95% upper bound for its probability — the rule of three — because a chance of $3/n$ would produce zero events in $n$ trials only with probability $(1 - 3/n)^n \approx e^{-3} \approx 0.05$. The bound is linear in $1/n$ rather than in $1/\sqrt n$, and that is the Poisson side of Bernstein’s inequality: when the variance is as small as the mean, a single rare event is as informative as a whole standard deviation of a common one.

In practice the variance is not known in advance — it depends on the very $p$ being estimated. The standard answer is an empirical Bernstein bound, due to Andreas Maurer and Massimiliano Pontil in 2009 among others, which substitutes the sample variance and pays a small additional term for having estimated it. The shape survives: a Gaussian term governed by the variance, and a linear term governed by the range.

Where each bound belongs #

The three bounds are not rivals so much as descriptions of three states of knowledge. Hoeffding’s bound is the right one when nothing is known beyond the range, and for terms whose variance is near the maximum it is nearly as good as the others. Bernstein’s bound is the one to write down: a single fraction, easy to invert for a sample size, and within a few percent of the best. Bennett’s is the one to compute when the last factor matters, and it is essentially exact for sums of rare events.

There is a fourth state of knowledge, and it is the one the ceiling hides. Every exponential bound here needs $b$, the most a single term can exceed its average. When there is no ceiling — a term that is occasionally enormous, like an insurance claim or the running time of a randomised program — neither Bernstein’s nor Bennett’s bound applies, and the plain average of the samples genuinely does not concentrate exponentially. The median of many small averages is the repair for that case: it recovers an exponential confidence from the variance alone, by changing the estimator rather than the bound. Between them, the variance-aware inequalities and the median of means cover what can be said from a variance, with and without a ceiling.

The same division runs through no single input can move it far, whose bounded-differences bound is Hoeffding’s in disguise and inherits its blindness. That essay ended by noting that replacing the range of each increment by a bound on its conditional variance gives inequalities “of Freedman’s and Bernstein’s kind”. This is what that replacement buys when the terms are independent: the difference between a promise of 92% and a promise of two in a million.

Still open: a Bernstein inequality for dependent structures #

For independent terms the picture is complete: Bennett’s bound is sharp at the level of generating functions, and nothing better follows from the variance and the ceiling alone. For dependent structures it is not. The bounded-differences method has a Bernstein version for martingales, due to David Freedman in 1975, but it needs the conditional variances of the increments, and for a complicated function of many inputs — the chromatic number of a random graph, the length of a longest increasing subsequence — nobody knows how to compute those conditional variances well enough to use it.

For some of those functions the true fluctuations are far smaller than any known inequality gives. The longest increasing subsequence of a random permutation of $n$ items fluctuates on the scale $n^{1/6}$, a result of Jinho Baik, Percy Deift and Kurt Johansson from 1999 that needed the machinery of random matrices; general inequalities of Bernstein’s or Talagrand’s kind reach $n^{1/4}$ at best. Which general principle, if any, produces the true scale — rather than a problem-specific calculation — is open.

What the figures do not settle #

Every tail probability and every sample size here is computed exactly from the binomial distribution, and every bound is checked against it at every point drawn; a bound that failed would have stopped the figure. The inequalities themselves are quoted, with their authors and dates, not proved, and the claim that the two-point variable has the largest generating function is checked for four variables at sixty-one values of $\lambda$ rather than for the whole class.

The coins are independent throughout. Everything above depends on that, and the dependent case is exactly where drawn without putting back found that the helpful kind of dependence costs nothing — and where the open question above begins.