No single input can move it far

Every bound in how far from the average a thing can be and the bound that answers a search is about a single quantity with a mean and a variance. The sharper bounds in the literature — the ones giving an exponentially small tail rather than a polynomial one — all carry an extra hypothesis, and it is always stated the same way: the quantity is a sum of independent pieces.

That hypothesis is stronger than the proof needs, and finding out what the proof actually uses changes what the bound applies to.

The number the bound depends on #

Let $f$ be a function of $n$ inputs, each drawn separately. Define $c_i$ to be the most $f$ can change when the $i$-th input is altered and the others are held fixed. That is a property of the function alone — no probabilities in it — and it is computable by trying every alteration.

The bounded-differences inequality then says

$$\Pr\big(|f - \mathbb{E}f| \ge t\big) \;\le\; 2\exp\!\left(\frac{-2t^2}{\sum c_i^2}\right).$$

Nothing in that statement requires $f$ to be a sum. What it requires is that no input has much leverage, and the conclusion is exponentially small in $t^2$ — the same shape of tail a sum of independent bounded pieces gets.

For a sum of $n$ values each in a range of width $w$, changing one input moves the sum by at most $w$, so $c_i = w$ and the bound reads $2\exp(-2t^2/nw^2)$. That is Hoeffding’s inequality, recovered as the special case, and the derivation used the sum only to compute $c_i$.

What the enumeration is for #

The figures compute $c_i$ by exhaustion rather than by an argument, and that is a deliberate choice with a cost. For ten binary inputs there are 1024 cases and for each of them ten positions to alter, which is ten thousand evaluations of the function — instant, and completely reliable.

An argument would be cheaper and is where mistakes live. Reasoning about the largest effect a single input can have is exactly the kind of estimate that comes out too small: a plausible argument gives a $c$ that holds in typical cases and fails on a configuration nobody thought of, and the resulting bound is simply false with no symptom — which is the failure mode an approximation has and a bound does not, arriving here through the hypothesis rather than the conclusion. The exhaustive version cannot be wrong about the function it was given.

The table’s two useless rows are what makes the enumeration worth having. One of them is a function designed to have a large $c$ — $n$ times the first input, which one input controls entirely. The other is the longest run of heads, which looks innocuous: a run of ten heads has length ten, and flipping one bit in the middle of it leaves two runs of about five, so a single input moves the answer by five. The leverage is not visible in the definition and the enumeration is what finds it.

A quantity with no formula #

The point of the weaker hypothesis is the quantities it reaches, and the longest non-decreasing subsequence is a fair example. Draw $n$ values from a few options and ask for the length of the longest non-decreasing run one can pick out — not consecutive, just in order. There is no formula for its distribution, it is not a sum of independent anything, and its mean is known only asymptotically.

Changing one of the $n$ values changes the answer by at most one, because a chosen subsequence either uses the altered position or does not: if it does, dropping that one element leaves a valid subsequence one shorter. So $c_i = 1$ for every $i$, and the bound reads $2\exp(-2t^2/n)$ — the same as for a sum of $n$ coin flips.

That is a strong conclusion about a quantity nobody can compute. The mean is not known exactly; the bound says the quantity is within a few multiples of $\sqrt{n}$ of its mean with high probability, whatever the mean is. A statement of the form this unknown number is concentrated around its unknown mean is a great deal more useful than it sounds, because in practice the mean is estimated and the bound then controls the estimate.

Comparing the two tables says which of the four leverages is a property of the function and which is a property of its size. The longest non-decreasing run has $c = 1$ at every $n$, because the argument for it does not mention $n$. The sum’s is the range of one input, also independent of $n$. The two failures grow: the dictator’s is $n$ times the input range by construction, and the longest run of heads grows roughly like $n/2$.

That distinction is the practical test. A bound of this kind is useful exactly when $c$ does not grow with the number of inputs, because $\sum c_i^2$ is then $nc^2$ and the deviation scale is $c\sqrt{n}$ — small against the quantity’s own size. If $c$ grows like $n$ the scale is $n^{3/2}$, which is larger than anything the quantity can be, and the bound is vacuous by arithmetic rather than by bad luck.

So the question to ask about a new quantity is not whether it is a sum but whether one input’s effect stays bounded as the problem grows. For most quantities built by a local rule it does, and for quantities defined by a maximum over the whole input it often does not.

Where the hypothesis is used, and what it is not #

The proof is a martingale argument and the hypothesis enters at one point, which is worth locating because the located version is what generalises.

Reveal the inputs one at a time and track the conditional expectation of $f$ given what has been revealed. That sequence starts at $\mathbb{E}f$, ends at $f$, and each step is the change in the expectation caused by learning one input. The bounded-differences condition says each step lies in a range of width at most $c_i$ — and a sum of steps each confined to a small range concentrates, by an argument about exponential moments that needs nothing about the steps except their ranges and that each has conditional mean nought.

So the hypothesis used is bounded increments of a martingale, and bounded differences of $f$ is one way to get it. Independence of the inputs is what makes the conditional expectations easy to write down, and even that can be weakened.

That locating exercise is the reason the inequality has so many relatives. Replace the bound on the increments’ range by a bound on their conditional variances and the result is a sharper inequality; allow the increments to be unbounded with controlled tails and another; drop independence for a weaker mixing condition and another again. Each is the same argument with the one hypothesis it uses replaced, and the catalogue of concentration inequalities is a catalogue of ways to control a martingale’s increments.

What the bound does not know #

The bound reads one number about the function and is therefore blind to everything else. The longest run of heads is the instructive failure.

Its distribution is concentrated: the enumeration shows it sitting within a couple of values of its mean almost always. But one input can move it by about half the total, so $\sum c_i^2$ is large and the bound says nothing at all. The quantity concentrates and the inequality cannot see it, and no amount of computing helps, because the input the bound uses is already exact.

What is going on is that the large leverage exists only on configurations that are themselves very unlikely — a run of ten heads, in this case. The bound is a worst-case statement about the function and it charges the full price of the worst configuration to every configuration. The repairs available are exactly the ones the previous section lists: bound the conditional variance of the increments rather than their range, and the unlikely high-leverage cases stop dominating.

That is a general caution about worst-case hypotheses. A bound whose only input is a maximum over all inputs is pessimistic by construction, and the pessimism is unbounded: two functions with identical distributions can have wildly different $c$, so the bound is not a function of the distribution at all.

The rate, and where it comes from #

The bound’s shape is worth reading, because it is the same shape as every other bound here and for the same reason.

At $t = \lambda\sqrt{\sum c_i^2}$ the bound is $2e^{-2\lambda^2}$, so deviations are measured in units of $\sqrt{\sum c_i^2}$ — which for $n$ inputs of equal leverage is $c\sqrt{n}$. The scale is the square root of the number of inputs, exactly as it is for a sum and for a random walk, and the reason is the martingale: a sum of $n$ increments each of size about $c$ and each with conditional mean nought has typical size $c\sqrt{n}$, which is the walk’s own scale.

So the inequality says a complicated function of many inputs behaves, as far as its fluctuations go, like a random walk of $n$ steps. That is a strong statement about a wide class of quantities and it is worth being clear about what it does not say: nothing about the mean, nothing about the shape of the distribution — which is what the bell curve supplies at the cost of a hypothesis — and nothing better than $\sqrt{n}$ even when the truth is smaller.

Where it is used #

The chromatic number of a random graph. Reveal the vertices one at a time; adding or removing a vertex changes the number of colours needed by at most one. So the chromatic number is concentrated within $O(\sqrt{n})$ of its mean — a result nobody has any other route to, since the mean itself is known only approximately.

The cost of a heuristic on random input. The number of bins a packing heuristic uses, the length of a tour a greedy rule produces, the size of a matching found by a simple algorithm: each is a complicated function of independently drawn items, each changes by a bounded amount when one item is altered, and each concentrates for that reason alone. The colouring case is the one where four colours and a proof nobody can read meets probability: the number needed on a random graph is concentrated even though the number needed on a given graph is hard to compute.

Estimates whose distribution is unknown. Estimating a number by sampling needs an error bound, and when the estimator is an average the bound is Chebyshev’s or Hoeffding’s. When the estimator is something else — a median of medians, a trimmed mean, an output of a procedure — bounded differences applies where neither of those does.

A quantity where the count is the whole answer #

The other end of the scale is worth seeing, because it shows the bound being correct and unnecessary at once.

Count how many of three options appear among $n$ draws. Changing one draw changes the count by at most one, so $c = 1$ and the bound applies with the usual $\sqrt{n}$ scale. But the quantity lives in $\{1, 2, 3\}$ and is almost always three, so its true fluctuation is exponentially small in $n$ and the bound’s $\sqrt{n}$ scale is far larger than the range the quantity has.

A bound can be true, sharp in its own terms, and about the wrong scale. The $\sqrt{n}$ comes from adding $n$ increments each of size $c$, and for this quantity almost every increment is nought — the count stops changing once all three options have appeared. The repair is again the conditional variance: most increments have variance nought, so a bound reading variances rather than ranges gives the right scale and a bound reading ranges cannot.

That is the same failure as the longest-run case with the sign reversed. There the leverage was rare and large; here it is rare and small. Both are cases where a maximum over configurations is a poor summary of what typically happens, and both are why the catalogue has more than one entry.

What the pictures cannot show #

Everything here is enumerated, so everything here is at eight to twelve inputs. The interest of the inequality is at $n$ in the thousands, where no enumeration is possible and the bound is the only statement available — and where, by the $\sqrt{n}$ scaling, it is strongest.

The figures compute $c$ exactly and the bound from it, and they check the bound against the true tail at every deviation the distribution reaches. That is the strongest form of check available and it is a check at small $n$: the inequality is a theorem for every $n$ and the figures cannot establish it.

And the martingale is not drawn. The proof reveals the inputs one at a time and tracks a conditional expectation, which is a sequence of numbers depending on a partial input — an object with $2^n$ branches and no useful picture. What the figures show is the hypothesis and the conclusion, and the argument between them is prose.

Still open: how to charge for rare leverage #

The failure case above is the live question. A function whose large single-input effects occur only on unlikely configurations is badly served by a bound reading the maximum, and the known repairs each work for a class of cases rather than in general.

The sharpest available statements replace the range of each increment by a bound on its conditional variance, which gives inequalities of Freedman’s and Bernstein’s kind, and those handle the case where the leverage is typically small and occasionally large. What they need is a bound on the conditional variance, which for a complicated function is often no easier to obtain than the distribution itself.

The other direction concerns functions whose concentration is better than $\sqrt{n}$. Several natural quantities fluctuate on a scale much smaller than the square root — the longest increasing subsequence of a random permutation fluctuates like $n^{1/6}$, a result of considerable depth — and no general inequality of this kind produces such a rate. The bound’s $\sqrt{n}$ is the price of using only the increments’ ranges, and recovering a smaller exponent needs the problem’s own structure rather than a general principle.

The variance, for comparison #

One more quantity is worth computing for every function in the table, because it separates what the bound knows from what is true and does so in a single number.

The bound’s scale is $\sqrt{\sum c_i^2}$, and the quantity’s own standard deviation is something else entirely. For the sum of $n$ coin flips the two agree up to a constant: the scale is $\sqrt{n}$ and the standard deviation is $\sqrt{n}$. For the longest non-decreasing run the scale is $\sqrt{n}$ and the true standard deviation is smaller. For the count of options used the scale is $\sqrt{n}$ and the true standard deviation falls to nothing.

The ratio of the two is how much the bound is giving away, and it is computable whenever the distribution is. The figures report both — each panel’s mean and its single-input effect — so the comparison is on the page rather than implied.

What makes the ratio interesting rather than merely discouraging is that it has a cause in every case, and the cause is always the same: the bound charges every configuration the worst configuration’s leverage. Where the leverage is uniform the bound is nearly right; where it is concentrated on rare configurations the bound is loose; and the loss is exactly the variance of the leverage, which is the quantity the sharper inequalities read instead.

What the weakened hypothesis was worth #

A hypothesis is worth weakening when the weaker version is checkable and reaches more. Independence of a sum’s terms is checkable and reaches sums. Bounded differences is checkable — the figures check it by exhaustion — and reaches every quantity built from separately drawn inputs with no single input in charge.

The gain is not sharper bounds but a larger class, and the class is the one applications live in. Almost nothing anybody wants to bound is a sum: it is the output of a procedure, the size of a structure, the cost of a heuristic. Each is a function of its inputs, each has a computable leverage, and each concentrates for one reason.

The habit worth carrying is the one that produced the inequality. When a theorem’s hypothesis is stronger than its proof needs, find the step where the hypothesis is used and state that step instead — the result is a theorem with a stranger-looking condition and a much wider reach, and here the stranger-looking condition turned out to be the easier one to check.