The law of large numbers, the central limit theorem and confidence intervals

Before this lesson: lesson 02 (expectation, variance and their rules), lesson 03 (the common distributions and moment generating functions) and lesson 04 (the variance of a sum). Time: about 75 minutes, plus the notebook.

---

Why this matters #

• Model evaluation. A test accuracy of 0.91 on 500 examples is a sample mean of 0/1 values. Its standard error, about $\sqrt{0.91 \cdot 0.09/500} \approx 0.013$, tells you whether 0.91 is really better than another model's 0.90 (here: not clearly).
• A/B tests. The conversion rate of each version of a web page is a sample mean. The usual z-test and its sample-size formula come from the central limit theorem (lesson 12).
• Monte Carlo. A Monte Carlo estimate, such as an expected reward in reinforcement learning or an integral in physics, is a sample mean. Its error is $\sigma_f/\sqrt n$ in any dimension (lesson 14).
• Stochastic gradient descent. A minibatch gradient is the mean of $B$ per-example gradients. Its noise has standard deviation proportional to $1/\sqrt B$ (optimization 05).
• Error bars in papers. "Mean ± standard error over 5 seeds" is a confidence interval in disguise, and with only 5 values it needs Student's $t$, not 1.96.

1. Predict first #

2. The picture #

A statistic is a random variable #

Take a population with mean $\mu$ and standard deviation $\sigma$: for example, the time (in minutes) that visitors spend on a web page. Draw a sample of $n$ values and compute its mean $\bar x$. A second sample gives a different $\bar x$. The distribution of $\bar X_n$ over many repeated samples is its sampling distribution.

Two facts describe it (we prove them in section 3):

• its centre is the true mean: $\mathbb{E}[\bar X_n] = \mu$;
• its spread is the standard error $\operatorname{SE} = \sigma/\sqrt n$, much smaller than the spread $\sigma$ of the data.

Interactive figure: loading…

The law of large numbers: running means settle down #

Flip a coin again and again, and after each flip compute the fraction of heads so far. This running mean jumps a lot at first and then settles near $0.5$. The band $\mu \pm 2\sigma/\sqrt n$ shows how fast: its width falls like $1/\sqrt n$, so 100 times more flips give a 10 times narrower band.

Interactive figure: loading…

The central limit theorem: sums look Gaussian #

Why a bell shape? A Galton board shows the mechanism. Each ball hits $R$ pegs and goes left or right with probability $1/2$ at each one. The final bin is the number of right steps: a sum of $R$ independent coin flips, so a Binomial($R$, 1/2) count. Many small independent pushes add up to a bell curve.

Interactive figure: loading…

The same happens for sums of almost any variables, not only coin flips. To compare different $n$, we standardise: subtract the mean $n\mu$ of the sum and divide by its SD $\sigma\sqrt n$,

$Z_n$ always has mean 0 and variance 1. The central limit theorem says that its shape approaches the standard normal $\mathcal N(0, 1)$.

Interactive figure: loading…

3. Definitions and main results #

Throughout, $X_1, \dots, X_n$ are i.i.d. (independent and identically distributed) with mean $\mu$ and variance $\sigma^2$, and

The mean and the standard error #

Theorem. $\mathbb{E}[\bar X_n] = \mu$ and $\operatorname{Var}(\bar X_n) = \sigma^2/n$.

Proof.

1. By linearity of expectation, $\mathbb{E}[S_n] = \sum_i \mathbb{E}[X_i] = n\mu$, so $\mathbb{E}[\bar X_n] = \mu$.
2. The $X_i$ are independent, so all covariances are 0 and the variances add (lesson 04): $\operatorname{Var}(S_n) = n\sigma^2$.
3. $\operatorname{Var}(cY) = c^2 \operatorname{Var}(Y)$ with $c = 1/n$ gives $\operatorname{Var}(\bar X_n) = n\sigma^2/n^2 = \sigma^2/n$. $\blacksquare$

The standard error of the mean is $\operatorname{SE}(\bar X_n) = \sigma/\sqrt n$. In practice $\sigma$ is unknown, and we use the estimate $s/\sqrt n$, where $s$ is the sample standard deviation (with $n - 1$).

Standard deviation vs standard error. The SD $\sigma$ describes the spread of the data; it does not shrink with $n$. The SE $\sigma/\sqrt n$ describes the spread of the mean; it shrinks. Report the SD when you describe the data, and the SE (or a confidence interval) when you describe how well you know $\mu$.

Step 2 used only that the variables are uncorrelated. If they are correlated, the variance is larger. With equal pairwise correlation $\rho$, $\operatorname{Var}(\bar X_n) = \frac{\sigma^2}{n}\big(1 + (n - 1)\rho\big)$, which tends to $\rho\sigma^2$, not to 0.

Markov's and Chebyshev's inequalities #

These two inequalities bound a tail probability with only a mean or a variance.

Markov's inequality. If $X \ge 0$ and $a > 0$, then

Proof.

1. For every outcome, $X \ge a\,\mathbf 1\{X \ge a\}$. If $X \ge a$, the right side is $a \le X$. Otherwise it is $0 \le X$; this is where $X \ge 0$ is used.
2. Take expectations of both sides: $\mathbb{E}[X] \ge a\,P(X \ge a)$. $\blacksquare$

Tight case. $X \in \{0, a\}$ with $P(X = a) = q$. Then $P(X \ge a) = q = \mathbb{E}[X]/a$. Equality needs all the mass at $0$ and at $a$, so for most distributions Markov is loose.

Chebyshev's inequality. If $\operatorname{Var}(X) = \sigma^2 < \infty$ and $\mathbb{E}[X] = \mu$, then for every $\varepsilon > 0$

Proof. Apply Markov to the nonnegative variable $Y = (X - \mu)^2$ with threshold $\varepsilon^2$. The events $\{|X - \mu| \ge \varepsilon\}$ and $\{Y \ge \varepsilon^2\}$ are the same, so $P(|X - \mu| \ge \varepsilon) \le \mathbb{E}[Y]/\varepsilon^2 = \sigma^2/\varepsilon^2$. $\blacksquare$

Tight case. $X = \mu \pm \varepsilon$ with probability $\sigma^2/(2\varepsilon^2)$ each, and $X = \mu$ otherwise (this needs $\sigma^2 \le \varepsilon^2$).

With $\varepsilon = k\sigma$: $P(|X - \mu| \ge k\sigma) \le 1/k^2$. So at least 75% of any distribution lies within 2 SD of the mean, and at least 89% within 3 SD. For a Gaussian the true values are 95.4% and 99.7%.

Modes of convergence #

"$\bar X_n$ goes to $\mu$" can mean different things. Let $Y_1, Y_2, \dots$ and $Y$ be random variables.

• In probability: for every $\varepsilon > 0$, $P(|Y_n - Y| > \varepsilon) \to 0$. For large $n$, a big error is unlikely.
• Almost surely (a.s.): $P(\lim_n Y_n = Y) = 1$. Almost every single path converges.
• In distribution: $P(Y_n \le y) \to P(Y \le y)$ at every $y$ where the CDF of $Y$ is continuous. Only the distributions get close, not the values.

Almost surely implies in probability, and in probability implies in distribution. The converses are false in general.

Two counterexamples

• In distribution, not in probability. Let $Y \sim \mathcal N(0, 1)$ and $Y_n = -Y$ for every $n$. Each $Y_n$ has exactly the distribution of $Y$, so $Y_n \to Y$ in distribution. But $|Y_n - Y| = 2|Y|$ does not shrink.
• In probability, not almost surely. Let $Y_n \sim \text{Bernoulli}(1/n)$ be independent. Then $P(Y_n > \varepsilon) = 1/n \to 0$, so $Y_n \to 0$ in probability. But $\sum_n 1/n = \infty$, so by the second Borel–Cantelli lemma $Y_n = 1$ for infinitely many $n$, with probability 1: no path converges.

One exception: convergence in distribution to a constant implies convergence in probability.

The law of large numbers #

Theorem (weak law of large numbers, WLLN). If $X_1, X_2, \dots$ are i.i.d. with mean $\mu$ and finite variance $\sigma^2$, then $\bar X_n \to \mu$ in probability: for every $\varepsilon > 0$, $P(|\bar X_n - \mu| \ge \varepsilon) \to 0$.

Proof.

1. $\mathbb{E}[\bar X_n] = \mu$ and $\operatorname{Var}(\bar X_n) = \sigma^2/n$ (theorem above).
2. Chebyshev applied to $\bar X_n$: $P(|\bar X_n - \mu| \ge \varepsilon) \le \dfrac{\sigma^2}{n\varepsilon^2}$.
3. For fixed $\varepsilon$, the right side goes to 0 as $n \to \infty$. $\blacksquare$

What this proof uses, and what it does not give:

• It needs only uncorrelated variables with equal mean and variance. For correlated data (time series, MCMC samples) the variance of the mean can stay large.
• It needs a finite variance. The WLLN also holds with only a finite mean (Khinchin's theorem), with a different proof.
• The strong law of large numbers says more: $\bar X_n \to \mu$ almost surely, for i.i.d. variables with $\mathbb{E}|X| < \infty$. Its proof is harder; we only state it.
• Without a mean, there is no law of large numbers. For the Cauchy distribution (density $1/(\pi(1 + x^2))$), $\mathbb{E}|X| = \infty$. The mean of $n$ standard Cauchy variables is again standard Cauchy, for every $n$. Averaging does not help at all.

The central limit theorem #

Theorem (CLT). Let $X_1, X_2, \dots$ be i.i.d. with mean $\mu$ and variance $0 < \sigma^2 < \infty$. Then

in distribution, that is, $P(Z_n \le z) \to \Phi(z)$ for every $z$, where $\Phi$ is the standard normal CDF.

How to use it. For large $n$, approximately

LLN vs CLT. The LLN says where $\bar X_n$ goes ($\mu$). The CLT says how the error looks on the scale $\sigma/\sqrt n$: Gaussian. The data do not become Gaussian; only the mean (or the sum) does.

Proof sketch with moment generating functions

Assume that the MGF $M(s) = \mathbb{E}[e^{sX}]$ is finite near 0 (lesson 03). Standardise so that $\mu = 0$ and $\sigma = 1$.

1. $Z_n = \sum_i X_i/\sqrt n$. The $X_i$ are independent, so the MGF of the sum is the product: $M_{Z_n}(t) = M(t/\sqrt n)^n$.
2. Taylor expansion at 0: $M(s) = 1 + s\,\mathbb{E}[X] + \tfrac{s^2}{2}\mathbb{E}[X^2] + o(s^2) = 1 + \tfrac{s^2}{2} + o(s^2)$.
3. Hence $\ln M_{Z_n}(t) = n \ln\big(1 + \tfrac{t^2}{2n} + o(1/n)\big) \to \tfrac{t^2}{2}$, using $\ln(1 + u) = u + o(u)$.
4. $e^{t^2/2}$ is the MGF of $\mathcal N(0, 1)$. If MGFs converge on an interval around 0, the distributions converge (Curtiss' continuity theorem). $\blacksquare$

With only a finite variance the MGF may not exist. The same steps then work with the characteristic function $\mathbb{E}[e^{itX}]$, which always exists, and Lévy's continuity theorem.

How fast? The Berry–Esseen theorem

If also $\rho = \mathbb{E}|X - \mu|^3 < \infty$, then for every $n$

$$\sup_z \big|P(Z_n \le z) - \Phi(z)\big| \le \frac{C\,\rho}{\sigma^3\sqrt n}, \qquad C \le 0.4748 \text{ (Shevtsova, 2011)}.$$

The error of the normal approximation is $O(1/\sqrt n)$, and this rate cannot be improved in general. For a fair coin, $P(S_n = n/2) \approx \sqrt{2/(\pi n)}$: the CDF of $Z_n$ jumps by about $1/\sqrt n$ at 0, and the continuous $\Phi$ cannot follow the jump.

For Exp(1) data the sum is Gamma($n$, 1), so the exact distance can be computed:

$n$	1	4	16	64	256
$\sup_z \lvert P(Z_n \le z) - \Phi(z)\rvert$	0.159	0.067	0.033	0.017	0.008
$\sqrt n \times$ distance	0.159	0.133	0.133	0.133	0.133
Berry–Esseen bound	1.146	0.573	0.287	0.143	0.072

From $n = 4$ on, $\sqrt n$ times the distance is constant, as the theorem predicts. The bound is valid but about 8 times too large here. Skewed data and rare events (large $\rho/\sigma^3$) need a much larger $n$.

From random walks to Brownian motion

Let $X_i = \pm 1$ with probability $1/2$ each, and take steps of size $\sqrt{\Delta t}$ every $\Delta t$ time units. At time $t$ you have made $t/\Delta t$ steps, so the position has variance $(t/\Delta t) \cdot \Delta t = t$. As $\Delta t \to 0$, the CLT makes the position at time $t$ a $\mathcal N(0, t)$ variable, and the whole path converges to Brownian motion (Donsker's theorem). This is why noise in stochastic differential equations scales like $\sqrt{\Delta t}$, not $\Delta t$ (ML for science 12).

When the CLT fails or is slow.

• Infinite variance: Cauchy, or Pareto with tail index below 2. There is no Gaussian limit.
• Strong dependence: a time series with long memory, or samples that share a common error.
• Skewness and rare events: the approximation is poor until $n$ is large. For a proportion, a common rule is to want $np \ge 10$ and $n(1 - p) \ge 10$.

Bound or approximation? For 100 fair coin flips, "60 or more heads" means $\bar X_n - 0.5 \ge 0.1$:

method	value	kind
Chebyshev, $\operatorname{Var}(\bar X_n)/\varepsilon^2 = 0.0025/0.01$	0.25	bound (always valid)
CLT, $P(Z \ge 2)$ with $Z = 0.1/0.05$	0.0228	approximation
exact binomial, $P(S_{100} \ge 60)$	0.0284	exact

Chebyshev is valid but 9 times too large. The CLT is close, but it is not a bound: here it is below the truth. Lesson 07 builds bounds that are valid and much tighter.

Confidence intervals #

Known $\sigma$. By the CLT, $P\big(|\bar X_n - \mu| \le 1.96\,\sigma/\sqrt n\big) \approx 0.95$, because $P(|Z| \le 1.96) = 0.95$ for $Z \sim \mathcal N(0, 1)$. Read the event the other way round: $|\bar X_n - \mu| \le 1.96\,\sigma/\sqrt n$ is the same as $\mu \in \big[\bar X_n - 1.96\,\sigma/\sqrt n,\ \bar X_n + 1.96\,\sigma/\sqrt n\big]$. So

is an (approximate) 95% confidence interval for $\mu$. For a level $1 - \alpha$, replace 1.96 by the quantile $z_{1 - \alpha/2}$ (1.645 for 90%, 2.576 for 99%).

What "95%" means. A confidence interval is a procedure: a rule that turns data into an interval. Its coverage is the probability, before you see the data, that the random interval contains the fixed number $\mu$. "95%" means: if you repeat the whole experiment many times, about 95% of the intervals contain $\mu$. After you computed one interval, say $[2.1, 3.4]$, nothing is random any more: $\mu$ is in it or not. In the frequentist view $\mu$ is a fixed number, so "$P(2.1 \le \mu \le 3.4) = 0.95$" is not a correct statement. (A Bayesian credible interval (lesson 10) does make such a statement, given a prior.)

Interactive figure: loading…

Unknown $\sigma$: Student's $t$. In practice we replace $\sigma$ by the sample SD $s$. This adds uncertainty, and the interval with 1.96 becomes too short for small $n$. For normal data the exact distribution is known:

Student's $t$ distribution with $n - 1$ degrees of freedom. It is symmetric like $\mathcal N(0, 1)$, but with heavier tails; as $n \to \infty$ it approaches $\mathcal N(0, 1)$. The t-interval is

Some 97.5% quantiles: $t_{1} = 12.71$, $t_{4} = 2.776$, $t_{9} = 2.262$, $t_{29} = 2.045$, $t_{99} = 1.984$, and $z = 1.960$.

For normal data the t-interval has coverage exactly 0.95 for every $n$. For other data it is approximate. A simulation with 200,000 data sets per row (Monte Carlo error about ±0.001) gives:

data	$n$	t-interval	$1.96 \cdot s/\sqrt n$
normal	10	0.950	0.918
normal	30	0.950	0.940
exponential (skewed)	10	0.900	0.869
exponential (skewed)	30	0.926	0.917
exponential (skewed)	100	0.942	0.939

Two lessons from the table. With small $n$, use $t$, not 1.96. And with skewed data, even $t$ under-covers until $n$ is large; the bootstrap (lesson 12) is one fix.

Intervals for a proportion #

For 0/1 data (clicked or not, correct or not), $\bar X_n = \hat p$ is the fraction of ones, and $\sigma^2 = p(1 - p)$. The Wald interval plugs $\hat p$ into the SE:

It fails for small $n$ or for $p$ near 0 or 1. Example: $n = 50$ and $p = 0.02$. With probability $0.98^{50} \approx 0.36$ you see no success at all; then $\hat p = 0$ and the interval is $[0, 0]$, which misses $p$. The exact coverage (a sum over the binomial PMF) is only 0.635, not 0.95.

The Wilson interval

Instead of plugging $\hat p$ into the SE, solve $|\hat p - p| \le z\sqrt{p(1 - p)/n}$ for $p$ (a quadratic inequality in $p$). With $z = 1.96$, the solution is the Wilson interval

$$\frac{\hat p + \frac{z^2}{2n}}{1 + \frac{z^2}{n}} \;\pm\; \frac{z}{1 + \frac{z^2}{n}}\sqrt{\frac{\hat p(1 - \hat p)}{n} + \frac{z^2}{4n^2}}.$$

Its centre is pulled towards $1/2$, and it is never $[0, 0]$. Exact coverage at $n = 50$:

$p$	Wald	Wilson
0.5	0.935	0.935
0.24	0.919	0.934
0.02	0.635	0.922

Use Wilson (or the exact Clopper–Pearson interval) by default. In Python: statsmodels.stats.proportion.proportion_confint(k, n, method="wilson").

Error bars for Monte Carlo, and the delta method #

Monte Carlo. To estimate $I = \mathbb{E}[f(X)]$, draw $X_1, \dots, X_n$ and average: $\hat I = \frac1n \sum_i f(X_i)$. This is a sample mean, so the CLT gives the error bar

where $s_f$ is the sample SD of the values $f(X_i)$. The rate $1/\sqrt n$ does not depend on the dimension of $X$; only $\sigma_f$ does. One more correct digit costs 100 times more samples.

The delta method. Often we need a function of a mean: the log-odds of a click rate, the ratio of two means, $\bar X^2$. If $\sqrt n(\bar X_n - \mu) \to \mathcal N(0, \sigma^2)$ and $g$ is differentiable at $\mu$ with $g'(\mu) \ne 0$, then

so

Why: the first-order Taylor expansion $g(\bar X_n) \approx g(\mu) + g'(\mu)(\bar X_n - \mu)$ is a linear function of $\bar X_n$, and a linear function multiplies the SD by $|g'(\mu)|$. The remainder is of smaller order than $1/\sqrt n$. In $d$ dimensions the variance is $\nabla g(\mu)^\top \Sigma\, \nabla g(\mu)/n$. The delta method is first order: it ignores the bias and skewness that a curved $g$ adds.

Answers to section 1. (1) About 0.03: the exact value is 0.0284. The CLT gives $P(Z \ge 2) = 0.0228$, since 60 heads is $(0.6 - 0.5)/0.05 = 2$ standard errors above the mean. Chebyshev gives only the bound 0.25. (2) No. The 95% describes how often the procedure covers $\mu$ in repeated experiments. A computed interval contains the fixed $\mu$ or not. (3) 100 times more. The width of the interval is proportional to $1/\sqrt n$.

4. Worked example #

(a) A t-interval for exam scores. Eight students get the scores $72, 85, 64, 90, 78, 69, 81, 77$. We want a 95% confidence interval for the mean score $\mu$ of all students who take this exam.

1. Mean: $\bar x = 616/8 = 77$.
2. Deviations: $-5, 8, -13, 13, 1, -8, 4, 0$. Squares: $25, 64, 169, 169, 1, 64, 16, 0$, with sum $508$.
3. Sample variance: $s^2 = 508/7 = 72.57$, so $s = 8.52$.
4. Standard error: $s/\sqrt 8 = 8.52/2.828 = 3.01$.
5. $n - 1 = 7$ degrees of freedom: $t_{7,\,0.975} = 2.365$.
6. Half-width: $2.365 \cdot 3.01 = 7.12$. Interval: $77 \pm 7.12 = [69.9,\ 84.1]$.

With 1.96 instead of 2.365 the half-width would be $5.90$: the interval would be 17% too short, and its coverage for normal data would be below 0.95.

(b) The click rate of a button. A web page shows a new button to $n = 50$ visitors; $12$ click it.

1. Estimate: $\hat p = 12/50 = 0.24$.
2. Standard error: $\sqrt{\hat p(1 - \hat p)/n} = \sqrt{0.24 \cdot 0.76/50}$, and this is $\sqrt{0.003648} = 0.0604$.
3. Half-width: $1.96 \cdot 0.0604 = 0.118$. Wald interval: $0.24 \pm 0.118 = [0.122,\ 0.358]$.
4. Wilson interval (formula above): $[0.143,\ 0.374]$, slightly shifted towards $1/2$.

Delta method on the log-odds. Logistic regression works with $\theta = \ln\frac{p}{1 - p}$. With $g(p) = \ln\frac{p}{1 - p}$ we have $g'(p) = \frac{1}{p(1 - p)}$, so

and with the numbers

$\hat\theta = \ln(0.24/0.76) = -1.153$. The half-width is $1.96 \cdot 0.331 = 0.649$, so the 95% interval is $[-1.802,\ -0.504]$. Map both ends back with the logistic function $p = 1/(1 + e^{-\theta})$: $[0.142,\ 0.377]$. This interval is not symmetric around 0.24, and it always stays inside $(0, 1)$.

How many visitors for $\pm 0.05$? We want $1.96\sqrt{p(1 - p)/n} \le 0.05$. The worst case is $p = 1/2$, so $n \ge (1.96 \cdot 0.5/0.05)^2 = 384.2$: 385 visitors. This is a CLT approximation. Chebyshev gives a guarantee for $P(|\hat p - p| \ge 0.05) \le 0.05$, but it needs $n \ge 0.25/(0.05 \cdot 0.05^2) = 2000$. Lesson 07 finds a guarantee with 738.

(c) What the i.i.d. assumption hides. Suppose the 50 visitors come in groups of friends who influence each other, and every pair of clicks has correlation $\rho = 0.2$. Then $\operatorname{Var}(\hat p) = \frac{\sigma^2}{50}(1 + 49 \cdot 0.2) = 0.216\,\sigma^2$, against $0.02\,\sigma^2$ for independent visitors. The true SE is $\sqrt{10.8} \approx 3.3$ times larger than the formula says.

5. In code #

NumPy and SciPy check the worked example. The notebook for this lesson has these cells and the exercises.

import numpy as np
from scipy import stats

# (a) exam scores: t-interval for the mean
x = np.array([72, 85, 64, 90, 78, 69, 81, 77.])
n, m, s = len(x), x.mean(), x.std(ddof=1)
q = stats.t.ppf(0.975, n - 1)
print(m, round(s, 2), round(s / np.sqrt(n), 2), round(q, 3))        # 77.0 8.52 3.01 2.365
print(np.round(stats.t.interval(0.95, n - 1, loc=m, scale=s / np.sqrt(n)), 2))   # [69.88 84.12]

# (b) 12 clicks out of 50 visitors: Wald interval and the delta method on the log-odds
k, n = 12, 50
p = k / n
se = np.sqrt(p * (1 - p) / n)
print(round(se, 4), np.round([p - 1.96 * se, p + 1.96 * se], 3))     # 0.0604 [0.122 0.358]
theta, se_t = np.log(p / (1 - p)), 1 / np.sqrt(n * p * (1 - p))
lo, hi = theta - 1.96 * se_t, theta + 1.96 * se_t
print(round(theta, 3), round(se_t, 3), np.round(1 / (1 + np.exp(-np.array([lo, hi]))), 3))
# -1.153 0.331 [0.142 0.377]

# (c) Monte Carlo estimate of pi with a CLT error bar
rng = np.random.default_rng(1)
u = rng.random((10_000, 2))
f = 4.0 * (np.sum(u**2, axis=1) <= 1)
print(f.mean(), round(1.96 * f.std(ddof=1) / np.sqrt(len(f)), 3))    # 3.1564 0.032  (one run)

# (d) coverage of the Wald interval for a rare event, exact
z = stats.norm.ppf(0.975)
k = np.arange(51); ph = k / 50
cover = np.abs(ph - 0.02) <= z * np.sqrt(ph * (1 - ph) / 50)
print(round(stats.binom.pmf(k, 50, 0.02)[cover].sum(), 3))            # 0.635, not 0.95

In (c) the error bar $\pm 0.032$ contains $\pi = 3.1416$. The SD of one value of $f$ is $4\sqrt{(\pi/4)(1 - \pi/4)} = 1.642$, so every run of 10,000 points has a half-width close to $1.96 \cdot 1.642/100 = 0.032$.

6. Where it shows up #

• Comparing models. Two classifiers with test accuracies 0.912 and 0.905 on 2,000 examples differ by 0.007. Each accuracy has a standard error of about 0.006, so the difference is not clear. Report intervals, and use a paired test on the same examples (lesson 11).
• Seeds in deep learning. Results over 3–5 random seeds are a tiny sample. Use the $t$ quantile ($t_{4} = 2.776$ for 5 seeds), not 1.96, or report all values.
• A/B tests. The sample size per arm, $n \approx 16\sigma^2/\Delta^2$ for a difference $\Delta$ at 5% level and 80% power, comes from the CLT (lesson 12).
• Monte Carlo and MCMC. Error bars $1.96\,s_f/\sqrt n$ for integrals and expected rewards; for correlated MCMC samples, $n$ is replaced by an effective sample size (lesson 15).
• Ensembles and averaging in science. Averaging $n$ independent sensor readings or ensemble members reduces the noise by $\sqrt n$, but a shared error (the same model physics, the same calibration) does not average out.
• Batch size in SGD. The gradient noise falls like $1/\sqrt B$, which is behind heuristics that scale the learning rate with the batch size.

7. Common mistakes #

• Mixing up SD and SE. The SD $\sigma$ of the data does not shrink with $n$; the SE $\sigma/\sqrt n$ of the mean does. Error bars that use the SD are not confidence intervals for the mean.
• "The data become Gaussian for large $n$." No. The CLT is about the distribution of the mean (or sum). A histogram of 10,000 exponential values is still exponential.
• "There is a 95% probability that $\mu$ is in this interval." For a computed confidence interval this is wrong; the 95% belongs to the procedure.
• Using 1.96 with a small sample. With $n = 10$ and estimated $s$, the coverage is about 0.92. Use $t_{n-1}$.
• Using the Wald interval for rare events. At $n = 50$, $p = 0.02$ its coverage is 0.635. Use Wilson.
• Treating the CLT as a bound. It is an approximation with error $O(1/\sqrt n)$; for 100 coin flips it was below the exact tail. Use a concentration inequality when you need a guarantee.
• Forgetting dependence. $\operatorname{Var}(\bar X_n) = \sigma^2/n$ needs uncorrelated data. Time series, MCMC samples, users in the same group, or repeated measurements of one patient break it.
• Markov on a variable that can be negative. Markov needs $X \ge 0$. Apply it to $|X|$ or $(X - \mu)^2$ instead.

8. Check yourself #

1. $X \ge 0$ and $\mathbb{E}[X] = 3$. Bound $P(X \ge 12)$. Can the bound be reached?
   Answer

   Markov gives $3/12 = 0.25$. Yes: $X \in \{0, 12\}$ with $P(X = 12) = 1/4$ has mean 3 and $P(X \ge 12) = 0.25$.
2. A die is rolled 100 times. Use Chebyshev to bound $P(|\bar X - 3.5| \ge 0.5)$.
   Answer

   One roll has $\sigma^2 = 35/12 = 2.917$. So $\operatorname{Var}(\bar X) = 0.02917$ and $P \le 0.02917/0.25 = 0.117$. (The CLT gives about $2P(Z \ge 0.5/0.171) = 2P(Z \ge 2.93) \approx 0.003$.)
3. 25 measurements have $\bar x = 10.4$ and $s = 2.0$. Give a 95% confidence interval for $\mu$ ($t_{24,\,0.975} = 2.064$).
   Answer

   $\operatorname{SE} = 2.0/5 = 0.4$, so $10.4 \pm 2.064 \cdot 0.4 = 10.4 \pm 0.83 = [9.57, 11.23]$.
4. A Monte Carlo estimate with $n = 10{,}000$ samples has the error bar $\pm 0.02$. How many samples give $\pm 0.005$?
   Answer

   The error bar must shrink by 4, so $n$ must grow by $4^2 = 16$: 160,000 samples.
5. $\bar X$ is the mean of $n = 100$ i.i.d. draws with $\mu = 2$ and $\sigma = 1$. Approximate the SD of $\bar X^2$.
   Answer

   Delta method with $g(x) = x^2$, $g'(2) = 4$: $\operatorname{SD}(\bar X^2) \approx 4 \cdot 1/\sqrt{100} = 0.4$.
6. Independent $Y_n \sim \text{Bernoulli}(1/n^2)$. Does $Y_n \to 0$ in probability? Almost surely?
   Answer

   Both. In probability: $P(Y_n = 1) = 1/n^2 \to 0$. Almost surely: $\sum_n 1/n^2 < \infty$, so by the first Borel–Cantelli lemma only finitely many $Y_n$ equal 1, with probability 1. Compare $\text{Bernoulli}(1/n)$, which fails almost surely.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. What is the standard error of the mean of $n$ i.i.d. values with SD $\sigma$?

   Show answer

2. State Chebyshev's inequality.

   Show answer

3. State the weak law of large numbers and the tool of its short proof.

   Show answer

4. State the central limit theorem with its assumptions.

   Show answer

5. Give the 95% confidence interval for a mean with unknown $\sigma$.

   Show answer

6. What does the "95%" of a confidence interval mean?

   Show answer

7. Why does the Wald interval fail for $n = 50$, $p = 0.02$?

   Show answer

8. A Monte Carlo error bar is too wide by a factor 10. How many more samples do you need?

   Show answer

9. State the delta method for $g(\bar X_n)$.

   Show answer

10. Why is the mean of Cauchy samples useless?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "State the CLT. What can break it?" — i.i.d. with finite variance; then the standardised mean tends to $\mathcal N(0, 1)$. It breaks with infinite variance (Cauchy, heavy tails), strong dependence, and it is slow for skewed data and rare events.
• "LLN versus CLT?" — The LLN says $\bar X_n \to \mu$. The CLT says the error $\bar X_n - \mu$ is approximately $\mathcal N(0, \sigma^2/n)$.
• "How many samples to estimate a probability within ±1% at 95%?" — Worst case $p = 1/2$: $(1.96 \cdot 0.5/0.01)^2 = 9604$.
• "What does a 95% confidence interval mean?" — The procedure covers the true value in 95% of repeated experiments. It is not a 95% probability for the one interval you computed.
• "Why is the Monte Carlo error independent of the dimension?" — The estimate is a sample mean with SE $\sigma_f/\sqrt n$; the dimension enters only through $\sigma_f$.
• "Your model gets 0.80 accuracy on 400 test examples. Error bar?" — $\sqrt{0.8 \cdot 0.2/400} = 0.02$, so about $0.80 \pm 0.04$ at 95%.

10. Practice #

The notebook for this lesson has five exercises, each with a check cell and a folded solution:

1. Running means of coin flips, and the fraction of paths inside the band $\mu \pm 2\sigma/\sqrt n$.
2. The KS distance of standardised exponential means to $\mathcal N(0, 1)$, and why $\sqrt n \cdot D$ stays constant.
3. A t-based mean_confidence_interval and its coverage for normal and skewed data.
4. Wald and Wilson intervals for a proportion, and their exact coverage at $p = 0.02$.
5. A Monte Carlo estimate of $\pi$ with a CLT error bar, and the coverage of that error bar.

11. Watch and read #

But what is the Central Limit Theorem?3Blue1Brown · 31 min

The CLT built from sums of dice, with the Galton board and a careful list of the assumptions.

Lecture 29: Law of Large Numbers and Central Limit Theorem | Statistics 110Harvard University · Joe Blitzstein, Statistics 110 · 50 min

The weak law from Chebyshev and the MGF proof of the CLT, the same route as section 3.

Confidence Intervals, Clearly Explained!!!StatQuest with Josh Starmer · 7 min

A short visual answer to "what does a 95% confidence interval mean".

The standard error, Clearly Explained!!!StatQuest with Josh Starmer · 12 min

The difference between the standard deviation of the data and the standard error of the mean.

• Joseph Blitzstein and Jessica Hwang, Introduction to Probability, 2nd edition (free PDF from the authors): §10.1 (inequalities), §10.2 (law of large numbers), §10.3 (central limit theorem), §10.4 (chi-square and Student's $t$).
• Larry Wasserman, All of Statistics: ch. 5 (convergence of random variables, the delta method) and ch. 6 (confidence intervals).
• Art Owen, Monte Carlo theory, methods and examples, ch. 2: the error of simple Monte Carlo, estimating probabilities, and intervals for rare events.