The central limit theorem

The law of large numbers says that an average settles at the expectation, and the variance says that its typical distance from it is $\sigma/\sqrt n$. The central limit theorem says much more: the shape of the fluctuations is almost always the same, the normal bell, whatever the distribution of the individual terms. A sum of exponential waiting times, a count of clicks, an average loss over a validation set and a measurement error made of many small disturbances are all close to normal. This is why the normal distribution is everywhere, and why error bars are computed from it.

Notation. $X_1, X_2, \dots$ are i.i.d. with mean $\mu$ and finite variance $\sigma^2 > 0$; $S_n = X_1 + \dots + X_n$ and $\bar X_n = S_n / n$. $Z_n = \sqrt n (\bar X_n - \mu)/\sigma = (S_n - n\mu)/(\sigma\sqrt n)$ is the standardized average; $\Phi$ is the standard normal CDF.

The theorem#

For every $z$,

$$P(Z_n \le z) \to \Phi(z) \quad \text{as } n \to \infty .$$

The standardized average converges in distribution to $N(0, 1)$. Undoing the standardization, for large $n$

$$\bar X_n \approx N\Big(\mu, \frac{\sigma^2}{n}\Big), \qquad S_n \approx N(n\mu, n\sigma^2) .$$

The only assumptions are independence, identical distribution and a finite variance. The terms can be discrete or continuous, symmetric or skewed. A single exponential variable is strongly skewed; standardized sums of a few of them already look much more symmetric:

Figure

A sum of exponential variables becomes normal

Why the normal#

Optional depth: a proof of the theorem with characteristic functions. The rest of the note does not depend on it.

The characteristic function explains the result in four lines. Let $Y_i = (X_i - \mu)/\sigma$, with mean 0 and variance 1, so that $Z_n = (Y_1 + \dots + Y_n)/\sqrt n$. For independent terms the characteristic function of the sum is the product of theirs:

$$\psi_{Z_n}(t) = \Big(\psi_Y\big(t/\sqrt n\big)\Big)^n .$$

Near 0, a characteristic function with mean 0 and variance 1 expands as $\psi_Y(s) = 1 - s^2/2 + o(s^2)$. Substituting $s = t/\sqrt n$,

$$\psi_{Z_n}(t) = \Big(1 - \frac{t^2}{2n} + o\big(\tfrac1n\big)\Big)^n \to e^{-t^2/2} ,$$

which is the characteristic function of $N(0, 1)$. Lévy’s continuity theorem turns convergence of characteristic functions into convergence of distributions. The computation also shows why the limit is universal: after standardization, only the first two terms of the expansion survive, and they are the same for every distribution with a finite variance. The remainder $o(s^2)$ needs nothing beyond the finite variance, and the argument gives no rate: with only a finite variance the convergence can be arbitrarily slow. Higher moments need not even exist. When the third absolute moment is finite, the Berry–Esseen theorem below bounds the error by order $1/\sqrt n$; when more moments are finite and the terms do not live on a lattice, finer (Edgeworth) expansions show the skewness entering at order $1/\sqrt n$ and the kurtosis at order $1/n$.

Error bars#

The theorem turns the $1/\sqrt n$ rule into probabilities. Since $\bar X_n$ is approximately $N(\mu, \sigma^2/n)$, the interval

$$\bar X_n \pm 1.96\, \frac{\sigma}{\sqrt n}$$

contains $\mu$ with probability close to $0.95$. A classifier that scores 0.9 on 1,000 independent test examples has an error bar of $\pm 1.96 \sqrt{0.9 \cdot 0.1/1000} = \pm 0.019$. For an A/B test of click rates 2.0% and 2.3% with 20,000 users in each group, the difference has standard error

$$\sqrt{\frac{0.02 \cdot 0.98}{20{,}000} + \frac{0.023 \cdot 0.977}{20{,}000}} = 0.00145 ,$$

so the observed difference of $0.003$ is $2.07$ standard errors from zero; if the two true rates were equal, a difference at least that large in either direction would arise with probability $0.039$. The confidence intervals note and the hypothesis tests note make these two statements precise and list what they do not mean.

The binomial. A binomial count is a sum of independent indicators, so $\mathrm{Bin}(n, p) \approx N(np, np(1-p))$, the de Moivre–Laplace theorem and the first version of the central limit theorem, going back to the 18th century. For 60 or more heads in 100 fair flips, the exact probability is $0.0284$; the normal approximation $P(Z \ge 2) = 0.0228$ is off because a discrete count is approximated by a continuous variable. Counting the bar at 60 from its left edge, $P(Z \ge (59.5 - 50)/5) = 0.0287$, almost removes the error; this continuity correction is standard for counts.

How fast#

The theorem is a limit, and $n$ is always finite. The Berry–Esseen theorem bounds the error in the CDF for every $n$:

$$\sup_z \big\lvert P(Z_n \le z) - \Phi(z) \big\rvert \le \frac{C\, E\lvert X - \mu \rvert^3}{\sigma^3 \sqrt n}, \qquad C \le 0.4748 .$$

The bound falls like $1/\sqrt n$, and its size is set by the standardized third absolute moment, which grows with both asymmetry and heavy tails. For the sums of exponentials in the figure, the largest gap is $0.159$ for $n = 1$ and $0.024$ for $n = 30$. Tails converge slowest: for the sum of 30 exponentials, $P(Z_n > 2) = 0.032$ against $0.023$ for the normal.

Skewed and rare-event counts need large $n$. For $\mathrm{Bin}(1000, 0.001)$, with mean 1, the probability of zero events is $0.368$, and the normal approximation with continuity correction gives $0.308$; the Poisson approximation is the right one there. A common rule of thumb asks for $np$ and $n(1-p)$ of at least about 10 before using the normal approximation for a proportion.

Modes of convergence#

The law of large numbers and the central limit theorem use different kinds of convergence, and the differences matter when reading statements about estimators and algorithms.

• Almost surely: $P(X_n \to X) = 1$; the realized sequence converges with probability 1. The strong law of large numbers.
• In mean square: $E[(X_n - X)^2] \to 0$. The variance proof of the law of large numbers, and the usual statement for estimators.
• In probability: $P(\lvert X_n - X \rvert \ge \varepsilon) \to 0$ for every $\varepsilon$. The weak law of large numbers, and consistency of estimators.
• In distribution: $P(X_n \le x) \to P(X \le x)$ at every point where the limit CDF is continuous. The central limit theorem.

Figure

Modes of convergence of random variables

Convergence in distribution is the weakest: it says nothing about the random variables themselves, only about their distributions. The standardized averages $Z_n$ do not approach any particular random variable; $Z_n$ and $Z_{2n}$ are only partly correlated however large $n$ is. The law of large numbers note showed an example of convergence in probability without almost sure convergence; a sequence that converges in distribution to $X$ but not in probability to $X$ is $X_n = -X$ for a standard normal $X$, which has the distribution of $X$ for every $n$ and never comes close to $X$ itself. It does converge in probability, to $-X$. A sequence with no limit in probability at all is $X_n = (-1)^n X$: every $X_n$ is standard normal, so it converges in distribution, but $X_{n+1} - X_n = \pm 2X$ never shrinks.

When the theorem fails#

• Infinite variance. The average of $n$ standard Cauchy variables is again standard Cauchy; nothing becomes normal. For tails like $x^{-\alpha}$ with $1 < \alpha < 2$ sums do converge after centring and rescaling, but by $n^{1/\alpha}$ instead of $\sqrt n$ and to a heavy-tailed stable distribution rather than the normal.
• A few terms dominate. For independent but not identically distributed terms, the Lindeberg condition requires that no single term carries a non-negligible share of the total variance. A sum of one huge measurement error and many small ones has the shape of the huge one.
• Strong dependence. Weakly dependent sequences, such as most Markov chains, still satisfy a central limit theorem with a different, usually inflated, variance; strongly dependent ones, for example sums of a slowly varying trend, need not.

What changed#

	Law of large numbers	Central limit theorem
Statement	$\bar X_n \to \mu$	$\sqrt n(\bar X_n - \mu)/\sigma \to N(0, 1)$ in distribution
What it gives	where the average goes	the shape and size of its fluctuations
Use	consistency, Monte Carlo	error bars, tests, the normal approximation to counts
Rate		Berry–Esseen: CDF error $\le 0.4748\, E\lvert X - \mu\rvert^3 / (\sigma^3\sqrt n)$

Limitations#

• “Large $n$” depends on the distribution. Skewed terms, rare events and tail probabilities need much larger samples than the bell shape near the centre suggests.
• Independence is the strongest assumption. Clustered data (several examples per user, per document, per hospital) make the real standard error larger than $\sigma/\sqrt n$; error bars must then be computed per cluster.
• The theorem is about sums. Statistics that are not sums need their own analysis; a maximum, for instance, converges to an extreme-value distribution, not to a normal.

What you should remember#

• For i.i.d. terms with finite variance, $\sqrt n(\bar X_n - \mu)/\sigma \to N(0, 1)$ in distribution: $\bar X_n \approx N(\mu, \sigma^2/n)$.
• Only the mean and the variance of the terms matter in the limit; finite variance alone gives no rate, and with a finite third absolute moment the CDF error is of order $1/\sqrt n$ (Berry–Esseen).
• Error bar of an average: $\pm 1.96\, \sigma/\sqrt n$ for about 95%; for counts, use the continuity correction.
• Berry–Esseen: the CDF error is at most $0.4748\, E\lvert X - \mu\rvert^3/(\sigma^3\sqrt n)$; tails and skewed terms converge slowly.
• Almost surely or in mean square ⇒ in probability ⇒ in distribution; the CLT is a statement in distribution.
• No finite variance (Cauchy, heavy tails), dominating terms or strong dependence break the theorem.

Code#

The figure’s gaps from exact gamma distributions, the error bars, the normal approximation to the binomial, and a simulation:

import numpy as np, math
from scipy import stats

# standardized sums of n exponentials: the largest CDF gap to the normal, and P(Z > 2)
for n in (1, 2, 5, 30):
    S = stats.gamma(n)                                             # the sum of n independent Exp(1)
    z = np.linspace(-6, 8, 140_001)
    gap = np.abs(S.cdf(n + math.sqrt(n) * z) - stats.norm.cdf(z)).max()
    print(n, round(float(gap), 3), round(float(S.sf(n + 2 * math.sqrt(n))), 4))
print(round(float(stats.norm.sf(2)), 4))
# 1 0.159 0.0498 | 2 0.094 0.0466 | 5 0.06 0.041 | 30 0.024 0.0316 | normal 0.0228

# error bar for accuracy 0.9 on 1,000 examples; A/B test of click rates 2.0% and 2.3%, 20,000 users each
print(round(1.96 * math.sqrt(0.9 * 0.1 / 1000), 4))               # 0.0186
se = math.sqrt(0.02 * 0.98 / 20_000 + 0.023 * 0.977 / 20_000)
print(round(se, 5), round(0.003 / se, 2), round(float(2 * stats.norm.sf(0.003 / se)), 3))   # 0.00145 2.07 0.039

# 60 or more heads in 100 flips: exact, normal, normal with continuity correction
print(round(float(stats.binom(100, 0.5).sf(59)), 4), round(float(stats.norm.sf(2)), 4), round(float(stats.norm.sf(1.9)), 4))   # 0.0284 0.0228 0.0287

# a rare event is far from normal: Bin(1000, 0.001), P(X = 0) exact and by the normal approximation
print(round(float(stats.binom(1000, 0.001).pmf(0)), 3), round(float(stats.norm.cdf(-0.5 / math.sqrt(0.999))), 3))   # 0.368 0.308

# simulation: standardized sums of 30 exponentials
rng = np.random.default_rng(0)
s = (rng.exponential(size=(200_000, 30)).sum(axis=1) - 30) / math.sqrt(30)
print(round(float((np.abs(s) < 1.96).mean()), 4), round(float((s > 2).mean()), 4))   # 0.9522 0.0311

Next#

The limit theorems are about averages of samples from a known distribution. Statistics turns the question around: from the samples, what can be said about the distribution? The next note opens the section on statistics with estimators, the functions of data that guess a parameter, and the bias, variance and mean squared error that measure how well they do it.

References#

• J. K. Blitzstein, J. Hwang. Introduction to Probability, 2nd ed. CRC Press, 2019. Chapter 10 (the central limit theorem).
• W. Feller. An Introduction to Probability Theory and Its Applications, Vol. 2, 2nd ed. Wiley, 1971. Chapter XV (characteristic functions and the central limit theorem), Chapter XVI (Berry–Esseen).
• A. N. Shiryaev. Probability-1, 3rd ed. Springer, 2016. Chapter 3 (the central limit theorem, Lindeberg’s condition, the rate of convergence).
• I. Shevtsova. On the absolute constants in the Berry–Esseen type inequalities for identically distributed summands. arXiv:1111.6554, 2011. The constant 0.4748.