Law of Large Numbers

Theorem 1 (Weak Law of Large Numbers) Let X_1, X_2, \dots be IID with \mathbb{E}[X_i] = \mu. Then \bar{X}_n = \frac{1}{n}\sum_{i=1}^n X_i \xrightarrow{P} \mu.

TipIntuition

Random errors cancel out. The running mean walks toward \mu.

import matplotlib.pyplot as plt
import numpy as np

from random_walk import running_mean

rng = np.random.default_rng(0)
flips = rng.integers(0, 2, size=5_000)

fig, ax = plt.subplots()
ax.plot(running_mean(flips), label=r"$\bar{X}_n$")
ax.axhline(0.5, color="grey", linestyle="--", label=r"$\mu$")
ax.set(xscale="log", xlabel="n", ylabel="running mean")
ax.legend();

Exercises

1. By Chebyshev, bound P(|\bar{X}_n - 0.5| \ge 0.05) for n = 1000 fair coin flips.

NoteSolution

\operatorname{Var}(\bar{X}_n) = \frac{0.25}{n}, so the bound is \frac{0.25}{1000 \cdot 0.05^2} = 0.1.