Law of the iterated logarithm

Remarks

This version under a finite second moment is the Hartman–Wintner theorem; Khinchin proved the first case, for coin tossing. One proof first treats the Wiener process $W$, for which $\limsup_{t \to \infty} W_t / \sqrt{2 t \log \log t} = 1$ almost surely. The upper bound uses the Gaussian tail and the Borel–Cantelli lemma along a geometric sequence of times $t_k = q^k$. The lower bound uses the second Borel–Cantelli lemma for the independent increments between these times. The case of general $X_k$ then follows by a strong approximation of the walk by Brownian motion, such as Skorokhod's embedding theorem.

Example: take a simple symmetric random walk, with steps $\pm 1$, and fix $\varepsilon > 0$. Almost surely, the walk exceeds $(1 - \varepsilon)\sqrt{2 n \log \log n}$ for infinitely many $n$. Almost surely, it exceeds $(1 + \varepsilon)\sqrt{2 n \log \log n}$ for only finitely many $n$.

The theorem sits between two other limit theorems. The strong law of large numbers gives $S_n / n \to 0$ almost surely. The central limit theorem gives that $S_n / \sqrt{n}$ converges in distribution, and it implies that $\limsup_n S_n / \sqrt{n} = \infty$ almost surely.

Going deeper

For a student

The result describes the almost sure size of the fluctuations of sums, which neither the strong law nor the central limit theorem determines. The normalisation $\sqrt{2 n \log \log n}$ is the boundary between the scale $\sqrt{n}$ of the central limit theorem and larger scales that the walk exceeds only finitely often. Strassen's functional form describes the whole set of limit points of the rescaled path.