Law of the iterated logarithm

Plot of ${\displaystyle S_{n}/n}$ (red), its standard deviation ${\displaystyle 1/{\sqrt {n}}}$ (blue) and its bound ${\displaystyle {\sqrt {2\log \log n/n}}}$ 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). ^[1] Another statement was given by A. N. Kolmogorov in 1929. ^[2]

Statement

Let {Y_n} be independent, identically distributed random variables with means zero and unit variances. Let S_n = Y₁ + ... + Y_n. Then

${\displaystyle \limsup _{n\to \infty }{\frac {|S_{n}|}{\sqrt {2n\log \log n}}}=1\quad {\text{a.s.}},}$

where “log” is the natural logarithm, “lim sup” denotes the limit superior, and “a.s.” stands for “almost surely”. ^{[3] [4]}

Discussion

The law of iterated logarithms operates “in between” the law of large numbers and the central limit theorem. There are two versions of the law of large numbers — the weak and the strong — and they both state that the sums S_n, scaled by n⁻¹, converge to zero, respectively in probability and almost surely:

${\displaystyle {\frac {S_{n}}{n}}\ {\xrightarrow {p}}\ 0,\qquad {\frac {S_{n}}{n}}\ {\xrightarrow {a.s.}}0,\qquad {\text{as}}\ \ n\to \infty .}$

On the other hand, the central limit theorem states that the sums S_n scaled by the factor n^−½ converge in distribution to a standard normal distribution. By Kolmogorov's zero–one law, for any fixed M, the probability that the event ${\displaystyle \limsup _{n}{\frac {S_{n}}{\sqrt {n}}}\geq M}$ occurs is 0 or 1. Then

${\displaystyle \Pr \left(\limsup _{n}{\frac {S_{n}}{\sqrt {n}}}\geq M\right)\geqslant \limsup _{n}\Pr \left({\frac {S_{n}}{\sqrt {n}}}\geq M\right)=\Pr \left({\mathcal {N}}(0,1)\geq M\right)>0}$

so

${\displaystyle \limsup _{n}{\frac {S_{n}}{\sqrt {n}}}=\infty \qquad {\text{with probability 1.}}}$

An identical argument shows that

${\displaystyle \liminf _{n}{\frac {S_{n}}{\sqrt {n}}}=-\infty \qquad {\text{with probability 1.}}}$

This implies that these quantities cannot converge almost surely. In fact, they cannot even converge in probability, which follows from the equality

${\displaystyle {\frac {S_{2n}}{\sqrt {2n}}}-{\frac {S_{n}}{\sqrt {n}}}={\frac {1}{\sqrt {2}}}{\frac {S_{2n}-S_{n}}{\sqrt {n}}}-\left(1-{\frac {1}{\sqrt {2}}}\right){\frac {S_{n}}{\sqrt {n}}}}$

and the fact that the random variables

${\displaystyle {\frac {S_{n}}{\sqrt {n}}}\quad {\text{and}}\quad {\frac {S_{2n}-S_{n}}{\sqrt {n}}}}$

are independent and both converge in distribution to ${\displaystyle {\mathcal {N}}(0,1).}$

The law of the iterated logarithm provides the scaling factor where the two limits become different:

${\displaystyle {\frac {S_{n}}{\sqrt {2n\log \log n}}}\ {\xrightarrow {p}}\ 0,\qquad {\frac {S_{n}}{\sqrt {2n\log \log n}}}\ {\stackrel {a.s.}{\nrightarrow }}\ 0,\qquad {\text{as}}\ \ n\to \infty .}$

Thus, although the absolute value of the quantity ${\displaystyle S_{n}/{\sqrt {2n\log \log n}}}$ is less than any predefined ε > 0 with probability approaching one, it will nevertheless almost surely be greater than ε infinitely often; in fact, the quantity will be visiting the neighborhoods of any point in the interval (-1,1) almost surely.

Exhibition of Limit Theorems and their interrelationship

Generalizations and variants

The law of the iterated logarithm (LIL) for a sum of independent and identically distributed (i.i.d.) random variables with zero mean and bounded increment dates back to Khinchin and Kolmogorov in the 1920s.

Since then, there has been a tremendous amount of work on the LIL for various kinds of dependent structures and for stochastic processes. The following is a small sample of notable developments.

Hartman–Wintner (1940) generalized LIL to random walks with increments with zero mean and finite variance. De Acosta (1983) gave a simple proof of the Hartman–Wintner version of the LIL. ^[5]

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

Strassen (1964) studied the LIL from the point of view of invariance principles. ^[7]

Stout (1970) generalized the LIL to stationary ergodic martingales. ^[8]

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

Vovk (1987) derived a version of LIL valid for a single chaotic sequence (Kolmogorov random sequence). ^[10] 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. ^{[11] [12]} 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. ^[13] This subsumes the martingale LIL as it provides matching finite-sample concentration and anti-concentration bounds, and enables sequential testing ^[14] and other applications. ^[15]

See also

• Iterated logarithm
• Brownian motion

Notes

1. A. Khinchine. "Über einen Satz der Wahrscheinlichkeitsrechnung", Fundamenta Mathematicae 6 (1924): pp. 9–20 (The author's name is shown here in an alternate transliteration.)
2. A. Kolmogoroff. "Über das Gesetz des iterierten Logarithmus". Mathematische Annalen, 101: 126–135, 1929. (At the Göttinger DigitalisierungsZentrum web site)
3. Leo Breiman. Probability. Original edition published by Addison-Wesley, 1968; reprinted by Society for Industrial and Applied Mathematics, 1992. (See Sections 3.9, 12.9, and 12.10; Theorem 3.52 specifically.)
4. Varadhan, S. R. S. Stochastic Processes. Courant Lecture Notes in Mathematics, 16. Courant Institute of Mathematical Sciences, New York; American Mathematical Society, Providence, RI, 2007.
5. A. de Acosta: "A New Proof of the Hartman-Wintner Law of the Iterated Logarithm". Ann. Probab., 1983.
6. Chung, Kai-lai (1948). "On the maximum partial sums of sequences of independent random variables". Trans. Am. Math. Soc. 61: 205–233.
7. V. Strassen: "An invariance principle for the law of the iterated logarithm". Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 1964.
8. W. F. Stout: "The Hartman-Wintner Law of the Iterated Logarithm for Martingales". Ann. Math. Statist., 1970.
9. R. Wittmann: "A general law of iterated logarithm". Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 1985.
10. V. Vovk: "The Law of the Iterated Logarithm for Random Kolmogorov, or Chaotic, Sequences". Theory Probab. Appl., 1987.
11. Y. Wang: "The law of the iterated logarithm for p-random sequences". In: Proc. 11th IEEE Conference on Computational Complexity (CCC), pages 180–189. IEEE Computer Society Press, 1996.
12. Y. Wang: Randomness and Complexity. PhD thesis, 1996.
13. A. Balsubramani: "Sharp finite-time iterated-logarithm martingale concentration". arXiv:1405.2639.
14. A. Balsubramani and A. Ramdas: "Sequential nonparametric testing with the law of the iterated logarithm". 32nd Conference on Uncertainty in Artificial Intelligence (UAI).
15. C. Daskalakis and Y. Kawase: "Optimal Stopping Rules for Sequential Hypothesis Testing". In 25th Annual European Symposium on Algorithms (ESA 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.