Central Limit Theorem

Let $S_n \sim \text{Binomial}(n, p)$ for fixed $p \in (0, 1)$. Then

Equivalently, for any $a < b$,

With $n = 100$, $p = 0.3$: $np = 30$, $\sqrt{npq} = \sqrt{21} \approx 4.58$. The standardization says $S_{100}$ is approximately $\mathcal{N}(30, 21)$. A 95% Normal band gives

The exact Binomial probability $\mathbb{P}(21 \le S_{100} \le 39)$ is $0.9507$ — the Normal approximation is off by less than $0.001$. For discrete-data accuracy, a continuity correction replaces the integer endpoints by half-integer ones: $\mathbb{P}(a \le S_n \le b) \approx \Phi((b + 0.5 - np)/\sqrt{npq}) - \Phi((a - 0.5 - np)/\sqrt{npq})$. This is what the explorer below toggles on and off.

De Moivre (1733) proved the $p = 1/2$ case. Laplace (1812) extended to general $p$. Lyapunov (1901) gave the first general CLT under a third-moment condition. Lindeberg (1922) gave the sharp necessary-and-sufficient condition. Lévy (1925) supplied the characteristic function machinery, and Berry (1941) and Esseen (1942) proved the rate. Two centuries of incremental sharpening separate de Moivre’s coin-flip argument from the modern graduate-level CLT.

Let $X_1, X_2, \ldots$ be iid with $\mathbb{E}[X_1] = \mu$ and $0 < \text{Var}(X_1) = \sigma^2 < \infty$. Let $\bar{X}_n = (1/n)\sum_{i=1}^n X_i$. Then

We simulate $M = 5000$ replications of the standardized mean $Z_n$ at several values of $n$:

(KS = Kolmogorov–Smirnov distance from $\mathcal{N}(0,1)$; smaller is better.)

Symmetric, bounded distributions (Uniform) hit target accuracy almost immediately. Skewed distributions (Chi², Exponential) take longer. The rate is $O(1/\sqrt{n})$ uniformly — §7 will pin it down.

The Lindeberg–Lévy hypothesis is restrictive — real data rarely comes iid. But the iid assumption is not necessary; §6 replaces it with the Lindeberg condition, which is the true mechanism making the CLT work: no single summand should contribute an appreciable fraction of the total variance. iid is simply the simplest setting in which this happens automatically.

For $X \sim \text{Exp}(1)$, $\mu = 1$ and $\sigma = 1$. Work with the centered variable $Y = X - 1$. Then

Expand: $e^{-t} = 1 - t + t^2/2 - t^3/6 + O(t^4)$ and $1/(1-t) = 1 + t + t^2 + t^3 + O(t^4)$. Multiply:

The coefficient of $t^2$ is $1/2$ — consistent with $\sigma^2 = 1$. Substituting $s = t/\sqrt{n}$ and taking logs:

The cubic term is $O(1/\sqrt{n})$ — it vanishes as $n \to \infty$, giving the $\mathcal{N}(0,1)$ limit as expected. But the cubic coefficient is the reason Exponential converges slower than Uniform (where the cubic term vanishes by symmetry). This is the Berry–Esseen rate effect of §7.

Topic 9, Theorem 9.13 proved the Poisson limit theorem by the same five-step recipe: (1) compute the MGF of the standardized sum, (2) take the log, (3) Taylor-expand in powers of $1/n$, (4) show the $n \to \infty$ limit is the target MGF, (5) invoke Lévy continuity and MGF uniqueness. Only step (3) differs between the two proofs: for Poisson, the Taylor expansion gives $\lambda(e^t - 1)$ in the limit; for the CLT, it gives $t^2/2$.

For a random variable $X$, the characteristic function is

where $i = \sqrt{-1}$. Since $|e^{itX}| = 1$, the expectation exists for every distribution. The characteristic function uniquely determines the distribution: $\varphi_X = \varphi_Y$ implies $X \stackrel{d}{=} Y$.

Let $X_n, X$ be random variables with characteristic functions $\varphi_n, \varphi$. Then $X_n \xrightarrow{d} X$ if and only if $\varphi_n(t) \to \varphi(t)$ for every $t \in \mathbb{R}$ and $\varphi$ is continuous at $0$.

MGFs are real-valued, which makes Taylor expansion concrete and helps with first intuition. CFs are complex-valued but always exist. The MGF proof assumes $M_X(t)$ finite in a neighborhood of zero — a nontrivial restriction (no Cauchy, no power-law tails without moments). The CF proof requires only $\mathbb{E}[X^2] < \infty$. In graduate probability, the CF proof is standard; in a first exposure, the MGF proof is more transparent. We do both.

Let $X_1, X_2, \ldots$ be independent (not necessarily identically distributed) with $\mathbb{E}[X_k] = 0$ and $\text{Var}(X_k) = \sigma_k^2 < \infty$. Set $s_n^2 = \sum_{k=1}^n \sigma_k^2$. The Lindeberg condition is

Under the setup of Definition 2, if the Lindeberg condition holds, then

Under the Lindeberg setup, if there exists $\delta > 0$ such that

then $S_n/s_n \xrightarrow{d} \mathcal{N}(0, 1)$.

The Lyapunov condition implies the Lindeberg condition.

Take $X_1 \sim \mathcal{N}(0, n^2)$ and $X_2, \ldots, X_n \sim \mathcal{N}(0, 1)$ all independent. Then

The Lindeberg condition fails because $X_1$ carries essentially all the variance. And sure enough, $S_n/s_n \approx X_1/n \sim \mathcal{N}(0, 1)$ already — but not because of the CLT. It’s simply inheriting the single Gaussian’s distribution. Replace $X_1$ with $X_1 \sim t(3) \cdot n$ (Student $t$ with three degrees of freedom scaled by $n$), still with variance $O(n^2)$, and $S_n/s_n$ will be approximately $t(3)$, not Normal — the CLT truly breaks.

Feller (1935) proved the converse: if $S_n/s_n \xrightarrow{d} \mathcal{N}(0, 1)$ and $\max_{k \le n} \sigma_k^2 / s_n^2 \to 0$ (a “negligibility” condition), then the Lindeberg condition holds. Together these constitute an if-and-only-if characterization: under negligibility, the Lindeberg condition is the precise mechanism making the CLT work. The Lyapunov condition is merely a more tractable sufficient one — it gives up some generality for ease of verification.

Let $X_1, X_2, \ldots$ be iid with $\mathbb{E}[X_1] = \mu$, $\text{Var}(X_1) = \sigma^2 > 0$, and finite absolute third moment $\mathbb{E}[|X_1 - \mu|^3] < \infty$. Set $\rho = \mathbb{E}[|X_1 - \mu|^3]/\sigma^3$. Let $F_n$ be the CDF of $Z_n = \sqrt{n}(\bar{X}_n - \mu)/\sigma$. Then there is an absolute constant $C$ such that

The best known bound is $C \le 0.4748$ (Shevtsova, 2011).

At $n = 50$ with $C = 0.4748$:

• Uniform(0, 1): $\rho = 1.8$, bound $= 0.4748 \cdot 1.8 / \sqrt{50} \approx 0.121$. Empirical sup deviation: $\approx 0.02$.
• Exponential(1): $\rho = 6$, bound $= 0.4748 \cdot 6 / \sqrt{50} \approx 0.403$. Empirical sup deviation: $\approx 0.05$.

The bound is an upper envelope — the empirical deviation is typically 5–10× smaller than the bound. But the relative ordering is preserved: the ratio of Uniform to Exponential sup deviations tracks the ratio of their $\rho$ values. The bound is not tight in general (it overstates the deviation), but it is tight in the worst case — there exist distributions (the Bernoulli family) for which the constant $C$ cannot be improved.

The original bound had $C \le 7.59$ (Esseen, 1942). Over eighty years of refinement, the constant has come down to $C \le 0.4748$ (Shevtsova, 2011). The true value is known to satisfy $C \ge (\sqrt{10} + 3)/(6\sqrt{2\pi}) \approx 0.40973$ by a sharp Bernoulli(p) example. The gap between $0.40973$ and $0.4748$ is the open problem.

Let $\mathbf{X}_1, \mathbf{X}_2, \ldots \in \mathbb{R}^d$ be iid with $\mathbb{E}[\mathbf{X}_1] = \boldsymbol{\mu}$ and finite covariance matrix $\Sigma = \text{Cov}(\mathbf{X}_1)$. Let $\bar{\mathbf{X}}_n = (1/n)\sum_{i=1}^n \mathbf{X}_i$. Then

Take $\mathbf{X}_i = (X_i, Y_i)$ with $X_i \sim \text{Exp}(1)$, $Y_i = X_i^2 - \mathbb{E}[X_i^2]$. Then

(The cross-covariance is $\mathbb{E}[(X - 1)(X^2 - 2)] = \mathbb{E}[X^3 - X^2 - 2X + 2] = 6 - 2 - 2 + 2 = 4$.) By the multivariate CLT, for $n = 100$ the sample mean vector is approximately $\mathcal{N}_2(\boldsymbol{\mu}, \Sigma/100)$. The Mahalanobis distance $n(\bar{\mathbf{X}}_n - \boldsymbol{\mu})^\top \Sigma^{-1} (\bar{\mathbf{X}}_n - \boldsymbol{\mu}) \xrightarrow{d} \chi^2(2)$ — the standard recipe for multivariate hypothesis tests.

The Cramér–Wold device reduces every multivariate convergence problem to a family of univariate problems. It does for convergence in distribution what linearity does for expectation: convert a $d$-dimensional question into a one-dimensional question indexed by the unit sphere. This is why the multivariate Normal is characterized by its one-dimensional projections, why quadratic forms of multivariate Normals are $\chi^2$-distributed, and why multivariate Slutsky works.

Let $\hat{\theta}_n$ be a sequence of estimators with $\sqrt{n}(\hat{\theta}_n - \theta) \xrightarrow{d} \mathcal{N}(0, \sigma^2)$, and let $g : \mathbb{R} \to \mathbb{R}$ be differentiable at $\theta$ with $g'(\theta) \ne 0$. Then

Suppose $X_i \sim \text{Exp}(\lambda)$ iid, and we want a 95% CI for the rate parameter $\lambda$. The MLE is $\hat{\lambda}_n = 1/\bar{X}_n$. By the CLT, $\sqrt{n}(\bar{X}_n - 1/\lambda) \xrightarrow{d} \mathcal{N}(0, 1/\lambda^2)$. Apply the delta method with $g(x) = 1/x$ so $g'(x) = -1/x^2$.

The key subtlety: $g'$ must be evaluated at the true mean $\mu = 1/\lambda$, not left as a function of $x$. A common pitfall is to mechanically plug $g'(x) = -1/x^2$ into $[g'(\mu)]^2 \sigma^2$ with the symbol $x$ still floating, producing an expression like $\lambda^{-4} \cdot \lambda^{-2}$ that has no stable interpretation. Evaluate first:

With $g'$ pinned to $\mu$, the delta method gives

The 95% CI is $\hat{\lambda}_n \pm 1.96 \,\hat{\lambda}_n/\sqrt{n}$. For skewed estimators like this, a log transform often gives a better small-$n$ CI: $g(x) = \log(1/x) = -\log x$ has derivative $-1/x$, so $\sqrt{n}(\log \hat{\lambda}_n - \log \lambda) \xrightarrow{d} \mathcal{N}(0, 1)$. Build the CI on the log scale, then exponentiate: $\exp(\log \hat{\lambda}_n \pm 1.96/\sqrt{n})$. This symmetric-on-log-scale CI respects the non-negativity of $\lambda$ (unlike the naive linear CI, which can be negative for small $n$).

If $g'(\theta) = 0$, the first-order delta method gives a degenerate $\mathcal{N}(0, 0)$ limit — which is useless. The fix is a second-order delta method: if $g''(\theta) \ne 0$, then $n(g(\hat{\theta}_n) - g(\theta)) \xrightarrow{d} \tfrac{1}{2} g''(\theta) \sigma^2 \chi^2(1)$. Now the convergence rate is $1/n$, not $1/\sqrt{n}$, and the limit is a (shifted, scaled) chi-squared, not a Normal. This happens, for example, with $g(x) = x^2$ at $\theta = 0$: the sample mean is centered at zero, so $(\bar{X}_n)^2$ has a non-Normal limit.

1. Confidence intervals for model accuracy. After evaluating a classifier on $n$ test examples, the error rate $\hat{p} = (1/n)\sum \mathbf{1}\{\hat{y}_i \ne y_i\}$ is a Binomial average. By de Moivre–Laplace, $\hat{p} \pm 1.96\sqrt{\hat{p}(1-\hat{p})/n}$ is an approximate 95% CI for the true error rate. Every reported accuracy on a test set has Binomial error bars whether the reporter acknowledges them or not — and those bars are $\approx 0.03$ on a 1000-example test set even for a perfectly classified model, growing to $0.05$ at $n = 400$.

2. SGD mini-batch gradient noise. The stochastic gradient $\hat{g}_B = (1/B)\sum_{i \in B} \nabla \ell(\theta; x_i)$ is an average of $B$ iid gradient samples (assuming the batch is uniform at random). By the multivariate CLT, $\hat{g}_B - \nabla L(\theta) \approx \mathcal{N}(\mathbf{0}, \Sigma/B)$ where $\Sigma$ is the per-sample gradient covariance. The optimization noise is Gaussian to leading order — this is why SGD trajectories look like Brownian motion on an energy landscape, and why the learning-rate schedule $\eta \propto 1/\sqrt{t}$ is the canonical rate. formalML: Stochastic Gradient Descent has the full story.

3. Bayesian posteriors (Bernstein–von Mises). The Bernstein–von Mises theorem is the CLT for posteriors: under regularity, $\sqrt{n}(\theta - \theta_0) \mid X_1, \ldots, X_n \xrightarrow{d} \mathcal{N}(0, I(\theta_0)^{-1})$ where $I(\theta_0)$ is the Fisher information. The posterior concentrates around the MLE at rate $1/\sqrt{n}$ with a Gaussian shape — regardless of the prior. This is why Bayesian credible intervals and frequentist confidence intervals agree asymptotically, and why casual users can get away with ignoring prior choice on large datasets. See formalML: Bayesian Neural Networks for where this machinery is indispensable (and where it breaks — small data, non-identifiable models).

The Bernstein–von Mises theorem formalizes a result practitioners use implicitly every day: on large-enough data, frequentist and Bayesian inference coincide. The proof (Van der Vaart 1998, Chapter 10) uses the CLT via the score function — the derivative of the log-likelihood at the MLE is asymptotically Normal by the CLT, and Laplace’s method extracts a Gaussian posterior from the likelihood. The rate $1/\sqrt{n}$ is inherited directly from the CLT rate. When Bernstein–von Mises fails — heavy-tailed priors, non-identifiable models, high-dimensional parameters with $d \sim n$ — it is precisely because one of the CLT’s hypotheses fails for the score.