Limit theorems §

Convergence in distribution is the weakest: it only requires the CDFs to converge, not the random variables themselves. It is the natural mode for the CLT because it captures the shape of the limiting law without requiring joint construction.

A useful sufficient condition for a.s. convergence: if $\sum_n P(|X_n - X| > \varepsilon) < \infty$ for every $\varepsilon > 0$, then $X_n \to X$ a.s. (Borel–Cantelli lemma).

Convergence in $L^p$ is the strongest: it implies convergence of moments. In particular, $L^2$ convergence means the variance of the difference goes to zero.

Worked example (why the modes differ). Let $U$ be uniform on $(0,1)$ and define $X_n = n \cdot \mathbf{1}_{U \le 1/n}$. Then $X_n \to 0$ in probability and in distribution (for any $\varepsilon > 0$, $P(|X_n| > \varepsilon) = 1/n \to 0$), but $X_n \not\to 0$ a.s. (for every outcome $U$, $X_n = n$ infinitely often) and not in $L^1$ (since $\mathbb{E}[X_n] = 1$ for all $n$). This single example separates all four modes.

Authoritative sources

• Convergence of random variables (Wikipedia)
• Borel–Cantelli lemma (Wikipedia)

The weak LLN follows from Chebyshev’s inequality when $\operatorname{Var}(X_1) < \infty$: $P(|\bar{X}_n - \mu| > \varepsilon) \leq \sigma^2/(n\varepsilon^2) \to 0$ (see Random variables and expectation).

The strong LLN requires deeper tools (Kolmogorov’s maximal inequality or the martingale convergence theorem). It says that for almost every sample path, the empirical average converges to the mean.

The rate of convergence is governed by the tail of the distribution. For finite variance, the deviation is $O_p(1/\sqrt{n})$; for finite $p$-th moment ($p > 1$), it is $O_p(n^{-(p-1)/p})$.

Worked example (fair die). Roll a fair die $n = 100$ times; $\mu = 3.5$ and $\sigma^2 = 35/12 \approx 2.917$. Chebyshev’s inequality gives

$P(|\bar{X}_{100} - 3.5| > 0.5) \leq \frac{35/12}{100 \times 0.5^2} \approx 0.117$,

so the sample average is within half a point of 3.5 with probability at least 88%, and the bound improves like $1/n$. (The CLT gives the far sharper value $\approx 2(1 - \Phi(2.93)) \approx 0.003$: Chebyshev is universal but loose.)

Authoritative sources

• Law of large numbers (Wikipedia)
• Chebyshev’s inequality (Wikipedia)

The CLT says that the sum of many independent, identically distributed, finite-variance random variables, properly normalized, converges in distribution to a normal. The normal is the unique stable distribution with finite variance (up to location and scale).

Proof sketch via MGFs. Center the variables: let $Y_i = X_i - \mu$, so $\mathbb{E}[Y_i] = 0$ and $\operatorname{Var}(Y_i) = \sigma^2$. The MGF of the normalized sum $S_n/(\sigma\sqrt{n})$ factors as $M_{S_n/(\sigma\sqrt{n})}(t) = [M_{Y_1}(t/(\sigma\sqrt{n}))]^n$. Expanding the MGF of the centered variable,

$M_{Y_1}(u) = 1 + \mathbb{E}[Y_1]\,u + \frac{\sigma^2 u^2}{2} + o(u^2) = 1 + \frac{\sigma^2 u^2}{2} + o(u^2)$,

and plugging in $u = t/(\sigma\sqrt{n})$ gives $[M_{Y_1}(t/(\sigma\sqrt{n}))]^n \to e^{t^2/2}$ as $n \to \infty$ — the MGF of $\mathcal{N}(0,1)$. (Note: plugging in the MGF of $X_1$ itself, which contains the mean $\mu$, would give the wrong limit $e^{\mu t}$; it is the centered variable that must be used.) Since MGF convergence (in a neighborhood of 0) implies convergence in distribution, the normalized sum converges to $\mathcal{N}(0,1)$.

Lindeberg condition. For independent (not identically distributed) $X_i$ with variances $\sigma_i^2$ and $s_n^2 = \sum \sigma_i^2$, the CLT holds if for every $\varepsilon > 0$:

$$\frac{1}{s_n^2}\sum_{i=1}^n \mathbb{E}[X_i^2 \cdot \mathbf{1}_{|X_i| > \varepsilon s_n}] \to 0$

This condition says no single variable dominates the sum.

Confidence intervals. The CLT is the justification for the standard 95% confidence interval: since $\sqrt{n}(\bar{X}_n - \mu)/\sigma \xrightarrow{d} \mathcal{N}(0,1)$ and $P(|Z| \le 1.96) \approx 0.95$, the interval $\bar{X}_n \pm 1.96\,\sigma/\sqrt{n}$ (or $\bar{X}_n \pm 1.96\,s/\sqrt{n}$ with the sample standard deviation $s$, by Slutsky’s theorem) covers the true $\mu$ with probability approaching 95%. This is the workhorse of Statistical inference.

Extensions. The theorem extends to the multivariate case (vector-valued sums converge to a multivariate normal with covariance the sum of the individual covariances) and to certain dependent sequences: for stochastic processes such as mixing or martingale-difference sequences, CLTs hold under suitable conditions controlling the dependence (e.g. strong mixing with summable mixing coefficients).

The CLT is the reason the normal distribution appears everywhere: measurement errors, sampling distributions, queue lengths, and diffusion limits all reduce to sums of many small independent contributions. See Distributions for the normal family.

The LIL refines the LLN by giving the exact rate at which the sample average approaches the mean. While the CLT says the typical deviation is $O(1/\sqrt{n})$, the LIL says the largest deviations (over all $n$ up to $N$) are of order $\sqrt{2 \log \log N / N}$.

The double logarithm $\log \log n$ appears because the events $\{S_n > c\sqrt{n \log \log n}\}$ are not independent across $n$; the Borel–Cantelli lemma applied at geometrically spaced times $n_k = \lfloor e^{e^k}\rfloor$ produces the $\log \log$ factor.

The LIL is a sharp a.s. statement: the sample path crosses the envelope $\pm\sigma\sqrt{2n \log \log n}$ infinitely often, but exceeds it only finitely often. The picture above shows one simulated sample path of a random walk with standard deviation σ = 1: its envelope of maximal excursions grows like the dashed curves — the path comes arbitrarily close to $\pm\sqrt{2n\log\log n}$ infinitely often, yet stays inside them eventually.

Worked example (how slow the envelope grows). For σ = 1: at $n = 10^6$ the envelope is $\sqrt{2 \cdot 10^6 \cdot \ln \ln 10^6} \approx 2292$, while the standard deviation of $S_n$ is only $\sqrt{n} = 1000$. At $n = 10^{12}$ the envelope is about $3.7 \times 10^6$ versus $\sqrt{n} = 10^6$: the correction factor $\sqrt{2\log\log n}$ grows extremely slowly, which is why the LIL is invisible on moderate samples.

Authoritative sources

• P. Hartman & A. Wintner (1941), On the law of the iterated logarithm
• A. N. Kolmogorov (1929), Über das Gesetz des iterierten Logarithmus

Each flip is $X_i \sim \text{Bernoulli}(1/2)$, so $\mu = 1/2$, $\sigma^2 = 1/4$.

By the CLT: $\sqrt{n}(\hat{p}_n - 1/2) \xrightarrow{d} \mathcal{N}(0, 1/4)$.

For $n = 10000$: $\sqrt{n} = 100$, so $100(\hat{p}_n - 1/2) \approx \mathcal{N}(0, 1/4)$, i.e. $\hat{p}_n - 1/2 \approx \mathcal{N}(0, 1/(4 \times 10000)) = \mathcal{N}(0, 2.5 \times 10^{-6})$.

Standard deviation: $\sigma_{\hat{p}} = 1/(2 \times 100) = 0.005$.

$$P(|\hat{p}_n - 1/2| > 0.05) \approx P(|Z| > 0.05/0.005) = P(|Z| > 10) \approx 2 \times 7.6 \times 10^{-24} \approx 0$

The probability is essentially zero: with 10 000 flips, the sample proportion is almost certainly within 5 percentage points of 1/2. The CLT quantifies this with a normal tail.