The laws of large numbers

The first lesson left a debt. It claimed that measured frequencies stabilise, could not justify it, and took the axioms as a starting point instead. Everything since then has been built on those axioms, and they now suffice to pay the debt back with interest: not only do averages settle, but the residual error has a shape that can be computed, and the shape does not depend on what was being averaged.

What has to be proved

Take independent repetitions $X_{1}, X_{2}, \dots$ of the same experiment, each with mean $μ$ and finite variance $σ^{2}$ , and let

{\overline{X}}_{n} = \frac{X_{1} + \dots + X_{n}}{n}

be the average of the first $n$ . The claim to be proved is that ${\overline{X}}_{n}$ closes in on $μ$ . Applied to indicators, where $X_{i}$ is $1$ when an event occurs and $0$ otherwise, ${\overline{X}}_{n}$ is the observed frequency of that event and $μ$ is its probability, so proving the general claim proves the specific one about coin tosses.

Two ingredients are already in hand. By linearity, $E [{\overline{X}}_{n}] = μ$ for every $n$ , so the average is centred correctly from the very first trial. By the additivity of variance for independent variables and the scaling rule,

operatorname {V a r} ({\overline{X}}_{n}) = \frac{σ^{2}}{n}

so the spread of the average shrinks towards zero. Centred correctly and shrinking: that is nearly the whole proof, and Chebyshev supplies the rest.

The weak law

Chebyshev's inequality, applied to ${\overline{X}}_{n}$ with its mean $μ$ and standard deviation $σ / \sqrt{n}$ , says that for any fixed tolerance $ε > 0$ ,

P (| {\overline{X}}_{n} - μ | \geq ε) \leq \frac{σ^{2}}{n ε^{2}}

obtained by setting $k σ / \sqrt{n} = ε$ in the inequality. The right-hand side is a constant divided by $n$ , so it tends to zero. That is the weak law of large numbers: for every tolerance, however tight, the probability that the average misses the true mean by more than that tolerance can be driven as low as you like by taking enough trials.

The proof is three lines and it uses only results already established, which is worth pausing on. Bernoulli's original proof in Ars Conjectandi, published in 1713, ran to twenty pages and he worked on it for twenty years. Chebyshev's inequality of 1867 collapsed it, and the collapse is what a good abstraction buys.

Note what the theorem does not claim. It does not say ${\overline{X}}_{n}$ eventually stays near $μ$ ; for each $n$ separately it bounds a probability, and a rare excursion at some later $n$ is not excluded. Strengthening it to "with probability one, the sequence of averages converges to $μ$ and stays there" is the strong law of large numbers, proved for coin tossing by Émile Borel in 1909 and in general by Kolmogorov in 1930. The strong law needs no variance at all, only a finite mean. Its proof is genuinely harder and is not attempted here; the statement is what matters, and it is what licenses the frequency reading of probability from the first lesson.

Example. A measurement has standard deviation $σ = 1$ unit. Using Chebyshev, how many repeats guarantee that the average is within $0.05$ units of the true value with probability at least $0.96$ ?

The bound is $σ^{2} / (n ε^{2}) = 1 / (n \times 0.0025)$ , and setting this to $0.04$ gives $n = 1 / (0.04 \times 0.0025) = 10000$ repeats. This is a guarantee for any distribution whatsoever, which is why it is so demanding.

Now you. With the same $σ$ and $ε = 0.1$ , what does Chebyshev give as the bound on the failure probability after $1000$ repeats?

Answer

$1 / (1000 \times 0.01) = 0.1$ , so at least a $90$ percent chance of landing within $0.1$ of the true mean.

What the law does not promise

The law of large numbers is the single most misquoted result in mathematics, and the misquotation has a name: the gambler's fallacy, the belief that a run of one outcome makes the other "due".

The trials are independent. A coin that has landed tails ten times running lands heads next with probability exactly $0.5$ , because the coin has no memory and nothing in the mathematics says otherwise. So how does the average recover?

By dilution, not by compensation. After ten tails you are ten heads behind. Toss a thousand more times and the expected number of heads among them is $500$ , leaving you at $500$ heads out of $1010$ , a fraction of $0.4950$ . Toss ten thousand more and it is $5000$ out of $10010$ , or $0.4995$ . The deficit of ten never goes away; it is simply divided by an ever larger denominator. This is exactly the pattern in Kerrich's table from the first lesson, where the absolute surplus of heads grew while the fraction converged, and the two facts are now both consequences of $operatorname {V a r} ({\overline{X}}_{n}) = σ^{2} / n$ with $operatorname {V a r} (S_{n}) = n σ^{2}$ .

The second misuse is applying the law to a small number of trials. Nothing in it says anything about ten tosses, or a hundred, or an evening at a casino. The bound weakens by a factor of $n$ , so it says nothing useful until $n$ is large relative to $σ^{2} / ε^{2}$ .

The shape of what is left over

The weak law says the error ${\overline{X}}_{n} - μ$ shrinks. That leaves an obvious question: shrinks how, and what does it look like on the way?

The scale is already known. The standard deviation of the error is $σ / \sqrt{n}$ , so multiplying the error by $\sqrt{n} / σ$ produces something whose spread stays fixed at $1$ as $n$ grows. Equivalently, standardise the sum:

Z_{n} = \frac{S_{n} - n μ}{σ \sqrt{n}}

which has mean $0$ and variance $1$ for every $n$ . The central limit theorem says that as $n$ grows, the distribution of $Z_{n}$ converges to the standard normal, whatever the distribution of the individual $X_{i}$ was, provided only that its variance is finite.

Read that again, because it is a strange claim. The ingredients can be dice, coin tosses, exponential waiting times, incomes, anything at all with a finite variance, symmetric or skewed, discrete or continuous. Sum enough of them, standardise, and the answer is the same curve to whatever accuracy you like. The individual distribution is forgotten entirely except through its mean and variance. Laplace stated a version in 1810, Lyapunov proved it under general conditions in 1901, and the name is Pólya's, from 1920.

This explains the observation the previous lesson could not. Measurement errors are normal because each is a sum of many small independent disturbances. Heights are roughly normal because many small genetic and environmental contributions add. And de Moivre's binomial approximation is the special case where the $X_{i}$ are Bernoulli trials, since a binomial variable is literally a sum of $n$ of them.

Example. Ten fair dice are rolled and totalled. The single-die mean is $3.5$ and variance $35 / 12$ , so the total has mean $35$ and standard deviation $\sqrt{350 / 12} \approx 5.4006$ . Estimate $P (total \geq 45)$ using the central limit theorem with a continuity correction, and compare with the exact value.

$z = (44.5 - 35) / 5.4006 = 1.7591$ , so the estimate is $1 - Φ (1.7591) \approx 0.03928$ . The exact answer, computed by convolving the six-sided distribution ten times, is $0.03899$ . Ten dice is already enough for agreement to three decimal places.

Now you. Using the same figures, estimate the probability that the total of ten dice is at least $40$ .

Answer

$z = (39.5 - 35) / 5.4006 = 0.8332$ , so the estimate is $1 - Φ (0.8332) \approx 0.2024$ . The exact value is $0.2050$ , so the approximation is a little over one percent low.

What a poll is actually claiming

The most familiar application is the reported margin of error on an opinion poll, and it is now derivable in full.

Poll $n$ people independently, each supporting a proposition with unknown probability $p$ . The count is binomial, and the observed proportion $\hat{p}$ has mean $p$ and standard deviation $\sqrt{p (1 - p) / n}$ . That quantity is largest at $p = 0.5$ , where it equals $0.5 / \sqrt{n}$ , so using the worst case costs little and needs no knowledge of $p$ . By the central limit theorem $\hat{p}$ is approximately normal, and $95$ percent of a normal distribution lies within $1.96$ standard deviations of its mean. Hence with probability about $0.95$ ,

| \hat{p} - p | \leq \frac{1.96 \times 0.5}{\sqrt{n}} = \frac{0.98}{\sqrt{n}}

For $n = 1000$ this is $0.031$ , the familiar "plus or minus three points". Quadrupling the sample to $4000$ halves it to $1.55$ points, which is the square root law again and is why polls are not larger: the fourth thousand respondents buy far less than the first thousand.

Two honest caveats. The figure assumes a genuine random sample, and in practice non-response and coverage errors dwarf the sampling error this formula describes, so a poll's real uncertainty is wider than its stated margin. And the margin is a statement about the procedure, not about this particular poll: one poll in twenty is expected to fall outside its own margin, which is worth remembering when a single surprising result appears.

Example. A poll of $2000$ people is conducted. What is the worst-case $95$ percent margin of error?

$0.98 / \sqrt{2000} = 0.0219$ , about $2.2$ percentage points.

Now you. How many people must be polled for a worst-case margin of $1$ percentage point?

Answer

Set $0.98 / \sqrt{n} = 0.01$ , so $\sqrt{n} = 98$ and $n = 9604$ people.

Where the limit laws fail

Both theorems have conditions, and each condition fails somewhere real.

Independence is the first. Correlated observations do not average out at the rate $σ / \sqrt{n}$ , and if the correlation does not decay with distance they may not average out at all. Sampling a thousand people from one town is not sampling a thousand people from the country, and treating it as such gives a margin of error that is confidently too small.

A finite variance is the second, and its failure is more dramatic. The Cauchy distribution, which describes the horizontal position where a randomly angled beam from a point source meets a line, has no finite mean or variance. The average of $n$ independent Cauchy variables has exactly the same distribution as a single one, no matter how large $n$ is. Averaging accomplishes literally nothing, and no amount of data helps. Real heavy-tailed data, in insurance and finance, sits between this extreme and the well-behaved case, and it converges slowly enough that the normal approximation misleads at the sample sizes people actually have.

The third is a matter of rate rather than of validity. The theorem says the limit is normal, and says nothing about how large $n$ must be for the approximation to be usable. For a symmetric ingredient like a die, ten is plenty. For a heavily skewed one, hundreds or thousands may not be, and the tails converge far more slowly than the centre, which is precisely where the answer usually matters.

The machinery of the subject is now complete: sample spaces, conditioning, inversion, quantities, spread, the standard laws, and the limit theorems that connect them back to observation. What remains is the reliable business of applying it wrongly, which is the last lesson.