The law of large numbers and the CLT

Everything measured in machine learning is a sample average standing in for an expectation. That substitution is licensed by exactly two theorems, and between them they answer the two questions that matter: does the average converge? (the law of large numbers: yes) and how wrong is it right now? (the central limit theorem: Gaussianly, shrinking as $1/\sqrt{n}$). This lesson proves the first, demonstrates the second until you believe it in your bones, and then collects the $1/\sqrt n$ tax bill from every corner of the curriculum.

The law of large numbers, via Chebyshev

For i.i.d. draws with mean $\mu$ and variance $\sigma^2$, last lesson gave the average’s moments: $\mathbb{E}[\bar X_n] = \mu$, $\operatorname{Var}[\bar X_n] = \sigma^2/n$. Chebyshev’s inequality — for any random variable, $\Pr(\lvert Y - \mathbb{E}Y\rvert \ge \varepsilon) \le \operatorname{Var}[Y]/\varepsilon^2$, provable in three lines — then turns shrinking variance into shrinking miss-probability:

That is the (weak) law of large numbers: sample means converge to the true mean. It is why empirical risk approaches true risk, why Monte Carlo works at all, and why a casino’s income is deterministic while every gambler’s night is random — the house plays $n$, the gambler plays 1. Sharper tools exist for bounded variables — Hoeffding’s inequality gives exponentially small miss probability, $2\exp(-2n\varepsilon^2)$, and is the standard engine behind generalization bounds — but Chebyshev’s virtue is that it needs nothing but a finite variance, and its $\sigma^2/n$ already displays the module’s favourite ratio.

The central limit theorem: the shape of the error

LLN says the error vanishes; the CLT says something far stranger — the error has a universal shape. If $X_i$ are i.i.d. with mean $\mu$ and finite variance $\sigma^2$, then the standardized mean

Average enough of anything (with finite variance) and the fluctuations become Gaussian. This is why the bell curve is everywhere: not because nature loves it, but because nature loves sums — measurement errors, biological traits, aggregated returns are all totals of many small contributions. It is also why Gauss’s error model for least squares (next lesson’s reveal) was such a defensible bet. Watch universality happen, because reading about it does not compare:

The 1/√n tax, itemized

The CLT’s practical content is the standard error: the typical error of an average is $\sigma/\sqrt{n}$, so every additional digit of accuracy costs 100× the data. This one scaling law has been quietly running the entire curriculum — collect the receipts:

• Test-set metrics (Evaluation lesson): accuracy on $m$ samples carries SE $\sqrt{p(1-p)/m}$ — the error bar that made 0.5% “improvements” on small benchmarks meaningless, now with its theorem attached. The 95% interval $\pm 1.96\,\mathrm{SE}$ is just the CLT’s Gaussian quantiles.
• Minibatch gradients (SGD lesson): a batch of $b$ samples estimates the true gradient with noise $\propto 1/\sqrt{b}$ — the reason batch size bought noise reduction at a sublinear exchange rate, and the reason the noise ball had the radius it had.
• Monte Carlo everything (RL track): a policy’s value estimated from $n$ rollouts, a win-rate from $n$ judged pairs, self-consistency’s vote from $k$ samples — all $\sigma/\sqrt{n}$ estimators, all priced by this lesson.
• A/B tests and cohort comparisons: detecting an effect of size $\delta$ needs $n \sim \sigma^2/\delta^2$ per arm — the sample-size arithmetic every product experiment lives and dies by.

The flip side is a warning label: the CLT needs finite variance and weak dependence. Heavy-tailed quantities (wealth, viral counts, catastrophic losses) can have effectively infinite variance — their averages converge slowly or to stable non-Gaussian laws, and $\sigma/\sqrt n$ reasoning silently lies. Correlated samples (time series, users within a cohort, the forest lesson’s $\rho$) shrink the effective $n$. When an error bar looks too good, one of these two assumptions is usually the reason.

import numpy as np
rng = np.random.default_rng(1)

# The 1/√n law, measured: SE of the mean of exponential(1) draws
for n in [10, 100, 1000, 10000]:
    means = rng.exponential(1.0, size=(20_000, n)).mean(axis=1)
    print(n, means.std(), 1 / np.sqrt(n))   # empirical SE ≈ σ/√n  (σ = 1)

Exercises