Mathematics
The Law of the Iterated Logarithm and Its Implications
Quick fact
For a fair coin toss, the maximum deviation from the mean, scaled by sqrt(n), almost surely has limsup equal to sqrt(2 log log n). This means the largest fluctuations grow like sqrt(2 n log log n), a result that holds almost surely and is not captured by the central limit theorem or the strong law of large numbers.
Why this is interesting
You flip a fair coin 1,000,000 times and record the number of heads minus tails. The average drift is tiny, but occasionally the path wanders far. How far can it possibly go? The answer is surprisingly precise.
Read the full explanation
Understanding The Law of the Iterated Logarithm and Its Implications
Imagine a random walk where you take steps of +1 or -1 with equal probability. After n steps, the sum Sn is the net displacement. The strong law of large numbers tells us that Sn/n converges to 0, but it does not say how far Sn might deviate on the way. The central limit theorem says that Sn/sqrt(n) converges in distribution to a normal variable, but this only describes typical fluctuations, not the extreme ones. The law of the iterated logarithm answers the question: how large can |Sn| be, in the worst case, infinitely often? It shows that the limsup of |Sn| / sqrt(n log log n) is almost surely sqrt(2). This means that for any epsilon 0, the event that |Sn| exceeds (sqrt(2) + epsilon) sqrt(n log log n) occurs only finitely often, but it exceeds (sqrt(2) - epsilon) sqrt(n log log n) infinitely often. So the boundary is sharp. The name 'iterated logarithm' comes from the log log n factor. It grows extremely slowly, so the maximum deviation is only slightly larger than the sqrt(n) scale of the CLT. This result is surprising because it gives a deterministic rate of growth that is valid for almost every realization of the random walk.
A deeper explanation
The proof of the law of the iterated logarithm typically uses the Borel-Cantelli lemma and the tail estimates of normal distributions. The key idea is to compare the random walk to a sum of independent normal variables (via the CLT with error bounds) and then use the fact that for a normal variable X, P(X t) is roughly (1/(sqrt(2π) t)) e^{-t^2/2}. Setting t = sqrt(2 log log n) makes e^{-t^2/2} = 1/log n, which is summable when multiplied by a slightly larger factor. This shows that deviations above the threshold occur only finitely often. For the lower bound, one shows that along a subsequence (e.g., nk = k^k), the events are independent enough to have infinitely many occurrences, using the Borel-Cantelli lemma in the other direction. The LIL holds not only for simple random walks but also for sums of independent, identically distributed random variables with finite variance, and for Brownian motion. For Brownian motion, the result states that limsup{t→∞} |B(t)| / sqrt(2 t log log t) = 1 almost surely. The implications are profound. In statistics, it gives a law for the maximum of a random sample that is used in sequential analysis and in the law of the iterated logarithm for empirical processes. In probability theory, it clarifies the distinction between convergence in distribution and almost sure convergence, and it underlines the delicate balance between the CLT and the SLLN. It also illustrates the power of the Borel-Cantelli lemma in determining almost sure behavior.