Law of large numbers and the central limit theorem

Setup

$x_1,\dots,x_n$ i.i.d. (Probability notation and random variables) from $p$, with $\mu=\mathbb{E}[x]$, $\sigma^2=\operatorname{Var}(x)<\infty$. The sample mean:

$$ \bar x_n = \frac1n\sum_{i=1}^n x_i. $$

$\bar x_n$ is itself a random variable (a different dataset gives a different $\bar x_n$), with $\mathbb{E}[\bar x_n]=\mu$ and:

$$ \operatorname{Var}(\bar x_n) = \frac{\sigma^2}{n}, $$

by independence (variances of independent sums add, and scale by $1/n^2$).

Intuition: the sample mean's own spread shrinks as $n$ grows; that shrinking variance is the entire engine behind both results below.

Notation: three kinds of convergence

$$ X_n \xrightarrow{\ p\ } X: \quad \text{for every } \epsilon>0,\ \ P(|X_n-X|>\epsilon)\to0. $$

$$ X_n \xrightarrow{\ \text{a.s.}\ } X: \quad P\Big(\lim_{n\to\infty}X_n = X\Big) = 1. $$

$$ X_n \xrightarrow{\ d\ } X: \quad P(X_n\leq x)\to P(X\leq x) \ \text{at every continuity point } x. $$

Almost sure convergence is the strongest of the three: $\xrightarrow{\text{a.s.}}\ \Rightarrow\ \xrightarrow{p}\ \Rightarrow\ \xrightarrow{d}$ (the reverse implications fail in general).

Intuition: $\xrightarrow{\text{a.s.}}$ asks the actual sequence of outcomes to settle down, path by path; $\xrightarrow{p}$ only asks the probability of a large gap to shrink at each $n$, without ever requiring the sequence to settle; $\xrightarrow{d}$ asks even less, only that the histogram's shape settles, not the variables themselves.

Weak law of large numbers

$$ \bar x_n \xrightarrow{\ p\ } \mu \quad \text{as } n\to\infty. $$

Quick proof, by Chebyshev's inequality (Concentration inequalities), for any $\epsilon>0$:

$$ P(|\bar x_n-\mu|\geq\epsilon) \ \leq\ \frac{\operatorname{Var}(\bar x_n)}{\epsilon^2} = \frac{\sigma^2}{n\epsilon^2} \ \xrightarrow[n\to\infty]{}\ 0, $$

which is exactly the definition of $\bar x_n\xrightarrow{p}\mu$. ✓

Intuition: averaging cancels noise; enough independent samples and the sample mean has nowhere left to fluctuate to but $\mu$.

Strong law of large numbers

$$ \bar x_n \xrightarrow{\ \text{a.s.}\ } \mu \quad \text{as } n\to\infty. $$

A stronger statement than the weak law: not just that $\bar x_n$ is unlikely to be far from $\mu$ at any given $n$, but that the actual sequence $\bar x_1,\bar x_2,\dots$ settles down to $\mu$ for good, with probability $1$. It requires only a finite mean (no variance needed at all), but the proof needs more machinery than fits here (typically the Borel–Cantelli lemma or a martingale argument), so it is stated without proof.

Intuition: the weak law only promises $\bar x_n$ is probably close to $\mu$ at each fixed $n$ separately; the strong law promises the whole infinite sequence of outcomes converges, path by path, not just one snapshot at a time.

Central limit theorem

The LLN says $\bar x_n\to\mu$ but says nothing about the error $\bar x_n-\mu$ on the way there. Rescale that error by $\sqrt n$ (exactly the rate needed to stop it from shrinking to $0$ or blowing up):

$$ \sqrt n\,(\bar x_n - \mu) \ \xrightarrow{\ d\ }\ \mathcal{N}(0,\sigma^2). $$

Equivalently, for large $n$:

$$ \bar x_n \ \approx\ \mathcal{N}\!\left(\mu,\ \frac{\sigma^2}{n}\right), \qquad Z_n := \frac{\bar x_n-\mu}{\sigma/\sqrt n} \ \xrightarrow{\ d\ }\ \mathcal{N}(0,1). $$

This holds no matter what $p$ is (Bernoulli, uniform, wildly skewed), as long as $\sigma^2<\infty$: the Gaussian shape comes from the averaging, not from $p$.

Intuition: the sample mean's leftover error, viewed at exactly the $1/\sqrt n$ scale, always looks Gaussian; too coarse a scale and the error looks like a point ($0$), too fine and it looks unbounded.

The proof (typically via the moment generating function or, more generally, the characteristic function, showing it converges to the Gaussian's) needs more buildup than fits here, so it too is stated without proof.

LLN vs. CLT

$$ \text{Weak LLN: } \bar x_n \xrightarrow{p} \underbrace{\mu}_{\text{a number}}, \qquad \text{CLT: } \sqrt n(\bar x_n-\mu) \xrightarrow{d} \underbrace{\mathcal{N}(0,\sigma^2)}_{\text{a distribution}}. $$

Intuition: LLN zooms out and says where the sample mean ends up; CLT zooms back in at the $\sqrt n$ scale and says what the leftover error looks like, regardless of where you started.

Where this is used

• Confidence intervals. $Z_n\approx\mathcal{N}(0,1)$ justifies $\bar x_n \pm 1.96\,\sigma/\sqrt n$ as a 95% interval for $\mu$, for essentially any $p$ with finite variance; when $\sigma$ itself has to be estimated, this becomes the $t$-statistic instead (Confidence intervals: the z and t statistics).
• Monte Carlo estimation. Any expectation $\mathbb{E}[f(x)]$ estimated by averaging samples has error shrinking like $\sigma/\sqrt n$ (LLN) and approximately Gaussian (CLT), which is exactly where the standard "error bars" on a Monte Carlo estimate come from.
• Minibatch gradients. A minibatch gradient is a sample mean over examples; LLN is why larger batches give less noisy gradient estimates, and CLT is why that noise is often modeled as approximately Gaussian.