Laws of Large Numbers

The law of large numbers is the theorem that connects the axioms to the practice that motivated them: the average of many independent copies of a random variable approaches its expectation. It comes in two forms — weak (convergence in probability) and strong (almost surely) — differing only in the mode of convergence, and the gap between them is the difference between a statement about each large $n$ and a statement about the whole infinite sequence.

§5 states carefully what the theorem does not do, since it is the result most often enlisted in claims it cannot support.

References: Durrett, Probability, ch. 2; Williams, Probability with Martingales, ch. 12; Etemadi (1981) for the pairwise-independent strong law.

Throughout, $X_1,X_2,\dots$ are random variables and $S_n=X_1+\cdots +X_n$, ${\bar{X}}_n=S_n/n$.

1. The Weak Law

Weak law (i.i.d., finite variance). If the $X_i$ are uncorrelated with common mean $\mu$ and variance ${\sigma }^2<\infty$, then ${\bar{X}}_n\stackrel{P}{\to }\mu$.

Proof. $E[{\bar{X}}_n]=\mu$ and, by uncorrelatedness, $\mathrm{Var}({\bar{X}}_n)={\sigma }^2/n$ (expectation.md §3). Chebyshev gives

$$P(|{\bar{X}}_n-\mu |>\epsilon )\le \frac{{\sigma }^2}{n{\epsilon }^2}⟶0.\square$$

Three lines, and no independence beyond uncorrelatedness. The finite-variance hypothesis can be removed:

Khinchin's weak law. If the $X_i$ are i.i.d. with $E|X_1|<\infty$ and mean $\mu$, then ${\bar{X}}_n\stackrel{P}{\to }\mu$.

Proof idea. Truncate at level $n$: $Y_i=X_i{1}_{|X_i|\le n}$. The truncated variables have variance $o(n)$ by dominated convergence, so Chebyshev applies to them, while $P(X_i\ne Y_i\text{ for some }i\le n)\le nP(|X_1|>n)\to 0$ because $E|X_1|<\infty$. $\square$

Truncation is the standard device throughout this part: replace a variable with no moments by a bounded one, control the error by a tail estimate, let the truncation level grow.

2. The Strong Law

Kolmogorov's strong law. Let $X_1,X_2,\dots$ be i.i.d. with $E|X_1|<\infty$ and $E[X_1]=\mu$. Then

$${\bar{X}}_n\stackrel{\text{a.s.}}{\to }\mu .$$

Conversely, if $E|X_1|=\infty$ then ${\mathrm{limsup}}_n|{\bar{X}}_n|=\infty$ a.s., so integrability is necessary as well as sufficient.

Proof sketch (Etemadi's argument). Reduce to $X_i\ge 0$ by splitting into $X_i^{\pm }$. Truncate $Y_i=X_i{1}_{\{X_i\le i\}}$; the first Borel–Cantelli lemma with ${\sum }_{i}P(X_i\ne Y_i)={\sum }_{i}P(X_1>i)\le E[X_1]<\infty$ (independence.md §5) shows the two sequences have the same a.s. limit behaviour. Along a geometric subsequence $n_k=\lfloor {\alpha }^k\rfloor$ ($\alpha >1$), Chebyshev plus a variance estimate gives a summable bound, so Borel–Cantelli again yields a.s. convergence along $n_k$; monotonicity of the partial sums fills the gaps, and $\alpha \downarrow 1$ completes the proof. $\square$

Two features of this proof are worth extracting, since they recur:

• Borel–Cantelli is what upgrades "in probability" to "almost surely". A summable sequence of failure probabilities means only finitely many failures occur, which is an almost-sure statement about the whole sequence. This is the place countable additivity is spent.
• Only pairwise independence is used. Etemadi's theorem holds for pairwise independent identically distributed integrable sequences — a genuine strengthening of Kolmogorov's original, and a reminder that "independent" in a theorem statement should be read for exactly what it is (independence.md §1).

Necessity of integrability. If $E|X_1|=\infty$ then ${\sum }_{n}P(|X_n|>n)=>\infty$, so by the second Borel–Cantelli lemma $|X_n|>n$ infinitely often a.s.; since $|X_n|/n=|S_n/n-(S_{n-1}/n)|$, the averages cannot converge. The Cauchy law is the standard illustration: ${\bar{X}}_n$ has the same Cauchy law for every $n$ and converges to nothing.

3. Which Hypotheses Do What

4. The Ergodic Theorem

Independence is far more than the law of large numbers needs. The general statement replaces it with stationarity plus a triviality condition on invariant events.

Let $T:\Omega \to \Omega$ be measure preserving ($P(T^{-1}A)=P(A)$), and call $A$ invariant if $T^{-1}A=A$. $T$ is ergodic if every invariant event has probability $0$ or $1$.

Birkhoff's pointwise ergodic theorem (stated). For $X\in L^1$ and $T$ measure preserving,

$$\frac{1}{n}\sum _{k=0}^{n-1}X(T^k\omega )\stackrel{\text{a.s. and }{L}^1}{\to }E[X\mid \mathcal{I}],$$

where $\mathcal{I}$ is the invariant $\sigma$-algebra. If $T$ is ergodic, the limit is the constant $E[X]$.

An i.i.d. sequence is the shift on a product space, which is ergodic (indeed mixing) by Kolmogorov's zero–one law (zero-one-laws.md), so the strong law is the ergodic theorem's special case. Note what the general statement concedes: without ergodicity the limit is a random variable, the conditional expectation given the invariant events — a system that decomposes into non-communicating components converges to a per-component average. This is exactly the structure that reappears in de Finetti's theorem (exchangeability-de-finetti.md), where the limit is the mixing parameter.

5. What the Law Does and Does Not Say

• It is a theorem about $P$. The convergence asserted is convergence $P$-almost surely, i.e. off a set the given measure assigns zero. The theorem therefore presupposes $P$ and cannot be used to define it in terms of frequencies without circularity. What it does establish is an internal consistency property: the axioms of kolmogorov-axioms.md imply that the frequency of an event in independent repetitions converges to its probability — take $X_i=1_{A_i}$, giving $\frac{1}{n}\#\{i\le n:A_i\}\to P(A)$ a.s.
• "Almost surely" is not "surely". The set where convergence fails is non-empty (it contains, e.g., the all-heads sequence); it merely has measure zero. No finite observation can distinguish a null set from an empty one, which is why the theorem gives no bound on any particular run.
• There is no rate without further hypotheses, and no self-correction. The "gambler's fallacy" — that a deficit of heads must be repaid — is false: $S_n-n/2$ is a martingale with $E[S_n-n/2]=0$ and $\mathrm{Var}\sim n/4$, so the absolute deviation grows like $\sqrt{n}$ while the average deviation shrinks like $1/\sqrt{n}$. The CLT quantifies exactly this, and the law of the iterated logarithm, $$\underset{n}{\mathrm{limsup}}\frac{S_n-n\mu }{\sqrt{2{\sigma }^{2}n\log \log n}}=1\text{a.s.},$$ gives the sharp almost-sure envelope.
• It says nothing about a single trial. The statement is about the sequence, and every rearrangement of the axioms that tries to extract a single-case claim needs an additional principle that is not in the axioms.

6. Where This Is Used

• The central limit theorem — the next-order term: fluctuations around the limit.
• Zero–one laws — why the a.s. limit is a constant.
• Martingales — a convergence theorem needing neither independence nor identical distribution.
• Algorithmic randomness — the frequency behaviour the strong law asserts for a.e. sequence, imposed instead on individual sequences.