A Walk Through Kolmogorov's Strong Law of Large Numbers

The Law of Large Numbers is one of those results that feels obvious — average more and more independent trials, and you converge to the mean. But making it rigorous, especially in the strong (almost sure) sense, requires a beautiful chain of ideas: almost sure convergence, Borel-Cantelli lemmas, truncation, and a clever sub-sequence argument.

This post walks through the full proof of Kolmogorov’s Strong Law of Large Numbers (SLLN). We assume only a finite first moment.

Roadmap

Almost sure convergence and “infinitely often” (i.o.)
The Borel-Cantelli lemmas
Two warm-up special cases
The general Kolmogorov SLLN

1. Almost Sure Convergence and “Infinitely Often”

Let $\{A_n\}_{n \ge 1}$ be a sequence of events. Define their limit superior and limit inferior:

\limsup_{n\to\infty} A_n := \bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty} A_k, \qquad \liminf_{n\to\infty} A_n := \bigcup_{n=1}^{\infty} \bigcap_{k=n}^{\infty} A_k.

Intuitively:

$\limsup A_n$ means $A_n$ occurs infinitely often — no matter how far out you go, there’s always another occurrence.
$\liminf A_n$ means $A_n$ occurs eventually — from some index onward, it always happens.

We write $\{A_n \text{ i.o.}\} := \limsup A_n$ .

Now let $\{X_n\}$ and $X$ live on the same probability space. We say $X_n \to X$ almost surely (a.s.) if

\mathbb{P}\!\left(\left\{\omega : \lim_{n\to\infty} X_n(\omega) = X(\omega)\right\}\right) = 1.

This has an equivalent i.o. characterization. For $\varepsilon > 0$ , define the deviation event

A_n(\varepsilon) := \{|X_n - X| > \varepsilon\}.

Then

X_n \to X \text{ a.s.} \iff \mathbb{P}\bigl(A_n(\varepsilon) \text{ i.o.}\bigr) = 0, \quad \forall \varepsilon > 0.

In words: for any fixed tolerance $\varepsilon$ , the event $|X_n - X| > \varepsilon$ happens only finitely many times, with probability $1$ .

Why this matters for SLLN. The Borel-Cantelli lemma gives us a way to prove $\mathbb{P}(A_n(\varepsilon) \text{ i.o.}) = 0$ by checking that $\sum \mathbb{P}(A_n(\varepsilon)) < \infty$ . That’s the bridge from moment bounds to almost sure convergence.

2. The Borel-Cantelli Lemmas

Lemma 1 (Borel-Cantelli I). If $\sum_{n=1}^{\infty} \mathbb{P}(A_n) < \infty$ , then $\mathbb{P}(A_n \text{ i.o.}) = 0$ .

Proof. Since $\{A_n \text{ i.o.}\} = \bigcap_m \bigcup_{n=m}^\infty A_n$ , for each $m$ ,

\mathbb{P}(A_n \text{ i.o.}) \le \mathbb{P}\!\left(\bigcup_{n=m}^{\infty} A_n\right) \le \sum_{n=m}^{\infty} \mathbb{P}(A_n).

The tail sum of a convergent series tends to $0$ as $m \to \infty$ . $\square$

Lemma 2 (Borel-Cantelli II). If the $A_n$ are independent and $\sum \mathbb{P}(A_n) = \infty$ , then $\mathbb{P}(A_n \text{ i.o.}) = 1$ .

Proof. Show the complement has probability $0$ . For any $m$ ,

\mathbb{P}\!\left(\bigcap_{n=m}^{\infty} A_n^c\right) = \lim_{N\to\infty} \prod_{n=m}^N (1 - \mathbb{P}(A_n)) \le \lim_{N\to\infty} \exp\!\left(-\sum_{n=m}^N \mathbb{P}(A_n)\right) = 0,

since $1-x \le e^{-x}$ and the sum diverges. Then $\{A_n \text{ i.o.}\}^c = \bigcup_m \bigcap_{n=m}^\infty A_n^c$ has probability $0$ . $\square$

Intuition. Lemma 1 is a pure measure-theoretic fact — if the total “mass” of events is finite, they can’t keep happening. Lemma 2 requires independence: if you have infinite independent chances at something, eventually it happens infinitely often.

3. Warm-Up: Two Special Cases

3.1 Finite Fourth Moment

Suppose $X_1, X_2, \ldots$ are i.i.d. with $\mu = \mathbb{E}[X_1]$ and $\mathbb{E}|X_1|^4 < \infty$ . Then $S_n/n \to \mu$ a.s.

Proof. Let $Y_k = X_k - \mu$ and $T_n = \sum_{k=1}^n Y_k$ . Since the $Y_k$ are independent with mean zero, expanding $T_n^4$ yields:

\mathbb{E}[T_n^4] = n\mathbb{E}[Y_1^4] + 3n(n-1)(\mathbb{E}[Y_1^2])^2 \le C n^2.

(The cross terms vanish because odd moments of centered independent variables are zero.) For any $\varepsilon > 0$ , Markov’s inequality gives

\mathbb{P}\!\left(\left|\frac{T_n}{n}\right| > \varepsilon\right) \le \frac{\mathbb{E}[T_n^4]}{\varepsilon^4 n^4} \le \frac{C}{\varepsilon^4 n^2}.

Since $\sum n^{-2} < \infty$ , Borel-Cantelli I kicks in:

\mathbb{P}\!\left(\left|\frac{T_n}{n}\right| > \varepsilon \text{ i.o.}\right) = 0,

which means $T_n/n \to 0$ a.s., i.e. $S_n/n \to \mu$ a.s. $\square$

The trick is that the fourth moment gives us a $1/n^2$ tail, which is summable. This is the simplest version of the pattern: use moment bounds $\to$ Markov/Chebyshev $\to$ summable probabilities $\to$ Borel-Cantelli $\to$ a.s. convergence.

3.2 Indicator Variables

Let $\{A_n\}$ be pairwise independent events with $\sum \mathbb{P}(A_n) = \infty$ . Then

\frac{\sum_{m=1}^n \mathbf{1}_{A_m}}{\sum_{m=1}^n \mathbb{P}(A_m)} \to 1 \quad \text{a.s.}

Proof sketch. Let $S_n = \sum_{m=1}^n \mathbf{1}_{A_m}$ . Pairwise independence gives $\operatorname{Var}(S_n) \le \mathbb{E}[S_n]$ . Chebyshev plus a sub-sequence $n_k = \inf\{n : \mathbb{E}[S_n] \ge k^2\}$ gives a.s. convergence along the sub-sequence. A sandwich argument extends it to the full sequence. $\square$

This is a stepping stone — it introduces the sub-sequence technique we’ll use in the full proof.

4. The Full Kolmogorov SLLN

Theorem (Kolmogorov). Let $\{X_n\}_{n \ge 1}$ be i.i.d. with $\mathbb{E}|X_1| < \infty$ and $\mu = \mathbb{E}[X_1]$ . Then

\frac{S_n}{n} \to \mu \quad \text{a.s.}, \qquad S_n := \sum_{k=1}^n X_k.

The proof proceeds in three stages: truncation, variance control, and sub-sequence sandwiching.

4.1 Truncation

Define the truncated variables

Y_k := X_k \mathbf{1}_{\{|X_k| \le k\}}, \qquad T_n := \sum_{k=1}^n Y_k.

Lemma (Truncation suffices). If $T_n/n \to \mu$ a.s., then $S_n/n \to \mu$ a.s.

Proof. Using the tail integral representation,

\sum_{k=1}^{\infty} \mathbb{P}(|X_k| > k) = \sum_{k=1}^{\infty} \mathbb{P}(|X_1| > k) \le \int_0^{\infty} \mathbb{P}(|X_1| > t)\, dt = \mathbb{E}|X_1| < \infty.

By Borel-Cantelli I, $\mathbb{P}(X_k \neq Y_k \text{ i.o.}) = 0$ . So almost surely, there exists a random constant $R(\omega) < \infty$ such that $|S_n(\omega) - T_n(\omega)| \le R(\omega)$ for all $n$ . Dividing by $n$ gives $|S_n/n - T_n/n| \le R/n \to 0$ . $\square$

Why truncate? The raw $X_k$ can be wild — a single huge value could dominate $S_n$ . By capping $X_k$ at $k$ , we tame the tail while changing only finitely many terms (a.s.). The truncated variables $Y_k$ have finite variance, which is the key to the next step.

4.2 Variance Estimate

Lemma. $\displaystyle \sum_{k=1}^{\infty} \frac{\operatorname{Var}(Y_k)}{k^2} \le 4\,\mathbb{E}|X_1| < \infty$ .

Proof. Since $\operatorname{Var}(Y_k) \le \mathbb{E}[Y_k^2]$ ,

\operatorname{Var}(Y_k) \le \mathbb{E}[Y_k^2] = \int_0^{\infty} 2y\,\mathbb{P}(|Y_k| > y)\,dy \le \int_0^{k} 2y\,\mathbb{P}(|X_1| > y)\,dy.

Summing and swapping sum/integral with Tonelli:

\sum_{k=1}^{\infty} \frac{\operatorname{Var}(Y_k)}{k^2} \le \int_0^{\infty} \left(2y \sum_{k > y} k^{-2}\right) \mathbb{P}(|X_1| > y)\,dy \le 4\int_0^{\infty} \mathbb{P}(|X_1| > y)\,dy = 4\,\mathbb{E}|X_1|,

where the inner sum bound $2y\sum_{k>y} k^{-2} \le 4$ is a calculus exercise (split $y < 1$ and $y \ge 1$ ). $\square$

4.3 Cesàro Mean

A quick auxiliary fact: if $a_n \to a$ , then $\frac{1}{n}\sum_{k=1}^n a_k \to a$ . This is the Cesàro mean — the arithmetic average preserves limits. We’ll use it for $\mathbb{E}[Y_k] \to \mu$ .

4.4 Main Proof

Proof of Kolmogorov SLLN. By the truncation lemma, it suffices to show $T_n/n \to \mu$ a.s.

Step 1 — Sub-sequence convergence. Fix $\alpha > 1$ and set $k(n) = \lfloor \alpha^n \rfloor$ . For any $\varepsilon > 0$ , Chebyshev gives

\mathbb{P}\bigl(|T_{k(n)} - \mathbb{E}[T_{k(n)}]| > \varepsilon\, k(n)\bigr) \le \varepsilon^{-2} \frac{\operatorname{Var}(T_{k(n)})}{k(n)^2} = \varepsilon^{-2} \sum_{m=1}^{k(n)} \frac{\operatorname{Var}(Y_m)}{k(n)^2}.

Swap sums (Tonelli) and use $k(n) \ge \alpha^n/2$ to bound the geometric series. There exists $C_\alpha$ such that

\sum_{n=1}^{\infty} \mathbb{P}\bigl(|T_{k(n)} - \mathbb{E}[T_{k(n)}]| > \varepsilon\, k(n)\bigr) \le C_\alpha \varepsilon^{-2} \sum_{m=1}^{\infty} \frac{\operatorname{Var}(Y_m)}{m^2} < \infty.

Borel-Cantelli I then yields

\frac{T_{k(n)} - \mathbb{E}[T_{k(n)}]}{k(n)} \to 0 \quad \text{a.s.}

Step 2 — Centering term. By dominated convergence, $\mathbb{E}[Y_k] \to \mu$ . By the Cesàro mean,

\frac{\mathbb{E}[T_{k(n)}]}{k(n)} = \frac{1}{k(n)} \sum_{m=1}^{k(n)} \mathbb{E}[Y_m] \to \mu.

So $T_{k(n)}/k(n) \to \mu$ a.s.

Step 3 — Fill the gaps. For $k(n) \le m < k(n+1)$ , the non-negativity of $Y_k$ (we can split into positive and negative parts — assume $X_k \ge 0$ w.l.o.g.) gives monotonicity:

\frac{T_{k(n)}}{k(n+1)} \le \frac{T_m}{m} \le \frac{T_{k(n+1)}}{k(n)}.

Rewrite as

\frac{k(n)}{k(n+1)} \cdot \frac{T_{k(n)}}{k(n)} \le \frac{T_m}{m} \le \frac{T_{k(n+1)}}{k(n+1)} \cdot \frac{k(n+1)}{k(n)}.

Since $k(n+1)/k(n) \to \alpha$ , taking limits gives

\frac{\mu}{\alpha} \le \liminf_{m\to\infty} \frac{T_m}{m} \le \limsup_{m\to\infty} \frac{T_m}{m} \le \alpha\mu.

Now let $\alpha \downarrow 1$ . The liminf and limsup are both squeezed to $\mu$ , so $T_m/m \to \mu$ a.s.

By the truncation lemma, $S_n/n \to \mu$ a.s. $\square$

Summary of the Proof Architecture

The whole proof is a chain of reductions, each elegant on its own:

Truncation $\to$ only finitely many terms changed a.s., so we can work with bounded-variance $Y_k$ .
Variance sum bound $\to$ $\sum \operatorname{Var}(Y_k)/k^2 < \infty$ , the crucial estimate that makes everything summable.
Chebyshev + Borel-Cantelli on a geometric sub-sequence $\to$ a.s. convergence along $k(n) = \lfloor \alpha^n \rfloor$ .
Monotonicity sandwich + $\alpha \downarrow 1$ $\to$ convergence on the full sequence.

Each step is individually natural, but the way they fit together — especially the geometric sub-sequence trick — is what makes this proof a classic.