law of the iterated logarithm

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

: $$

\limsup_{n \to \infty} \frac

where "log" is the natural logarithm, "lim sup" denotes the limit superior, and "a.s." stands for "almost surely".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.)R. Durrett. Probability: Theory and Examples. Fourth edition published by Cambridge University Press in 2010. (See Theorem 8.8.3.)

Another statement given by A. N. Kolmogorov in 1929A. Kolmogoroff. [http://www-gdz.sub.uni-goettingen.de/cgi-bin/digbib.cgi?PPN235181684_0101 "Über das Gesetz des iterierten Logarithmus"]. Mathematische Annalen, 101: 126–135, 1929. (At the [http://gdz.sub.uni-goettingen.de/en/index.html Göttinger DigitalisierungsZentrum web site]) is as follows.

Let $\backslash \{\; Y\_n\; \backslash \}$ be independent random variables with zero means and finite variances. Let $S\_n\; =\; Y\_1\; +\; \backslash dots\; +\; Y\_n$ and $B\_n\; =\; \backslash operatorname\{Var\}(Y\_1)\; +\; \backslash dots\; +\; \backslash operatorname\{Var\}(Y\_n)$. If $B\_n\; \backslash to\; \backslash infty$ and there exists a sequence of positive constants $\backslash \{\; M\_n\; \backslash \}$ such that $|Y\_n|\; \backslash le\; M\_n$ a.s. and

: $$

M_n \;=\; o \left( \sqrt{\frac{B_n}{\log \log B_n}} \right),

then we have

: $$

\limsup_{n \to \infty} \frac

Note that, the first statement covers the case of the standard normal distribution, but the second does not.

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:

: $$

\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^−1/2 converge in distribution to a standard normal distribution. By Kolmogorov's zero–one law, for any fixed M, the probability that the event

$\backslash limsup\_n\; \backslash frac\{S\_n\}\{\backslash sqrt\{n\}\}\; \backslash geq\; M$

occurs is 0 or 1.

Then

: $\backslash Pr\backslash left(\; \backslash limsup\_n\; \backslash frac\{S\_n\}\{\backslash sqrt\{n\}\}\; \backslash geq\; M\; \backslash right)\; \backslash geqslant\; \backslash limsup\_n\; \backslash Pr\backslash left(\; \backslash frac\{S\_n\}\{\backslash sqrt\{n\}\}\; \backslash geq\; M\; \backslash right)\; =\; \backslash Pr\backslash left(\; \backslash mathcal\{N\}(0,\; 1)\; \backslash geq\; M\; \backslash right)\; >\; 0$

so

:$\backslash limsup\_n\; \backslash frac\{S\_n\}\{\backslash sqrt\{n\}\}=\backslash infty\; \backslash qquad\; \backslash text\{with\; probability\; 1.\}$

An identical argument shows that

:$\backslash liminf\_n\; \backslash frac\{S\_n\}\{\backslash sqrt\{n\}\}=-\backslash infty\; \backslash qquad\; \backslash 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

:$\backslash frac\{S\_\{2n\}\}\{\backslash sqrt\{2n\}\}-\backslash frac\{S\_n\}\{\backslash sqrt\{n\}\}\; =\; \backslash frac1\{\backslash sqrt2\}\backslash frac\{S\_\{2n\}-S\_n\}\{\backslash sqrt\{n\}\}\; -\; \backslash left\; (1-\backslash frac1\backslash sqrt2\; \backslash right\; )\backslash frac\{S\_n\}\{\backslash sqrt\{n\}\}$

and the fact that the random variables

:$\backslash frac\{S\_n\}\{\backslash sqrt\{n\}\}\backslash quad\; \backslash text\{and\}\; \backslash quad\; \backslash frac\{S\_\{2n\}-S\_n\}\{\backslash sqrt\{n\}\}$

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

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

: $$

\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 $S\_n/\backslash sqrt\{2n\backslash log\backslash 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.

File:LimitTheoremsExhibition.png

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.A. de Acosta: "[https://projecteuclid.org/journals/annals-of-probability/volume-11/issue-2/A-New-Proof-of-the-Hartman-Wintner-Law-of-the/10.1214/aop/1176993596.full A New Proof of the Hartman-Wintner Law of the Iterated Logarithm]". Ann. Probab., 1983.

Chung (1948) proved another version of the law of the iterated logarithm for the absolute value of a brownian motion.{{cite journal|first1=Kai-lai|last1=Chung|title=On the maximum partial sums of sequences of independent random variables|journal=Trans. Am. Math. Soc.|volume=61|date=1948|pages=205–233}}

Strassen (1964) studied the LIL from the point of view of invariance principles.V. Strassen: "[https://link.springer.com/article/10.1007/BF00534910 An invariance principle for the law of the iterated logarithm]". Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 1964.

Stout (1970) generalized the LIL to stationary ergodic martingales.W. F. Stout: "[https://projecteuclid.org/journals/annals-of-mathematical-statistics/volume-41/issue-6/The-Hartman-Wintner-Law-of-the-Iterated-Logarithm-for-Martingales/10.1214/aoms/1177696721.full The Hartman-Wintner Law of the Iterated Logarithm for Martingales]". Ann. Math. Statist., 1970.

Wittmann (1985) generalized Hartman–Wintner version of LIL to random walks satisfying milder conditions.R. Wittmann: "[https://link.springer.com/article/10.1007/BF00535343 A general law of iterated logarithm]". Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 1985.

Vovk (1987) derived a version of LIL valid for a single chaotic sequence (Kolmogorov random sequence).V. Vovk: "[https://epubs.siam.org/doi/abs/10.1137/1132061 The Law of the Iterated Logarithm for Random Kolmogorov, or Chaotic, Sequences]". Theory Probab. Appl., 1987. 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.Y. Wang: "[http://webpages.uncc.edu/yonwang/papers/CCC96.pdf 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.Y. Wang: [http://webpages.uncc.edu/yonwang/papers/thesis.pdf Randomness and Complexity]. PhD thesis, 1996. The Java-based software [http://webpages.uncc.edu/yonwang/liltest/ 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.A. Balsubramani: "[https://arxiv.org/abs/1405.2639 Sharp finite-time iterated-logarithm martingale concentration]". arXiv:1405.2639. This subsumes the martingale LIL as it provides matching finite-sample concentration and anti-concentration bounds, and enables sequential testingA. Balsubramani and A. Ramdas: "[http://www.auai.org/uai2016/proceedings/supp/270_supp.pdf Sequential nonparametric testing with the law of the iterated logarithm]". 32nd Conference on Uncertainty in Artificial Intelligence (UAI). and other applications.C. Daskalakis and Y. Kawase: "[http://drops.dagstuhl.de/opus/volltexte/2017/7823/pdf/LIPIcs-ESA-2017-32.pdf Optimal Stopping Rules for Sequential Hypothesis Testing]". In 25th Annual European Symposium on Algorithms (ESA 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

• Iterated logarithm
• Brownian motion

{{reflist}}

{{Stochastic processes}}

Category:Asymptotic theory (statistics)

Category:Theorems in statistics

Category:Stochastic processes