![Law of large numbers](https://upload.wikimedia.org/wikipedia/commons/e/ee/Law_of_large_numbers.gif)
In
probability theory
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set ...
, the law of the iterated logarithm describes the magnitude of the fluctuations of a
random walk
In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space.
An elementary example of a random walk is the random walk on the integer number line \mathbb Z ...
. 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 be independent, identically distributed
random variables with means zero and unit variances. Let ''S''
''n'' = ''Y''
1 + ... + ''Y''
''n''. Then
:
where “log” is the
natural logarithm, “lim sup” denotes the
limit superior
In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting (that is, eventual and extreme) bounds on the sequence. They can be thought of in a similar fashion for a function (see limit of a function). For a ...
, and “a.s.” stands for “
almost surely
In probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (or Lebesgue measure 1). In other words, the set of possible exceptions may be non-empty, but it has probability 0 ...
”.
Discussion
The law of iterated logarithms operates “in between” the
law of large numbers and the
central limit theorem
In probability theory, the central limit theorem (CLT) establishes that, in many situations, when independent random variables are summed up, their properly normalized sum tends toward a normal distribution even if the original variables themsel ...
. There are two versions of the law of large numbers —
the weak and
the strong
The Strong is an interactive, collections-based educational institution in Rochester, New York, United States, devoted to the study and exploration of play. It carries out this mission through six programmatic arms called "Play Partners":
* Na ...
— and they both state that the sums ''S''
''n'', scaled by ''n''
−1, converge to zero, respectively
in probability and
almost surely
In probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (or Lebesgue measure 1). In other words, the set of possible exceptions may be non-empty, but it has probability 0 ...
:
:
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
In probability theory, Kolmogorov's zero–one law, named in honor of Andrey Nikolaevich Kolmogorov, specifies that a certain type of event, namely a ''tail event of independent σ-algebras'', will either almost surely happen or almost sure ...
, 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 absolute value of the quantity
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.
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
Andrey Nikolaevich Kolmogorov ( rus, Андре́й Никола́евич Колмого́ров, p=ɐnˈdrʲej nʲɪkɐˈlajɪvʲɪtɕ kəlmɐˈɡorəf, a=Ru-Andrey Nikolaevich Kolmogorov.ogg, 25 April 1903 – 20 October 1987) was a Sovi ...
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.
Strassen (1964) studied the LIL from the point of view of invariance principles.
Stout (1970) generalized the LIL to stationary ergodic martingales.
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 Yongge Wang (born 1967) is a computer science professor at the University of North Carolina at Charlotte specialized in algorithmic complexity and cryptography. He is the inventor of IEEE P1363 cryptographic standards SRP5 and WANG-KE and has cont ...
(1996) showed that the law of the iterated logarithm holds for polynomial time pseudorandom sequences also. The Java-based softwar
testing tooltests 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. This subsumes the martingale LIL as it provides matching finite-sample concentration and anti-concentration bounds, and enables sequential testing and other applications.
[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.
See also
*
Iterated logarithm
In computer science, the iterated logarithm of n, written n (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1. The simplest formal definition i ...
*
Brownian motion
Brownian motion, or pedesis (from grc, πήδησις "leaping"), is the random motion of particles suspended in a medium (a liquid or a gas).
This pattern of motion typically consists of random fluctuations in a particle's position insi ...
Notes
{{reflist
Asymptotic theory (statistics)
Theorems in statistics
Stochastic processes