The Strong Law of Large Numbers

(Kolmogorov's inequality.) Let $A_k = \{|S_1|<\lambda,\ldots,|S_{k-1}|<\lambda, |S_k|\ge \lambda\}$ for $k=1,\ldots,n$: the event that $k$ is the first time the partial sum exceeds $\lambda$ in absolute value. The $A_k$ are disjoint and their union is $\{\max_{k\le n}|S_k|\ge \lambda\}$. We compute

This holds because the $A_k$ are disjoint subsets of $\Omega$ and $S_n^2\ge 0$, so summing $E[S_n^2\mathbf 1_{A_k}]$ over $k$ only uses part of the total expectation $E[S_n^2]=E[S_n^2 \mathbf 1_{\bigcup A_k}] + E[S_n^2\mathbf 1_{(\bigcup A_k)^c}]$, and the second term is $\ge 0$. Write $S_n = S_k + (S_n - S_k)$ on $A_k$. Then

Now $A_k$ is determined by $Y_1,\ldots,Y_k$ only (it depends on $S_1,\ldots,S_k$), while $S_n - S_k = Y_{k+1}+\cdots+Y_n$ is independent of $Y_1,\ldots,Y_k$, hence independent of $\mathbf 1_{A_k} S_k$. Since $E[S_n - S_k] = 0$,

Therefore $E[S_n^2 \mathbf 1_{A_k}] \ge E[S_k^2 \mathbf 1_{A_k}] \ge \lambda^2 P(A_k)$, the last inequality because on $A_k$ we have $|S_k|\ge \lambda$. Summing over $k$,

Since $E[S_n^2] = \mathrm{Var}(S_n) = \sum_i \sigma_i^2$ (using independence and mean zero), the inequality follows. $\blacksquare$

(Strong Law, finite-variance case, as a stepping stone.) We first prove the theorem under the extra assumption $\mathrm{Var}(X_1) = \sigma^2 < \infty$; this illustrates the main mechanism cleanly, and the full proof below removes this restriction by truncation. Let $Y_i = X_i - \mu$, so $E[Y_i]=0$, $\mathrm{Var}(Y_i)=\sigma^2$, and set $S_n = \sum_{i=1}^n Y_i = \sum_{i=1}^n X_i - n\mu$, so that $\bar X_n - \mu = S_n/n$. We must show $S_n/n \to 0$ a.s. Fix $\varepsilon>0$. For each block of times between $2^{m}$ and $2^{m+1}$, apply Kolmogorov's inequality (proved above) to the variables $Y_1,\ldots,Y_{2^{m+1}}$ with $\lambda = \varepsilon\, 2^m$:

Summing over $m=0,1,2,\ldots$ gives a convergent geometric series, $\sum_m \frac{2\sigma^2}{\varepsilon^2 2^m} < \infty$. By the (easy, first) Borel–Cantelli lemma, almost surely only finitely many of the events

occur. Hence almost surely there is a (random) $M$ such that for all $m\ge M$, $\max_{k\le 2^{m+1}}|S_k| < \varepsilon\, 2^m$. For any $k$ with $2^m \le k < 2^{m+1}$ and $m\ge M$,

So almost surely, $\limsup_{k\to\infty} |S_k|/k \le \varepsilon$. Since $\varepsilon>0$ was arbitrary, intersecting over a countable sequence $\varepsilon = 1/j$, $j=1,2,\ldots$ (a countable intersection of probability-1 events has probability 1) gives $S_k/k \to 0$ almost surely, i.e. $\bar X_n \to \mu$ a.s. $\blacksquare$

(Strong Law, general case $E|X_1|<\infty$, via truncation.) This is the classical Kolmogorov truncation argument; it removes the finite-variance assumption used above. Step 1 (truncate). Define $X_i' = X_i \mathbf 1_{|X_i|\le i}$. We will show $\bar X_n - \bar X_n' \to 0$ a.s. where $\bar X_n' = \frac1n\sum_{i=1}^n X_i'$, and separately that $\bar X_n' \to \mu$ a.s.; together these give $\bar X_n\to\mu$ a.s. Step 2 ($X_i \ne X_i'$ only finitely often, a.s.). Since the $X_i$ are identically distributed with law that of $X_1$,

A standard identity for nonnegative random variables (Fubini/Tonelli on $|X_1| = \int_0^{\infty} \mathbf 1_{|X_1|>t}\,dt$) gives

By Borel–Cantelli, almost surely only finitely many of the events $\{X_i \ne X_i'\}$ occur. Hence, almost surely, there is a random $N_0(\omega)$ such that $X_i(\omega) = X_i'(\omega)$ for all $i \ge N_0(\omega)$; consequently $\frac1n\sum_{i=1}^n (X_i - X_i') \to 0$ a.s. (a finite, fixed number of nonzero terms divided by $n\to\infty$ vanishes), i.e. $\bar X_n - \bar X_n' \to 0$ a.s. Step 3 (center the truncated variables and control their variance sum). Let $\mu_i = E[X_i'] = E[X_1 \mathbf 1_{|X_1|\le i}]$. By dominated convergence (dominating function $|X_1|$, using $E|X_1|<\infty$), $\mu_i \to E[X_1] = \mu$ as $i\to\infty$, so by Cesàro's lemma $\frac1n\sum_{i=1}^n \mu_i \to \mu$. It remains to show $\frac1n \sum_{i=1}^n (X_i' - \mu_i) \to 0$ a.s. The summands are independent (since the $X_i$ are), mean zero, with variance

We must show $\sum_{i=1}^\infty \frac{\mathrm{Var}(X_i')}{i^2} < \infty$; this is the key technical estimate, after which we can apply a martingale/$L^2$-convergence + Kronecker's lemma argument (below) exactly as in the finite-variance proof. Estimate, using Fubini and $E[X_1^2\mathbf 1_{|X_1|\le i}] = \int_0^{i^2} P(X_1^2 \mathbf 1_{|X_1|\le i} > t)\,dt \le \int_0^{i^2} P(X_1^2>t)\,dt$:

Using $\sum_{i=k}^\infty i^{-2} \le \frac{2}{k}$ for $k \ge 1$ (standard tail bound: $\sum_{i\ge k} i^{-2} \le \frac1k + \int_k^\infty t^{-2}dt = \frac2k$), and $X_1^2 \mathbf 1_{k-1<|X_1|\le k} \le k^2 \mathbf 1_{k-1<|X_1|\le k} \le 2k\, |X_1| \mathbf 1_{k-1<|X_1|\le k}$ (valid since $k\le 2|X_1|$ on that event when $k\ge1$; if $k-1 < |X_1|$ then $k < |X_1|+1 \le 2|X_1|$ once $|X_1|\ge 1$, and the finitely many boundary terms with $|X_1|<1$ contribute a bounded amount), we get

for an absolute constant $C$ (one may take $C=6$ after tracking constants; the exact value is immaterial). So

Step 4 (Kronecker's lemma finishes it). Let $Z_i = (X_i' - \mu_i)/i$. The $Z_i$ are independent, mean $0$, with $\sum_i \mathrm{Var}(Z_i) = \sum_i \mathrm{Var}(X_i')/i^2 < \infty$ by Step 3. A standard $L^2$-martingale convergence argument (the partial sums $T_n = \sum_{i=1}^n Z_i$ form a martingale with $\sup_n E[T_n^2] = \sum_i \mathrm{Var}(Z_i) < \infty$, hence by the $L^2$ martingale convergence theorem $T_n$ converges a.s. and in $L^2$ to a finite limit $T_\infty$) shows that $\sum_{i=1}^\infty Z_i$ converges almost surely. Now Kronecker's Lemma states: if $\sum_i z_i$ converges (as a numerical series) then $\frac1n \sum_{i=1}^n i z_i \to 0$. Applying this pointwise, a.s., to $z_i = Z_i(\omega)$, $i z_i = X_i'(\omega) - \mu_i$, gives

Combining with Step 3's Cesàro limit $\frac1n\sum \mu_i \to \mu$, we get $\bar X_n' \to \mu$ a.s. Combined with Step 2 ($\bar X_n - \bar X_n'\to 0$ a.s.), this gives $\bar X_n \to \mu$ a.s., completing the proof of the direct statement. Converse. Suppose $X_1,X_2,\ldots$ are i.i.d. and $\bar X_n \to c$ a.s. for a finite constant $c$. Then $\bar X_n - \frac{n-1}{n}\bar X_{n-1} = X_n/n \to c - c = 0$ a.s. (using $\frac{n-1}{n}\to 1$). So $X_n/n \to 0$ a.s. By the second Borel–Cantelli lemma (using independence and identical distribution), if $E|X_1|=\infty$ then $\sum_n P(|X_n|>n) = \sum_n P(|X_1|>n) = \infty$ (since $E|X_1|=\infty$ forces the tail sum to diverge, by the same integral identity as in Step 2 run in reverse), which would force $|X_n|>n$ infinitely often almost surely, contradicting $X_n/n\to 0$ a.s. Hence $E|X_1|<\infty$, and then the direct statement already proved forces $c=\mu=E[X_1]$. $\blacksquare$