Law of the iterated logarithm

Notice the way the average randomly switches from the upper bound given by the law of large numbers to the lower bound. This effect can be seen in this plot since neither axis is a simple linear axis.

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. Y. Khinchin (1924). Another statement was given by A.N. Kolmogorov in 1929.

Statement

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

$\limsup_{n \to \infty} \frac{S_n}{\sqrt{n \log\log n}} = \sqrt{2}, \qquad \text{a.s.},$

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 claim 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^−½ converge in distribution to a standard normal distribution. Combined with Kolmogorov's zero-one law, this implies that these quantities converge neither in probability nor almost surely:

$\frac{S_n}{\sqrt n} \ \stackrel{p}{\nrightarrow}\ \forall, \qquad \frac{S_n}{\sqrt n} \ \stackrel{a.s.}{\nrightarrow}\ \forall, \qquad \text{as}\ \ n\to\infty.$

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

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

Thus, although the quantity $S_n/\sqrt{n\log\log n}$ is less than any predefined ε > 0 with probability approaching one, that quantity will nevertheless be dropping out of that interval infinitely often, and in fact will be visiting the neighborhoods of any point in the interval (0,√2) almost surely.

See also

• Central limit theorem
• Law of large numbers
• Brownian motion