The law of large numbers and the central limit theorem

Almost every simulation in this course ends by averaging. A Monte Carlo price is an average of discounted payoffs, a sample volatility is an average of squared returns, and the Brownian motion of "Random walks and Brownian motion" is the limit of a rescaled sum of coin flips. Two theorems explain why averages are so well behaved: the law of large numbers says that an average settles down, and the central limit theorem says how it fluctuates around the value it settles on. This lesson states both with their hypotheses, proves the simpler one, and uses a figure to show how quickly the second takes hold. The sample means and variances of "Returns and volatility" are the first averages you met.

Averages of independent draws

Let $X_1, X_2, \dots$ be independent, identically distributed (i.i.d.) random variables with mean $\mu$ and a finite variance $\sigma^2$. The sample mean of the first $n$ is $\bar X_n = (X_1 + \cdots + X_n)/n$. Linearity of expectation, and the fact that variances of independent variables add, give two facts that everything below rests on:

The average is right on average, and its standard deviation $\sigma/\sqrt{n}$, called the standard error, shrinks like $1/\sqrt{n}$. Nothing more is assumed yet. The rest of the lesson asks what that shrinking implies.

The weak law of large numbers

Theorem (weak law). For every $\varepsilon > 0$, $P(|\bar X_n - \mu| > \varepsilon) \to 0$ as $n \to \infty$. One says that $\bar X_n$ converges to $\mu$ in probability. The proof is Chebyshev's inequality, $P(|Y - E[Y]| \ge \varepsilon) \le \operatorname{Var}(Y)/\varepsilon^2$, applied to $Y = \bar X_n$:

Chebyshev's bound is crude, but it needs nothing beyond a finite variance, and the shrinking variance does all the work.

The strong law

Theorem (strong law). If $E|X_i| < \infty$, then $P(\bar X_n \to \mu) = 1$. Here "with probability one", or almost surely, means that the sequences of draws for which the averages fail to settle form a set of probability zero. The weak law controls each fixed $n$ separately. The strong law controls the whole path of running averages as $n$ grows, and that is what a single long simulation relies on. It does not even need a finite variance, only a finite mean. We state it without proof.

The central limit theorem

The laws say where the average ends up, not how it is distributed around that value. To see the shape, standardise it, so that it has mean 0 and variance 1 for every $n$:

Theorem (central limit theorem). If the $X_i$ are i.i.d. with finite mean $\mu$ and finite, positive variance $\sigma^2$, then for every $z$

where $\Phi$ is the standard normal distribution function. The hypotheses matter: independence, a common distribution, and a finite variance. The source distribution is otherwise arbitrary, which is why the walk of "Random walks and Brownian motion", rescaled by $\sqrt{n}$, has a normal limit even though its steps are coin flips. In practice the theorem is used as the approximation $\bar X_n \approx N(\mu, \sigma^2/n)$ for large $n$.

How fast: the Berry–Esseen bound

The theorem is a statement about a limit. For a finite $n$ it is an approximation, and Berry–Esseen measures its error. If $\rho_3 = E|X_i - \mu|^3$ is finite, then

The error shrinks like $1/\sqrt{n}$ and is larger when $\rho_3/\sigma^3$ is large, that is, for skewed or heavy-tailed sources. It equals about 1.30 for the uniform law and $12/e - 2 \approx 2.41$ for the exponential law.

The figure averages $n$ draws from the source you choose, 4,000 times, standardises each average and draws the histogram against the standard normal density. The first readout is the Kolmogorov distance, the largest gap between the two distribution functions. With the exponential source and $n = 10$ it is about 0.05, and at $n = 100$ about 0.02, which is close to the 0.014 that sampling noise alone produces with 4,000 averages. Switch to the Bernoulli source with $p = 0.1$, a very skewed coin: the distance is about 0.24 at $n = 10$ and still about 0.09 at $n = 100$. Berry–Esseen is conservative, since for the exponential source at $n = 10$ it would allow 0.36, but its message is the one the figure shows: skewed sources converge more slowly. The second readout, the simulated standard deviation of the average, matches $\sigma/\sqrt{n}$ at every $n$, which is the weak law at work.

Where the theorems are used

A Monte Carlo price is a sample mean $\bar X_n$ of discounted payoffs. The strong law says that it converges to the true price. The central limit theorem gives the error bar: the estimate lies within $\pm 1.96\,\sigma/\sqrt{n}$ of the truth in about 95% of runs, which is the band that returns when the track prices options by simulation. Because the error falls like $1/\sqrt{n}$, every extra correct digit costs a hundred times as many draws.

The same theorem is behind the Brownian limit. A random walk with steps of mean 0 and variance 1, observed after $n$ steps and divided by $\sqrt{n}$, is a standardised sum, so its distribution at a fixed time is approximately normal. Brownian motion is the continuous-time object whose every time slice has exactly that normal distribution.

Summary

• The sample mean of i.i.d. draws has mean $\mu$ and standard error $\sigma/\sqrt{n}$.
• The weak law (by Chebyshev) says the average converges in probability; the strong law says the whole sequence of averages converges almost surely, needing only a finite mean.
• The central limit theorem says the standardised average becomes normal, whatever the source, provided the variance is finite.
• Berry–Esseen bounds the error by a constant times $1/\sqrt{n}$; skewed sources converge more slowly.

The next lesson, "Probability spaces, σ-algebras and random variables", makes precise what "with probability one" and "random variable" mean.