Spread, moments and concentration

A mean is not the whole story

Suppose a factory ships bolts whose lengths are random. Two production lines both average ten millimetres. On line A the lengths cluster between 9.9 and 10.1; on line B they range from 9 to 11. If you must guarantee that a bolt fits a hole drilled to ten millimetres, the two lines are not interchangeable, and the mean alone cannot tell them apart. Something has to measure the spread around the centre.

Before there is a formula there is a picture. Imagine the probability mass of a distribution sitting on a weightless beam, one unit of total mass spread along the x-axis. The mean is the point where the beam balances — the centre of gravity. Spread is what a physicist would call the moment of inertia: it resists rotation about the balance point, and it grows not with distance but with the square of distance. A gram placed twice as far from the pivot contributes four times as much inertia. That single fact — squares, not distances — is the entire definition of variance, and it is why variance is additive in the clean way it is.

So the first move is to define the spread as the average squared distance from the mean. If X has mean $\mu=\mathbb{E}[X]$, then its variance is

The second equality is not obvious but it is pure algebra: expand the square, pull the expectation through the linear terms, and the cross term collapses because $\mu$ is a constant. The form $\mathbb{E}[X^2]-\mu^2$ is the one you compute with, because it needs only two numbers: the second moment and the mean.

The second move is to ask what the variance buys you. On its own it is a summary; used in an inequality it becomes a guarantee. If you know only the mean, Markov's inequality already caps how much probability can sit far to the right. If you know the mean and the variance, Chebyshev caps how much mass can be far from the centre in either direction. And if the variable is bounded, Hoeffding caps it far better than either. The rest of this part is the picture, the algebra, and those three caps.

Moving mass on a beam

The demo below is a beam with three lumps of probability mass on it. Drag a lump and the mean — the balance point — slides with it, while the variance tells you how much the arrangement resists a spin about that point. The grey parabola drawn behind the masses is the function $(x-\mu)^2$: it is the cost, in inertia, of placing a lump at position x. Each lump is shown with a stem up to the parabola, and the dot at the top of the stem has size proportional to how much mass is there. The variance is exactly the mass-weighted average height of those dots. Push the outer lumps together and the dots slide down the walls of the parabola; spread them out and the average height climbs.

That is the parallel-axis theorem in disguise. Physics splits the inertia of a rigid body into its inertia about the centre of mass plus the mass times the squared offset of the pivot. Probability does the same thing. The quantity $\mathbb{E}[X^2]$ is the inertia about the origin; subtracting $\mu^2$ moves the pivot to the centre of gravity. If you shift the whole distribution by a constant b, the spread does not change at all, because every distance to the new centre is the same as before. If you scale by a, every distance scales by |a| and every squared distance by a^2. Together,

The square root deserves attention because it repairs a unit mismatch. If X is measured in millimetres, then $X-\mu$ is in millimetres, its square is in square millimetres, and the variance carries units of area. The standard deviation $\sigma$ is back in millimetres, on the same scale as the data, and it is the number people quote. Variance is the thing that adds nicely; standard deviation is the thing that has the right units. Keep both, and use each where it is convenient.

Two boundary cases are worth naming. A constant has variance zero: all the mass sits at the mean, so every deviation is zero and the beam refuses to spin. At the other extreme a heavy-tailed distribution can have a mean but no finite variance, in which case $\mathbb{E}[X^2]$ diverges and the inertia is infinite. The Cauchy distribution is the standard example, and it is a warning that "the mean exists" and "the spread is finite" are separate facts. Every concentration bound below assumes the second moment is finite; when it is not, those guarantees simply do not apply.

Watch the two formulas agree while you drag. The readout reports $\mathbb{E}[X^2]-\mu^2$ and $\mathbb{E}[(X-\mu)^2]$ separately, and they track each other to the last digit. That is not a numerical coincidence; it is the algebraic identity doing exactly what it promised. It is also the reason variance is so much easier to handle than a raw average of absolute deviations: squares are differentiable, they separate into moments, and they turn the messy job of measuring spread into arithmetic on two expectations.

Spreads that add, and the term that spoils it

Expectation is linear with no strings attached, but variance is not, and the extra term is the interesting part. Start with the sum of two random variables. The deviation of X+Y from its mean is the sum of the two separate deviations, $(X-\mu_X)+(Y-\mu_Y)$. Square it and the cross term survives:

The new quantity, the covariance, measures whether the two variables tend to move together. If a large X comes with a large Y, the product of deviations is usually positive and covariance adds to the spread of the sum. If X is large exactly when Y is small, the product is usually negative, the cross term cancels some of the variance, and the sum is calmer than its parts. When the two are independent the covariance is zero, though zero covariance is weaker than independence: uncorrelated variables can still be dependent in a nonlinear way, and the independence part drew that distinction with two clouds of points.

For many variables the same expansion gives the full rule, $\operatorname{Var}(\sum_i X_i)=\sum_i\operatorname{Var}(X_i)+2\sum_{i<j}\operatorname{Cov}(X_i,X_j)$. Collect the pairwise covariances into a matrix $\Sigma$ whose (i,j) entry is $\operatorname{Cov}(X_i,X_j)$, and the variance of any weighted sum $w_1X_1+\cdots+w_nX_n$ is the quadratic form $w^\top\Sigma w$. That matrix is always symmetric, because swapping i and j does not change a covariance, and it is always positive semidefinite, because a variance can never be negative. Symmetry plus positive semidefiniteness is exactly the structure that symmetric matrices are built to handle: the eigenvectors of $\Sigma$ are the independent directions of variation, and its eigenvalues are the variances along them.

That is why the covariance matrix, not the list of individual variances, is the object that travels through statistics and machine learning. In a robotic filter the covariance records how uncertain the pose estimate is and in which directions; in a Gaussian process it is the kernel; in a linear model it is the shape of the parameter uncertainty. The next part of the guide builds the multivariate normal around exactly this matrix, and the discrete families after that show the covariances that fall out of familiar count distributions.

One practical corollary hides in the algebra. If you average n independent copies of X, each with variance $\sigma^2$, the covariances all vanish and the variance of the average is $\sigma^2/n$. Averages are less variable than their parts, and the spread shrinks like $1/\sqrt n$ — the same square-root law that governed the running frequency in Part 1. Add another n observations and the standard error improves not by a factor of two but by a factor of $\sqrt2$, which is why data is precious and why the tail bounds in the next section scale with n in the exponent.

Markov, Chebyshev, Hoeffding, Chernoff

A tail probability is usually hard: it asks for the area under a density far out in the shoulder, where no closed form may exist and where simulation rarely lands. A concentration bound replaces the exact tail with a guarantee that needs only a few numbers about the distribution. The first such guarantee is the crudest and the most general.

Markov's inequality applies to any non-negative random variable and uses only its mean: for a>0, $P(X\ge a)\le\mathbb{E}[X]/a$. It is true for a reason you can see. A variable that is at least a whenever it exceeds a already contributes a to its own mean in that event; if the probability of exceeding a were more than $\mathbb{E}[X]/a$, the mean would have to be larger than it is. The bound is loose, but it requires nothing.

Chebyshev's inequality is Markov applied to the non-negative variable $(X-\mu)^2$. The event $|X-\mu|\ge t$ is the same as $(X-\mu)^2\ge t^2$, and the mean of that square is exactly $\sigma^2$, so $P(|X-\mu|\ge t)\le\sigma^2/t^2$. Two consequences are worth memorising. No distribution with finite variance can put more than 1/4 of its mass beyond two standard deviations, and no more than 1/9 beyond three, no matter how strange its shape. The sandwich shop, the stock return, and the sensor noise all obey the same ceiling.

Both bounds decay like 1/t^2, which is slow. For thin-tailed variables that is wasteful: the true normal tail beyond three standard deviations is about 0.0027, while Chebyshev still allows 0.111, forty times larger. If the variable is bounded, the tail collapses exponentially instead. Hoeffding's inequality says that if X lies in an interval of length b-a, then the average of n independent copies obeys

The exponent grows with n, so the bound decays like a Gaussian in the deviation and like e^{-n} in the sample size — this is the sharp-looking engine underneath the law of large numbers. Chernoff bounds are the general recipe behind it: for any s>0, Markov on the variable e^{sX} gives $P(X\ge a)\le e^{-sa}\mathbb{E}[e^{sX}]$, and one then chooses s to make the right side as small as possible. Hoeffding is what that optimisation produces for bounded variables; for a sum of Bernoullis it produces the binomial Chernoff bound, the workhorse of learning theory. The price of the exponential decay is a stronger assumption: you must know the variable is bounded, or know its moment-generating function converges in a neighbourhood of zero.

The demo below is the honest picture of these claims. It draws the true tail $P(|X-\mu|\ge t)$ for a distribution you choose, and lays the Markov and Chebyshev bounds on top of it so you can see the gap with your own eyes. Pick the two-point (bounded) distribution and Hoeffding joins in, tight against the true tail and decaying far faster than the other two. Switch on the log scale to watch an exponential bound separate from a polynomial one.

Why care about bounds that are visibly loose? Because they hold when nothing else does. Chebyshev needs two numbers and no distributional assumption; it is the reason a sample mean is a defensible estimate of a population mean before you have any idea what the population looks like. Hoeffding needs a range and independence; it is the reason a bounded average concentrates. And the Chernoff recipe, applied to losses instead of coordinates, becomes a generalisation bound: the gap between training error and test error is a tail probability of an average, and you bound it with exactly the machinery on this canvas. The scaling picture of training is ultimately a statement about how quickly such averages concentrate as models and data grow.

Spread and its bounds, in practice

Every formula in one place

Where to go deeper

• William Feller, An Introduction to Probability Theory and Its Applications, volume I — the moment of inertia picture and the classical inequalities, developed with the same physical instinct.
• Geoffrey Grimmett and David Stirzaker, Probability and Random Processes, chapters 3 and 5 — variance, covariance and the elementary concentration inequalities, with exercises.
• Wassily Hoeffding, "Probability Inequalities for Sums of Bounded Random Variables", JASA, 1963 — the original paper and the sharpest version of the bound that carries his name.
• Herman Chernoff, "A Measure of Asymptotic Efficiency for Tests of a Hypothesis", Annals of Mathematical Statistics, 1952 — where the exponential-moment technique first appears.
• Martin Wainwright, High-Dimensional Statistics, chapter 2 — concentration inequalities collected and proved, for readers headed toward learning theory.