Chapter XI · 18 min

Limit Theorems

Why averages settle

“The law of large numbers is the bridge between probability and the world of observed frequencies.”

A single coin is noise. A thousand coins are a fact. Limit theorems are the precise form of that slogan. They are why polling works, why sample means are worth computing, and why a learning algorithm can look at a finite dataset and say something about a distribution it has never seen whole.

The law of large numbers

Let $X_1,X_2,\dots$ be i.i.d. with finite mean $\mu =\mathbb{E}[X_1]$. Write ${\bar{X}}_n=(X_1+\cdots +X_n)/n$. Then ${\bar{X}}_n\to \mu$ as $n\to \infty$ — in probability (the weak law) and, under the same hypotheses, almost surely (the strong law). Chebyshev plus vanishing variance of the mean, $\mathrm{Var}({\bar{X}}_n)={\sigma }^2/n$, already gives the weak law when the variance is finite.

The law does not say that the next flip is due to compensate. Memorylessness of independent trials is still in force. It says the average so far forgets its start. Visit the settling averages lab and watch a path calm down.

The central limit theorem

The average settles; the shape of its error becomes universal. If the $X_i$ are i.i.d. with mean $\mu$ and finite positive variance ${\sigma }^2$, then

Convergence in distribution means that probabilities of intervals settle to the corresponding normal probabilities. The left-hand side is the number of standard errors by which the sample mean misses $\mu$. For large $n$, that number looks like a standard normal, even if each $X_i$ was a coin, a die, or a waiting time.

This is why the bell of Chapter 9 keeps returning. Add many independent small contributions, scale by $\sqrt{n}$, and the density of the sum forgets the density of the parts. (The hypotheses can fail: infinite variance, strong dependence, one term dominating. Then other limit laws — stable laws, not Gaussian — may appear.)