Berry–Esseen: The Central Limit Theorem With a Rate

The CLT tells you the average is asymptotically Gaussian. It says nothing about how close you actually are at your finite sample size. Berry–Esseen fills the gap — with an explicit constant, a rate that is provably tight, and (if you use Stein's method to prove it) an argument that feels geometric rather than analytic.

The lie about "n = 30"

Every statistics course teaches the Central Limit Theorem, and most of them follow it with a bit of folk wisdom: "n = 30 is usually enough." This is not a theorem. It's a rule of thumb about the visual appearance of a histogram. The question a working statistician actually cares about is:

How large does n need to be so that my Gaussian approximation is wrong by at most ε?

That "wrong by at most ε" needs a distance. The natural choice is the Kolmogorov distance — the supremum over all thresholds of the absolute gap between the empirical CDF and the Gaussian CDF.

Let me set notation. Let $X_1, \ldots, X_n$ be iid with mean $0$, variance $\sigma^2$, and finite third absolute moment $\rho := \mathbb{E}|X|^3 < \infty$. Let $S_n = (X_1 + \cdots + X_n)/(\sigma\sqrt n)$ be the standardized sum. The classical CLT says the CDF $F_n(x) := \mathbb{P}(S_n \le x)$ converges pointwise to $\Phi(x)$, the standard normal CDF. That's a statement about the limit. Berry–Esseen upgrades it to a statement about every finite $n$.

Berry–Esseen, precisely

Independently in 1941–42, Andrew Berry and Carl-Gustav Esseen proved:

Under the hypotheses above,

In words: the worst-case gap between the CDF of your normalized sum and the standard normal CDF shrinks like $1/\sqrt n$, with a prefactor that is a universal constant $C$ times a scale-free measure of the third moment. The quantity $\rho/\sigma^3$ is the standardized third absolute moment — for a symmetric, well-behaved distribution it is small; for something spiky and skewed, it is large.

Two things to notice.

The rate $1/\sqrt n$ is tight. For $X \sim \text{Bernoulli}(1/2)$ — a fair coin flip — the CDF is a staircase with jumps of size $\approx 1/\sqrt n$, and no smooth $\Phi$ can shadow those jumps to better than that order. So no proof, no matter how clever, can beat $1/\sqrt n$ uniformly over $x$ for arbitrary distributions.

The constant $C$ is a decades-long story. Esseen's 1942 bound had $C = 7.59$. Successive tightenings have brought it down; the best known value for the iid case is $C \le 0.4748$ (Shevtsova, 2011). The best known lower bound is $(\sqrt{10}+3)/(6\sqrt{2\pi}) \approx 0.4097$ (Esseen, 1956). The true optimal $C$ is trapped in a narrow band and remains an open problem.

A worked example

Take $X$ = $\pm 1/2$ each with probability $1/2$ (a mean-zero coin flip). Then $\sigma^2 = 1/4$, so $\sigma = 1/2$; and $\mathbb{E}|X|^3 = 1/8$, so $\rho = 1/8$. The ratio $\rho/\sigma^3$ is $(1/8)/(1/8) = 1$. Berry–Esseen with the Shevtsova constant then says

At $n = 30$, that's $\approx 0.087$. At $n = 100$, $\approx 0.047$. At $n = 1000$, $\approx 0.015$. So if you want your Gaussian approximation correct to within one percentage point uniformly across the axis, you need thousands of coin flips, not thirty. The folk wisdom is wildly optimistic in the tails.

Stein's characterization of the normal

The most beautiful modern proof of Berry–Esseen — and the one worth walking through — is due to Charles Stein, in a 1972 Berkeley symposium paper that reframed the whole question. He noticed something almost too simple to believe:

A real random variable $Z$ is standard normal if and only if $\mathbb{E}[f'(Z) - Z f(Z)] = 0$ for every absolutely continuous $f$ with $\mathbb{E}|f'(Z)| < \infty$.

Here $Z$ is our candidate variable; $f$ is any smooth test function; $f'(Z)$ is its derivative evaluated at $Z$; and the "for every $f$" is the strong part. The forward direction is one line of integration by parts against the Gaussian density $\phi(x) = (1/\sqrt{2\pi})\exp(-x^2/2)$, using the identity $\phi'(x) = -x\,\phi(x)$:

The converse — that this identity forces $Z$ to be standard normal — is what Stein turned into a distance.

The Stein equation

If being close to normal is equivalent to $\mathbb{E}[f'(Z) - Z f(Z)]$ being small for a wide class of $f$, then to bound the distance-from-normal of some $W$, we should try to bound $\mathbb{E}[f'(W) - W f(W)]$ over that class.

The engineering step is the Stein equation. For a test function $h$ (say the indicator $\mathbf{1}_{x \le a}$), find $f$ solving

An explicit solution exists:

This is where the load is carried, so it's worth staring at. The right-hand side is exactly the quantity whose expectation we want to bound: taking expectations under the law of $W$ gives $\mathbb{E}[h(W)] - \mathbb{E}[h(Z)] = \mathbb{E}[f'(W) - W f(W)]$. So a bound on a distance-from-normal quantity for $h$ has been converted into a bound on a distance-from-normal quantity for $f' - x f$, and $f$ is a function whose smoothness we can control. When $h$ is an indicator (which is what you want for Kolmogorov distance), one shows $\|f'\|_\infty \le 2$ and $\|f''\|_\infty \le \sqrt{2/\pi}$.

That controlled smoothness is what makes the technique powerful. We have traded a nasty comparison (CDF gaps against a discontinuous indicator) for a smooth one (integrals of a Lipschitz function) at bounded cost.

The load-bearing step: leave-one-out

Now let $W = (X_1 + \cdots + X_n)/(\sigma\sqrt n)$ and expand $\mathbb{E}[W f(W)]$ by pulling one summand at a time. Write $W = W^{(i)} + X_i/(\sigma\sqrt n)$, where $W^{(i)}$ is the leave-one-out sum (drop $X_i$, keep the same normalization). Then

Because $X_i$ is independent of $W^{(i)}$ and has mean zero, $\mathbb{E}[X_i\, f(W^{(i)})] = 0$. So only the increment matters. Taylor-expand $f(W)$ around $W^{(i)}$:

with $|R_i| \le \tfrac{1}{2} \|f''\|_\infty (X_i/(\sigma\sqrt n))^2$. Multiply by $X_i$, take expectation, sum over $i$, and match against $\mathbb{E}[f'(W)]$. The zeroth-order term vanishes by independence. The first-order terms aggregate — using $\mathbb{E}[X_i^2] = \sigma^2$ — to $\mathbb{E}[f'(\text{something close to }W)]$, and a further Taylor step closes the loop with $\mathbb{E}[f'(W)]$ itself.

The remainders are where $\rho = \mathbb{E}|X|^3$ enters. Each $R_i$ contributes $O(\|f''\|_\infty \mathbb{E}|X_i|^3 / (\sigma^3 n^{3/2}))$; summing over $i$ gives exactly the $\rho/(\sigma^3 \sqrt n)$ prefactor Berry–Esseen advertises. The universal constant $C$ absorbs $\|f'\|_\infty$ and $\|f''\|_\infty$ from the Stein equation.

That is the whole architecture. No characteristic functions, no Fourier inversion, no complex-analytic delicacy. The intuition — that swapping one summand at a time moves $W$ by $O(1/\sqrt n)$, and the third-moment control tells you the swap-error can't accumulate faster than that — is exactly what the arithmetic confirms.

What Berry–Esseen does not tell you

Berry–Esseen is a uniform bound. It is sharp in the bulk and pessimistic in the tails. If you're trying to estimate a rare-event probability like $\mathbb{P}(S_n \ge 5)$ — a quantity of order $10^{-7}$ — a Berry–Esseen error of $0.5/\sqrt n$ utterly dwarfs the thing you're estimating. In that regime you want large-deviation theory: Cramér's theorem (1938) gives $\mathbb{P}(S_n/n \ge a) = \exp(-n I(a) + o(n))$ for the rate function $I(a) = \sup_\theta \{\theta a - \log \mathbb{E}[e^{\theta X}]\}$. The CLT is about the $O(1/\sqrt n)$ window around the mean; Cramér governs everything else.

Going the other direction, in the bulk one can do better than $1/\sqrt n$ with Edgeworth expansions: adding a skewness correction of order $1/\sqrt n$ (involving $\mathbb{E}[X^3]$ and Hermite polynomials) drops the residual to $O(1/n)$ — provided the summands are non-lattice, which the fair coin isn't. And local CLTs bound the pointwise density $f_{S_n}(x)$ against $\phi(x)$, at the cost of requiring smoothness on the summand distribution.

Finally: the whole Berry–Esseen story assumes a finite third moment. Drop that and the CLT itself changes shape. Sums of heavy-tailed variables with $\mathbb{E}|X|^2 = \infty$ converge to $\alpha$-stable laws, not to a Gaussian, and the rate question becomes entirely different — Kolmogorov distance need not shrink polynomially in $n$ at all. That's a different post.

But when the third moment exists, Berry–Esseen is what you want in your pocket. The CLT tells you the destination; Berry–Esseen tells you when you have plausibly arrived.