Editing Law of the iterated logarithm (section)

==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.

[[Philip Hartman|Hartman]]–[[Aurel Wintner|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.<ref>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.</ref>

[[Chung Kai-lai|Chung]] (1948) proved another version of the law of the iterated logarithm for the absolute value of a brownian motion.<ref>{{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}}</ref>

[[Volker Strassen|Strassen]] (1964) studied the LIL from the point of view of invariance principles.<ref>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.</ref>

Stout (1970) generalized the LIL to stationary ergodic martingales.<ref>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.</ref>

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

Vovk (1987) derived a version of LIL valid for a single chaotic sequence (Kolmogorov random sequence).<ref>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.</ref> 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.<ref>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.</ref><ref>Y. Wang: [http://webpages.uncc.edu/yonwang/papers/thesis.pdf ''Randomness and Complexity'']. PhD thesis, 1996.</ref> 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 (probability theory)|martingale]] sample paths.<ref>A. Balsubramani: "[https://arxiv.org/abs/1405.2639 Sharp finite-time iterated-logarithm martingale concentration]". arXiv:1405.2639.</ref> This subsumes the martingale LIL as it provides matching finite-sample concentration and anti-concentration bounds, and enables sequential testing<ref>A. 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).</ref> and other applications.<ref>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.</ref>