Law of the iterated logarithm

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 {Yn} be independent, identically distributed random variables with means zero and unit variances. Let Sn = Y1 + ... + Yn. Then
 
where “log” is the natural logarithm, “lim sup” denotes the limit superior, and “a.s.” stands for “almost surely”.

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 Sn, scaled by n−1, converge to zero, respectively in probability and almost surely:
 

On the other hand, the central limit theorem states that the sums Sn 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

occurs is 0 or 1.
Then

 

so

An identical argument shows that

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

and the fact that the random variables

are independent and both converge in distribution to 

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

Thus, although the quantity  is less than any predefined ε > 0 with probability approaching one, the quantity will nevertheless be greater than ε infinitely often; in fact, the quantity will be visiting the neighborhoods of any point in the interval (-1,1) almost surely.

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.  Following is a small sample of notable developments.

Hartman–Wintner (1940) generalized LIL to random walks with increments with zero mean and finite variance.

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

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

De Acosta (1983) gave a simple proof of Hartman–Wintner version of LIL.

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

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 has shown 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.

A non-asymptotic version that holds over finite-time martingale sample paths has also been proved and applied.

See also
 Central limit theorem
 Iterated logarithm
 Law of large numbers
 Brownian motion

Notes

Category:Asymptotic theory (statistics)
Category:Statistical theorems
Category:Stochastic processes