Tails, heavy tails, and high dimensions

When does the average mislead?

Take a pile of numbers and average them. This is the most trusted move in all of statistics, and it is trusted for a reason: independent errors cancel, the mean lands near the centre, and the spread of that landing shrinks as the sample grows. Part 17 made the convergence precise and Part 18 made the fluctuation Gaussian. Both results are about the same quantity, $\bar X_n = (X_1+\cdots+X_n)/n$, and both quietly assume that the thing being averaged has a finite variance.

The Cauchy distribution is the cleanest counterexample. Its density is a symmetric bump peaked at x_0, but its tails decay only like 1/x^2, so slowly that $\mathbb{E}|X|$ diverges and the mean is not a number at all. Average n independent Cauchy draws and you get a Cauchy variable back — not approximately, exactly, and with the same width. Watch the running mean of such a sequence and it will not settle; at any scale you choose, it can still lurch. The average is not a worse estimator here. It is simply not an estimator of anything.

The interesting question is not whether heavy tails exist but how far the damage spreads. The central limit theorem's requirement of finite variance is sharp: no finite-variance distribution violates it, and the Cauchy shows the failure when the requirement is dropped. Yet the two facts that people actually want from the CLT — a small deviation probability and a shrinking error — survive in weaker form for much heavier tails than the Gaussian's, as long as we replace the exact normal approximation with an inequality. Hoeffding and Chernoff bounds keep the exponential decay; Chebyshev, which knows only the variance, loses it.

Then there is the dimension. The law of large numbers and the CLT both live in $\mathbb{R}$, and it is tempting to apply them coordinate by coordinate in $\mathbb{R}^d$. Usually that is fine. But the geometry they describe is not merely higher-dimensional — it is qualitatively different. Distances between independent random points in $\mathbb{R}^d$ concentrate as d grows: the relative spread of pairwise distances falls like $1/\sqrt{d}$, so in a hundred dimensions essentially every pair is the same distance apart. Nearest neighbours stop being near, and the notion of "close" that a whole class of algorithms relies on begins to dissolve.

This part takes the three failures in order — undefined means, polynomial tails, and the geometry of large d — and shows for each one what still works and what must be given up.

The average that refuses to settle

A distribution is called heavy-tailed when its survival function P(X>x) decays slower than any exponential. The Gaussian's tail dies like e^{-x^2/2}; the exponential dies like $e^{-\lambda x}$; the Cauchy dies like 1/x, and its density like 1/x^2. That is not a small difference in the fourth decimal place. It means that the probability of an observation a thousand standard deviations from the centre is, for the Cauchy, not negligible at all — and that one such observation can single-handedly move an average.

The Cauchy density with location x_0 and scale $\gamma$ is the bell-shaped curve

Its median is x_0 and its quartiles are $x_0\pm\gamma$, so it is perfectly well behaved near the middle. All of the trouble lives in the tails. The integral defining $\mathbb{E}|X|$ diverges logarithmically, which is the slowest possible divergence of that kind, and it is exactly what makes the sample mean useless. The stable law that the Cauchy belongs to has the same shape after averaging: if $X_1,\dots,X_n$ are independent Cauchy with parameters $(x_0,\gamma)$, then

Read that again: the running mean has the same distribution at n=1 and at n=10^6. There is no concentration at all. The CLT cannot apply even in spirit, because its normalisation $\sqrt{n}$ would have to be replaced by n — the mean is already invariant under adding more data, so no rescaling of it can produce a limit theorem. This is the heaviest possible failure of the averaging principle, and it comes with an intuitive picture: a single sample can be so large that it dominates the sum, the next sample can dominate in the other direction, and the sequence of averages never forgets.

The picture is worth pausing over. The median absolute running mean of a standard Cauchy sits at about 1 for every sample size, because the median of |X| for a standard Cauchy is $\tan(\pi/4)=1$. The individual pale traces are not converging toward zero: they make enormous jumps at unpredictable times, and each jump happens because one new observation was comparable to the whole previous sum. The magenta normal running mean, by contrast, is pinned down almost immediately — by n=4000 it is inside a band a hundredth of a unit wide.

Heavy tails are not exotic. The ratio of two independent normals is Cauchy, which is why a least-squares estimate can jump when a measurement error happens to be near zero in the denominator. Log returns of financial assets, the sizes of cities, and the distances between stars in a cluster are all closer to power laws than to Gaussians. The practical lesson is not "never average" but "know the tail": a trimming or median-based estimator, which ignores the largest few observations, is $\sqrt{n}$-consistent for the Cauchy centre while the mean is not consistent at all. The continuous families part sets the Student-t family alongside the Gaussian, and the Student-t is exactly the dial that turns a light tail into a heavy one: at $\nu=1$ it is the Cauchy, at $\nu\to\infty$ it is the normal.

Exponential fall-off without a Gaussian

The CLT is an asymptotic statement with a sharp hypothesis: it needs $\sigma^2<\infty$. Part 18 made the requirement visible through Berry–Esseen, where the error to the normal limit is controlled by the third absolute moment. For a bounded variable there is no problem at all — and that is the setting in which a much more robust tool is available. Instead of asking what the distribution of the mean looks like, ask only how fast a specified tail can decay. A tail bound does not need to know the distribution, and it works at every finite n, not just in the limit.

The engine is Markov's inequality applied to an exponential. For any $\theta>0$, the event $X\ge t$ implies $e^{\theta X}\ge e^{\theta t}$, so by Markov,

This is the Chernoff bound. It is valid for every $\theta$ and is made as tight as possible by minimising the right-hand side over $\theta$. Its power comes from using the whole moment generating function, not just the variance. If the mgf exists in a neighbourhood of zero the bound decays exponentially in t; if the mgf fails to exist, so does the bound, which is exactly how a heavy tail announces itself.

For an average of bounded independent variables $X_i\in[a,b]$ with mean $\mu$, the mgf estimate $M(\theta)\le e^{\theta^2(b-a)^2/8}$ gives Hoeffding's inequality after optimising $\theta$:

For a Bernoulli variable the bound can be sharpened to the exact large-deviation rate. With $p=\mathbb{E}[X]$ and t>p, the Chernoff exponent is the relative entropy $D(t\,\|\,p)=t\log(t/p)+(1-t)\log((1-t)/(1-p))$, so

Chebyshev, by contrast, knows only the variance and can say nothing better than $P(|\bar X_n-\mu|\ge t)\le p(1-p)/(nt^2)$, which decays like 1/n. That is a polynomial where Chernoff is exponential: at moderate t the two differ by orders of magnitude, and the gap grows without bound as t moves away from the mean. The demo plots all three on a logarithmic vertical axis so that exponential decay appears as a steeply falling curve and polynomial decay as a shallow line.

Notice where the curves cross. Close to the mean, Chebyshev can be competitive, because there the true tail is nearly one half and any bound that stays below 1 is doing something. Move away from the mean and Chebyshev falls off a cliff edge that never comes: it keeps returning a number in the hundredths while the truth is already in the millionths. Chernoff tracks the true exponent almost exactly for the Bernoulli — the gap between the teal and magenta curves is a constant factor, not a growing one — because the large-deviation rate $D(t\,\|\,p)$ is the exact exponent of the binomial tail. This is the sense in which bounds replace the CLT: they give up the claim that the fluctuation is Gaussian, and in exchange they hold for every n, for every bounded distribution, and with an error the CLT never had.

In a hundred dimensions, everyone is the same distance apart

Sample two points independently from the standard Gaussian in $\mathbb{R}^d$. Each coordinate of the difference is N(0,2), so the squared distance is a sum of d independent, identically distributed terms. Its mean is 2d, its variance is proportional to d, and so the distance itself is a fluctuating quantity with mean about $\sqrt{2d}$ and standard deviation about a constant. The relative spread therefore shrinks like $1/\sqrt{d}$. This is the same $1/\sqrt{n}$ averaging story as before, applied not to a statistic but to a geometric quantity.

The inequality is the quantitative version of the picture: distance is concentrated. Pick any tolerance $\varepsilon$, and the probability that a random pair's distance is off by more than a fraction $\varepsilon$ of the typical distance falls exponentially in the dimension. In two dimensions the distances between random points range from nearly zero to several times the mean; in a hundred dimensions almost every pair sits within a few percent of the same value; in five hundred, to within a fraction of a percent. There is no analogy in low dimensions. The intuition that "near" means "in the same neighbourhood" is a two- and three-dimensional habit, and it quietly stops being true.

Two consequences are worth naming. First, the contrast between the average distance and the extreme ones: the ratio plotted on the second canvas falls by roughly two orders of magnitude between d=2 and d=100, and the failure of "nearest" and "farthest" to mean anything distinct is exactly this collapse. Second, the concentration is not a Gaussian fact. Any distribution with light tails and independent coordinates concentrates just as sharply; heavy tails break it precisely as they broke the mean in the previous sections, which is why the dimension and the tail are usually discussed together. When both are in play — heavy tailed coordinates in high dimensions — the distances can spread again, and methods that assume concentration fail.

This is the mathematics behind the so-called curse of dimensionality, and it is the reason the scaling laws of language models and the robust fitting of vision geometry care about the effective dimension of their data rather than the raw count of features. If the intrinsic dimension is low — the data lies near a low-dimensional manifold — concentration is weak and neighbourhood methods work. If it is high, distances become uninformative and every algorithm that ranks points by proximity has to be repaired. The central limit theorem part shows the same $1/\sqrt{n}$ collapse for the sample mean, one dimension at a time; this section is what happens when "one dimension at a time" is not enough.

Tails and dimension in practice

Every formula in one place

Where to go deeper

• William Feller, An Introduction to Probability Theory and Its Applications, vol. II — stable laws and the Cauchy as the canonical example where the CLT fails.
• Roman Vershynin, "High-Dimensional Probability", 2018 — concentration of measure done carefully, with the sub-Gaussian toolkit in chapters 2–3.
• Michel Ledoux, The Concentration of Measure Phenomenon, 2001 — the geometric view of concentration used in section 4.
• Terence Tao, "254A Notes 1: Concentration of measure" — a compact tour from Chernoff to the concentration of Lipschitz functions.
• Wikipedia, "Cauchy distribution" and "Chernoff bound" — quick statements of every formula on this page.