thumb|Plot of <math>S_n/n</math> (red), its standard deviation <math>1/\sqrt{n}</math> (blue) and its bound <math>\sqrt{2\log\log n/n}</math> given by LIL (green). Notice the way it randomly switches from the upper bound to the lower bound. Both axes are non-linearly transformed (as explained in figure summary) to make this effect more visible.

In probability theory, the law of the iterated logarithm describes the magnitude of the fluctuations of a random walk. The original statement of the law of the iterated logarithm is due to A. Ya. Khinchin (1924). Another statement was given by A. N. Kolmogorov in 1929.

Statement

Let {Y<sub>n</sub>} be independent, identically distributed random variables with zero means and unit variances. Let S<sub>n</sub> = Y<sub>1</sub> + ... + Y<sub>n</sub>. Then

: <math>

\limsup_{n \to \infty} \frac{|S_n|}{\sqrt{2n \log\log n = 1 \quad \text{a.s.},

</math>

where "log" is the natural logarithm, "lim sup" denotes the limit superior, and "a.s." stands for "almost surely".

Another statement given by A. N. Kolmogorov in 1929

Chung (1948) proved another version of the law of the iterated logarithm for the absolute value of a brownian motion.

Strassen (1964) studied the LIL from the point of view of invariance principles.

Stout (1970) generalized the LIL to stationary ergodic martingales.

Wittmann (1985) generalized Hartman–Wintner version of LIL to random walks satisfying milder conditions.

A survey up to 1986.

Vovk (1987) derived a version of LIL valid for a single chaotic sequence (Kolmogorov random sequence). This is notable, as it is outside the realm of classical probability theory.

Yongge Wang (1996) showed that the law of the iterated logarithm holds for polynomial time pseudorandom sequences also. The Java-based software testing tool tests whether a pseudorandom generator outputs sequences that satisfy the LIL.

Balsubramani (2014) proved a non-asymptotic LIL that holds over finite-time martingale sample paths. This subsumes the martingale LIL as it provides matching finite-sample concentration and anti-concentration bounds, and enables sequential testing and other applications.

See also

  • Iterated logarithm
  • Brownian motion

Notes