Steven R. Dunbar
Department of Mathematics
203 Avery Hall
Lincoln, NE 68588-0130
http://www.math.unl.edu
Voice: 402-472-3731
Fax: 402-472-8466

Topics in
Probability Theory and Stochastic Processes
Steven R. Dunbar

__________________________________________________________________________

Law of the Iterated Logarithm

_______________________________________________________________________

Note: These pages are prepared with MathJax. MathJax is an open source JavaScript display engine for mathematics that works in all browsers. See http://mathjax.org for details on supported browsers, accessibility, copy-and-paste, and other features.

_______________________________________________________________________________________________

### Rating

Mathematicians Only: prolonged scenes of intense rigor.

_______________________________________________________________________________________________

### Section Starter Question

__________________________________________________________________________

### Key Concepts

1. The Law of the Iterated Logarithm tells very precisely how far the number of successes in a coin-tossing game will make excursions from the average value.
2. The Law of the Iterated Logarithm is a high-point among increasingly precise limit theorems characterizing how far the number of successes in a coin-tossing game will make excursions from the average value. The theorems start with the Strong Law of Large Numbers and the Central Limit Theorem, to Hausdorﬀ’s Estimate, and the Hardy-Littlewood Estimate leading to the Law of the Iterated Logarithm.
3. Khinchin’s Law of the Iterated Logarithm says: Almost surely, for all $𝜖>0$, there exist inﬁnitely many $n$ such that
${S}_{n}-np>\left(1-𝜖\right)\sqrt{n}\sqrt{2p\left(1-p\right)ln\left(ln\left(n\right)\right)}$

and furthermore, almost surely, for all $𝜖>0$, for every $n$ larger than a threshold value $N$

${S}_{n}-np<\left(1+𝜖\right)\sqrt{n}\sqrt{2p\left(1-p\right)ln\left(ln\left(n\right)\right)}.$

__________________________________________________________________________

### Vocabulary

1. The limsup, abbreviation for limit superior is a reﬁned and generalized notion of limit, being the largest dependent-variable subsequence limit. That is, among all subsequences of independent-variable values tending to some independent-variable value, usually inﬁnity, there will be a corresponding dependent-variable subsequence. Some of these dependent-variable sequences will have limits, and among all these, the largest is the limsup.
2. The liminf, abbreviation for limit inferior is analogous, it is the least of all dependent-variable subsequence limits.
3. Khinchin’s Law of the Iterated Logarithm says: Almost surely, for all $𝜖>0$ there exist inﬁnitely many $n$ such that
${S}_{n}-np>\left(1-𝜖\right)\sqrt{n}\sqrt{2p\left(1-p\right)ln\left(ln\left(n\right)\right)}$

and furthermore, almost surely, for all $𝜖>0$, for every $n$ larger than a threshold value $N$

${S}_{n}-np<\left(1+𝜖\right)\sqrt{n}\sqrt{2p\left(1-p\right)ln\left(ln\left(n\right)\right)}.$

__________________________________________________________________________

### Mathematical Ideas

#### Overview

We again consider the number of successes in a coin-tossing game. That is, we consider the sum ${S}_{n}$ where the independent, identically distributed random variables in the sum ${S}_{n}={X}_{1}+\cdots +{X}_{n}$ are the Bernoulli random variables ${X}_{i}=+1$ with probability $p$ and ${X}_{i}=0$ with probability $q=1-p$. Note that the mean $\mu =p$ is and the variance is ${\sigma }^{2}=p\left(1-p\right)$ for each of the summands ${X}_{i}$.

The Strong Law of Large Numbers says that

$\underset{n\to \infty }{lim}\frac{{S}_{n}-np}{n}=0$

with probability $1$ in the sample space of all possible coin ﬂips. This says the denominator $n$ is “too strong”, it “condenses out” all variation in the sum ${S}_{n}$.

The Central Limit Theorem applied to this sequence of coin ﬂips says

$\underset{n\to \infty }{lim}\frac{{S}_{n}-np}{\sqrt{np\left(1-p\right)}}=Z$

where $Z\equiv N\left(0,1\right)$ is a normal random variable and the limit is interpreted as convergence in distribution. In fact, this implies that for large $n$ about 68% of the points in the sample space of all possible coin ﬂips satisfy

$\left|\frac{{S}_{n}-np}{\sqrt{np\left(1-p\right)}}\right|\le 1$

and about 95% of the points in the sample space of all possible coin ﬂips satisfy

$\left|\frac{{S}_{n}-np}{\sqrt{np\left(1-p\right)}}\right|\le 2.$

This says the denominator $\sqrt{n}$ is “too weak”, it doesn’t condense out enough information. In fact, using the Kolmogorov zero-one law and the Central Limit Theorem, almost surely

$\underset{n\to \infty }{liminf}\frac{{S}_{n}-np}{\sqrt{np\left(1-p\right)}}=-\infty$

and almost surely

$\underset{n\to \infty }{limsup}\frac{{S}_{n}-np}{\sqrt{np\left(1-p\right)}}=+\infty .$

The Strong Law and the Central Limit Theorem together suggest that “somewhere in between $n$ and $\sqrt{n}$” we might be able to make stronger statements about convergence and the variation in the sequence ${S}_{n}$.

In fact, Hausdorﬀ’s estimate tells us:

$\underset{n\to \infty }{lim}\left|\frac{{S}_{n}-np}{{n}^{1∕2+𝜖}}\right|=0$

with probability $1$ in the sample space of all possible coin ﬂips for all values of $𝜖>0$. This says the denominator ${n}^{1∕2+𝜖}$ is “still too strong”, it condenses out too much information.

Even better, Hardy and Littlewood’s estimate tells us:

$\underset{n\to \infty }{lim}\left|\frac{{S}_{n}-np}{\sqrt{nlnn}}\right|\le \text{constant}$

with probability $1$ in the sample space of all possible coin ﬂips for all values of $𝜖>0$. In a way, this says $\sqrt{nlnn\right)}$ is “still a little too strong”, it condenses out most information.

Khinchin’s Law of the Iterated Logarithm has a denominator that is “just right.” It tells us very precisely how the deviations of the sums from the mean vary with $n$. Using a method due to Erdös, it is possible to reﬁne the law even more, but for these notes a reﬁnement is probably past the point of diminishing returns.

Like the Central Limit Theorem, the Law of the Iterated Logarithm illustrates in an astonishingly precise way that even completely random sequences obey precise mathematical laws.

Khinchin’s Law of the Iterated Logarithm says that:

Almost surely, for all $𝜖>0$, there exist inﬁnitely many $n$ such that

${S}_{n}-np>\left(1-𝜖\right)\sqrt{np\left(1-p\right)}\sqrt{2ln\left(ln\left(n\right)\right)}$

and furthermore, almost surely, for all $𝜖>0$, for every $n$ larger than a threshold value $N$ depending on $𝜖$

${S}_{n}-np<\left(1+𝜖\right)\sqrt{np\left(1-p\right)}\sqrt{2ln\left(ln\left(n\right)\right)}.$

These appear in a slightly non-standard way, with the additional factor $\sqrt{2lnlnn}$ times the standard deviation from the Central Limit Theorem to emphasize the similarity to and the diﬀerence from the Central Limit Theorem.

Theorem 1 (Law of the Iterated Logarithm). With probability $1$:

$\underset{n\to \infty }{limsup}\frac{{S}_{n}-np}{\sqrt{2np\left(1-p\right)ln\left(ln\left(n\right)\right)}}=1.$

This means that with probability $1$ for any $𝜖>0$, only ﬁnitely many of the events:

${S}_{n}-np>\left(1+𝜖\right)\sqrt{n}\sqrt{2p\left(1-p\right)ln\left(ln\left(n\right)\right)}$

occur; on the other hand, with probability $1$,

${S}_{n}-np>\left(1-𝜖\right)\sqrt{n}\sqrt{2p\left(1-p\right)ln\left(ln\left(n\right)\right)}$

occurs for inﬁnitely many $n$.

For reasons of symmetry, for $𝜖>0$, the inequality

${S}_{n}-np<-\left(1+𝜖\right)\sqrt{n}\sqrt{2p\left(1-p\right)ln\left(ln\left(n\right)\right)}$

can only occur for ﬁnitely many $n$; while

${S}_{n}-np<-\left(1-𝜖\right)\sqrt{n}\sqrt{2p\left(1-p\right)ln\left(ln\left(n\right)\right)}$

must occur for inﬁnitely many $n$. That is,

$\underset{n\to \infty }{liminf}\frac{{S}_{n}-np}{\sqrt{2np\left(1-p\right)ln\left(ln\left(n\right)\right)}}=-1$

with probability $1$.

Compare the Law of the Iterated Logarithm to the Central Limit Theorem. The Central Limit Theorem, says that $\left({S}_{n}-np\right)∕\sqrt{np\left(1-p\right)}$ is approximately distributed as a $N\left(0,1\right)$ random variable for large $n$. Therefore, for a large but ﬁxed $n$, there is probability about $1∕6$ that the values of $\left({S}_{n}-np\right)∕\sqrt{np\left(1-p\right)}$ can exceed the standard deviation $1$, or ${S}_{n}-np>\sqrt{np\left(1-p\right)}$. For a ﬁxed but large $n$, with probability about $0.025$, $\left({S}_{n}-np\right)∕\sqrt{np\left(1-p\right)}$ can exceed twice the standard deviation $2$, or $\left({S}_{n}-np\right)>2\sqrt{np\left(1-p\right)}$. The Law of the Iterated Logarithm tells us the more precise information that there are inﬁnitely many $n$ such that

${S}_{n}-np>\left(1-𝜖\right)\sqrt{2np\left(1-p\right)ln\left(ln\left(n\right)\right)}$

for any $𝜖>0$. The Law of the Iterated Logarithm does not tell us how long we will have to wait between such repeated crossings however, and the wait can be very, very long indeed, although it must (with probability $1$) eventually occur again. Moreover, the Law of the Iterated Logarithm tells us in addition that

${S}_{n}-np<-\left(1-𝜖\right)\sqrt{2np\left(1-p\right)ln\left(ln\left(n\right)\right)}$

must occur for inﬁnitely many $n$.

Khinchin’s Law of the Iterated Logarithm also applies to the cumulative fortune in a coin-tossing game, or equivalently, the position in a random walk. Consider the independent Bernoulli random variables ${Y}_{i}=+1$ with probability $p$ and ${Y}_{i}=-1$ with probability $q=1-p$. The mean is $\mu =2p-1$ and the variance is ${\sigma }^{2}=4p\left(1-p\right)$ for each of the summands ${Y}_{i}$. Then consider the sum ${T}_{n}={Y}_{1}+\cdots +{Y}_{n}$ with mean $\left(2p-1\right)n$ and variance $4np\left(1-p\right)$. Since ${Y}_{n}=2{X}_{n}-1$, then ${T}_{n}=2{S}_{n}-n$ and ${S}_{n}=\frac{1}{2}{T}_{n}+\frac{n}{2}$. Then applying the Law of the Iterated Logarithm says that with probability $1$ for any $𝜖>0$, only ﬁnitely many of the events:

$|{T}_{n}-n\left(2p-1\right)|>\left(1+𝜖\right)2\sqrt{n}\sqrt{2p\left(1-p\right)ln\left(ln\left(n\right)\right)}$

occur; on the other hand, with probability $1$,

$|{T}_{n}-n\left(2p-1\right)|>\left(1-𝜖\right)2\sqrt{n}\sqrt{2p\left(1-p\right)ln\left(ln\left(n\right)\right)}$

occurs for inﬁnitely many $n$. This means that the fortune must (with probability $1$) oscillate back and forth across the net zero axis inﬁnitely often, crossing the upper and lower boundaries:

$±\left(1-𝜖\right)2\sqrt{2p\left(1-p\right)nln\left(ln\left(n\right)\right)}$

The statement puts some strength behind an understanding of the long-term swings backs and forth in value of a random process. It also implies a form of recurrence, that is, a random walk must visit every integer value.

The Law of the Iterated Logarithm for Bernoulli trials stated here is a special case of an even more general theorem ﬁrst formulated by Kolmogorov in 1929. It is also possible to formulate even stronger and more general theorems! The proof here uses the Large Deviations and Moderate Deviations results with the Borel-Cantelli Lemmas. In another direction, the Law of the Iterated Logarithm can be proved using invariance theorems, so it is distantly related to the Central Limit Theorem.

Figure 1 gives an impression of the growth of the function in the Law of the Iterated Logarithm compared to the square root function. Figure 2 gives an impression of the Law of the Iterated Logarithm by showing a piecewise linearly connected graph of $2000$ steps of ${S}_{n}-np$ with $p=q=1∕2$. In this ﬁgure, the random walk must return again to cross the blue curves with $\left(1-𝜖\right)=0.9$ inﬁnitely many times, but may only cross the red curve with $1+𝜖=1.1$ ﬁnitely many times. Of course, this is only a schematic impression since a single random walk (possibly atypical, from the negligible set!) on the ﬁnite interval $0\le n\le 2000$ can only suggest the almost sure inﬁnitely many crossings of $\left(1-𝜖\right)\alpha \left(x\right)$ for any $𝜖>0$.

Figure 3 gives a comparison of impressions of four of the limit theorems. The individual ﬁgures deliberately are “spaghetti graphs” to give an impression of the ensemble of sample paths. Each ﬁgure shows a diﬀerent scaling of the same $15$ sample paths for a sequence of $100,000$ fair coin ﬂips, each path a diﬀerent color. Note that the steps axis has a logarithmic scale, meaning that the shape of the paths is distorted although it still gives an impression of the random sums. The top left ﬁgure shows ${S}_{n}∕n-p$ converging to $0$ for all paths in accord with the Strong Law of Large Numbers. The top right ﬁgure plots the scaling $\left({S}_{n}-np\right)∕\sqrt{2p\left(1-p\right)n}$. For large values of steps the values over all paths is a distribution ranging from about $-2$ to $2$, consistent with the Central Limit Theorem. The lower left ﬁgure plots $\left({S}_{n}-np\right)∕{n}^{0.6}$ as an illustration of Hausdorﬀ’s Estimate with $𝜖=0.1$. It appears that the scaled paths are very slowly converging to $0$, the range for $n=100,000$ is within $\left[-0.5,0.5\right]$. The lower right ﬁgure shows $\left({S}_{n}-np\right)∕\sqrt{2p\left(1-p\right)nln\left(ln\left(x\right)\right)}$ along with lines $±1$ to suggest the conclusions of the Law of the Iterated Logarithm. It suggests that all paths are usually in the range $\left[-1,1\right]$ but with each path making a few excursions outside the range.

#### Hausdorﬀ’s Estimate

Theorem 2 (Hausdorﬀ’s Estimate). Almost surely, for any $𝜖>0$,

${S}_{n}-np=o\left({n}^{𝜖+1∕2}\right)$

as $n\to \infty$.

Proof.

The proof resembles the proof of the Strong Law of Large Numbers for independent random variables with mean $0$ and uniformly bounded $4$th moments. That proof showed that using the independence and identical distribution assumptions

$𝔼\left[{S}_{n}^{4}\right]=n𝔼\left[{X}_{1}^{4}\right]+3n\left(n-1\right)𝔼{\left[{X}_{1}^{2}\right]}^{2}\le nC+3{n}^{2}{\sigma }^{4}\le {C}_{1}{n}^{2}.$

Then adapting the proof of the Markov and Chebyshev inequalities with fourth moments

$\frac{𝔼\left[|{S}_{n}{|}^{4}\right]}{{n}^{4}}\le \frac{{C}_{1}{n}^{2}}{{n}^{4}}.$

Use the Corollary that if $\sum _{n=1}^{\infty }𝔼\left[|{X}_{n}|\right]$ converges, then the sequence ${\left({X}_{n}\right)}_{n\ge 1}$ converges almost surely to $0$. By comparison, $\sum _{n=1}^{\infty }\frac{𝔼\left[|{S}_{n}{|}^{4}\right]}{{n}^{4}}$ converges so that ${S}_{n}∕n\to 0$ a.s. Using the same set of ideas

$\frac{𝔼\left[|{S}_{n}{|}^{4}\right]}{{n}^{\alpha }}\le \frac{{C}_{1}{n}^{2}}{{n}^{4\alpha }}$

provided that $\alpha >3∕4$. Then using the same lemma ${S}_{n}∕{n}^{\alpha }\to 0$ for $\alpha >3∕4$ for a simple version of Hausdorﬀ’s Estimate.

Now adapt this proof to higher moments. Let $k$ be a ﬁxed positive integer. Recall the deﬁnition ${R}_{n}\left(\omega \right)={S}_{n}\left(\omega \right)-np=\sum _{k=1}^{n}\left({X}_{k}-p\right)=\sum _{k=1}^{n}\left({X}_{k}^{\prime }$ where ${X}_{k}^{\prime }={X}_{k}-p$ and consider $𝔼\left[{R}_{n}^{2k}\right]$. Expanding the product ${R}_{n}^{2k}$ results in a sum of products of the individual random variables ${X}_{i}^{\prime }$ of the form ${X}_{{i}_{1}}^{\prime }{X}_{{i}_{2}}^{\prime }\cdots {X}_{{i}_{2k}}^{\prime }$. Each product ${X}_{{i}_{1}}^{\prime }{X}_{{i}_{2}}^{\prime }\cdots {X}_{{i}_{2k}}^{\prime }$ results from a selection or mapping from indices $\left\{1,2,\dots ,2k\right\}$ to the set $\left\{1,\dots ,n\right\}$. Note that if an index $j\in \left\{1,2,\dots ,n\right\}$ is selected only once so that ${X}_{j}^{\prime }$ appears only once in the product ${X}_{{i}_{1}}^{\prime }{X}_{{i}_{2}}^{\prime }\cdots {X}_{{i}_{k}}^{\prime }$, then $𝔼\left[{X}_{{i}_{1}}^{\prime }{X}_{{i}_{2}}^{\prime }\cdots {X}_{{i}_{k}}^{\prime }\right]=0$ by independence. Further notice that for all sets of indices

$𝔼\left[{X}_{{i}_{1}}^{\prime }{X}_{{i}_{2}}^{\prime }\cdots {X}_{{i}_{k}}^{\prime }\right]\le 1.$

Thus

$𝔼\left[{R}_{n}^{2k}\right]=\sum _{1\le {i}_{1},\dots ,{i}_{2k}\le n}𝔼\left[{X}_{{i}_{1}}^{\prime }{X}_{{i}_{2}}^{\prime }\cdots {X}_{{i}_{2k}}^{\prime }\right]\le N\left(k,n\right),$

where $N\left(k,n\right)$ is the number of functions from $\left\{1,\dots ,2k\right\}$ to $\left\{1,\dots ,n\right\}$ that take each value at least twice. Let $M\left(k\right)$ be the number of partitions of $\left\{1,\dots ,2k\right\}$ into subsets each containing at least two elements. If $P$ is such a partition, then $P$ has at most $k$ elements. The number of functions $N\left(k,n\right)$ that are constant on each element of $P$ is at most ${n}^{k}$. Thus, $N\left(k,n\right)\le {n}^{k}M\left(k\right)$.

Now let $𝜖>0$ and consider

$𝔼\left[{\left({n}^{-𝜖-1∕2}{R}_{n}\right)}^{2k}\right]\le {n}^{-2k𝜖-k}N\left(k,n\right)\le {n}^{-2k𝜖}M\left(k\right).$

Choose $k>\frac{1}{2𝜖}$. Then

$\sum _{n\ge 1}𝔼\left[{\left({n}^{-𝜖-1∕2}{R}_{n}\right)}^{2k}\right]<\infty .$

Recall the Corollary 2 appearing in the section on the Borel-Cantelli Lemma:

Let ${\left({X}_{n}\right)}_{n\ge 0}$ be a sequence of random variables. If ${\sum }_{n=1}^{\infty }𝔼\left[|{X}_{n}|\right]$ converges, then ${X}_{n}$ converges to zero, almost surely.

By this corollary, the sequence of random variables

$\left({n}^{-𝜖-1∕2}{R}_{n}\right)\to 0$

almost surely as $n\to \infty$.

This means that for each $𝜖>0$, there is a negligible event (depending on $𝜖$) outside of which ${n}^{-𝜖-1∕2}{R}_{n}$ converges to $0$. Now consider a countable set of values of $𝜖$ tending to $0$. Since a countable union of negligible events is negligible, then for each $𝜖>0$, ${n}^{-𝜖-1∕2}{R}_{n}$ converges to $0$ almost surely. □

#### Hardy-Littlewood Estimate

Theorem 3 (Hardy-Littlewood Estimate).

Remark. The proof shows that ${S}_{n}-np\le \sqrt{nlnn}$ a.s. for $n\to \infty$.

Proof. The proof uses the Large Deviations Estimate as well as the Borel-Cantelli Lemma. Recall the Large Deviations Estimate says

$ℙ\left[\frac{{S}_{n}}{n}\ge p+𝜖\right]\le {\mathrm{e}}^{-n{h}_{+}\left(𝜖\right)},$

where

${h}_{+}\left(𝜖\right)=\left(p+𝜖\right)ln\left(\frac{p+𝜖}{p}\right)+\left(1-p-𝜖\right)ln\left(\frac{1-p-𝜖}{1-p}\right).$

Note that as $𝜖\to 0$, ${h}_{+}\left(𝜖\right)=\frac{{𝜖}^{2}}{2p\left(1-p\right)}+O\left({𝜖}^{3}\right)$.

Note that

$ℙ\left[\frac{{S}_{n}}{n}\ge p+𝜖\right]=ℙ\left[{S}_{n}-np\ge n𝜖\right],$

and take $𝜖=\sqrt{\frac{lnn}{n}}$ and note that

$ℙ\left[{S}_{n}-np\ge \sqrt{nlnn}\right]\le {e}^{-n{h}_{+}\left(\sqrt{\frac{lnn}{n}}\right)}.$

Then

${h}_{+}\left(\sqrt{\frac{lnn}{n}}\right)=\frac{lnn}{2p\left(1-p\right)n}+o\left(\frac{1}{n}\right),$

since $O\left({\left(\frac{lnn}{n}\right)}^{3∕2}\right)=o\left(\frac{1}{n}\right)$. Thus, the probability is less than or equal to the following:

$\begin{array}{llll}\hfill exp\left(-n{h}_{+}\left(\sqrt{\frac{lnn}{n}}\right)\right)& =exp\left(-\frac{1}{2p\left(1-p\right)}lnn+o\left(1\right)\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =exp\left(\frac{-lnn}{2p\left(1-p\right)}\right)exp\left(o\left(1\right)\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & ={n}^{\frac{-1}{2p\left(1-p\right)}}\cdot exp\left(o\left(1\right)\right).\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

Hence $exp\left(-n{h}_{+}\left(\sqrt{\frac{lnn}{n}}\right)\right)\sim {n}^{\frac{-1}{2p\left(1-p\right)}}$, and ${\sum }_{n\ge 1}{n}^{\frac{-1}{2p\left(1-p\right)}}$ is convergent because of the following inequalities

$\begin{array}{llll}\hfill p\left(1-p\right)& \le \frac{1}{4}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill 2p\left(1-p\right)& \le \frac{1}{2}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill \frac{1}{2p\left(1-p\right)}& \ge 2\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill \frac{-1}{2p\left(1-p\right)}& \le -2\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill {n}^{\frac{-1}{2p\left(1-p\right)}}& \le {n}^{-2}.\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

Thus,

$\sum _{n\ge 1}ℙ\left[{S}_{n}-np>\sqrt{nlnn}\right]<\infty ,$

and so

##### Proof of Khinchin’s Law of Iterated Logarithm

Theorem 4 (Khinchin’s Law of Iterated Logarithm). Almost surely,

$\underset{n\to \infty }{limsup}\frac{{S}_{n}-np}{\sqrt{2p\left(1-p\right)nln\left(lnn\right)}}=1,$

and

$\underset{n\to \infty }{liminf}\frac{{S}_{n}-np}{\sqrt{2p\left(1-p\right)nln\left(lnn\right)}}=-1.$

First establish a two lemmas, and for convenience, let

$\alpha \left(n\right)=\sqrt{2p\left(1-p\right)nln\left(lnn\right)}.$

Lemma 5. For all positive $a$ and $\delta$ and large enough $n$,

${\left(lnn\right)}^{-{a}^{2}\left(1+\delta \right)}<ℙ\left[{S}_{n}-np>a\alpha \left(n\right)\right]<{\left(lnn\right)}^{-{a}^{2}\left(1-\delta \right)}.$

Proof of Lemma 5. Recall that the Large Deviations Estimate gives

$\begin{array}{llll}\hfill ℙ\left[{R}_{n}\ge a\alpha \left(n\right)\right]& =ℙ\left[{S}_{n}-np\ge a\alpha \left(n\right)\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =ℙ\left[\frac{{S}_{n}}{n}-p\ge \frac{a\alpha \left(n\right)}{n}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \le exp\left(-n{h}_{+}\left(\frac{a\alpha \left(n\right)a}{n}\right)\right).\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

Note that $\frac{\alpha \left(n\right)}{n}\to 0$ as $n\to \infty$. Then

${h}_{+}\left(\frac{a\alpha \left(n\right)}{n}\right)=\frac{{a}^{2}}{2p\left(1-p\right)}{\left(\frac{\alpha \left(n\right)}{n}\right)}^{2}+O\left({\left(\frac{\alpha \left(n\right)}{n}\right)}^{3}\right),$

and so

$n{h}_{+}\left(\frac{a\alpha \left(n\right)}{n}\right)={a}^{2}ln\left(lnn\right)+O\left(\frac{\alpha {\left(n\right)}^{3}}{{n}^{2}}\right)\ge {a}^{2}\left(1-\delta \right)ln\left(lnn\right)$

for large enough $n$. This means that

$ℙ\left[\frac{{S}_{n}}{n}-p\ge a\alpha \left(n\right)\right]\le exp\left(-{a}^{2}\left(1-\delta \right)ln\left(lnn\right)\right)={\left(lnn\right)}^{-{a}^{2}\left(1-\delta \right)}.$

Since $\sqrt{ln\left(lnn\right)}=o\left({n}^{1∕6}\right)$, the results of the Moderate Deviations Theorem apply to give

$\begin{array}{llll}\hfill ℙ\left[\frac{{S}_{n}}{n}-p\ge \frac{a\alpha \left(n\right)}{n}\right]& =ℙ\left[\frac{{S}_{n}}{n}-p\ge \sqrt{\frac{p\left(1-p\right)}{n}}a\sqrt{2ln\left(lnn\right)}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \sim \frac{1}{\sqrt{2\pi }a\sqrt{2ln\left(lnn\right)}}exp\left(-{a}^{2}ln\left(lnn\right)\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{1}{2a\sqrt{\pi ln\left(lnn\right)}}{\left(lnn\right)}^{-{a}^{2}}.\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

Since $\sqrt{ln\left(lnn\right)}=o\left({\left(lnn\right)}^{{a}^{2}\delta }\right)$,

$ℙ\left[\frac{{S}_{n}}{n}-p\ge \frac{a\alpha \left(n\right)}{n}\right]\ge {\left(lnn\right)}^{-{a}^{2}\left(1+\delta \right)}$

for large enough $n$. □

Lemma 6 (12.5, Kolmogorov Maximal Inequality). Suppose ${\left({Y}_{n}\right)}_{n\ge 1}$ are independent random variables. Suppose further that $𝔼\left[{Y}_{n}\right]=0$ and $\text{Var}\left({Y}_{n}\right)={\sigma }^{2}$. Deﬁne ${T}_{n}:={Y}_{1}+\cdots +{Y}_{n}$. Then

$ℙ\left[\underset{1\le k\le n}{max}{T}_{k}\ge b\right]\le \frac{4}{3}ℙ\left[{T}_{n}\ge b-2\sigma \sqrt{n}\right].$

Remark. Lemma 6 is an example of a class of lemmas called maximal inequalities. Here are two more examples of maximal inequalities.

Lemma 7 (Karlin and Taylor, page 280). Let ${\left({Y}_{n}\right)}_{n\ge 1}$ be identical independently distributed random variables with $𝔼\left[{Y}_{n}\right]=0$ and $\text{Var}\left({Y}_{n}\right)={\sigma }^{2}<\infty$. Deﬁne ${T}_{n}={\sum }_{k=1}^{n}{Y}_{k}$. Then

${𝜖}^{2}ℙ\left[\underset{0\le k\le n}{max}\left|{T}_{k}\right|>𝜖\right]\le n{\sigma }^{2}.$

Lemma 8 (Karlin and Taylor, page 280). Let ${\left({X}_{n}\right)}_{n\ge 0}$ be a submartingale for which ${X}_{n}\ge 0$. For $\lambda >0$,

$\lambda ℙ\left[\underset{0\le k\le n}{max}{X}_{k}>\lambda \right]\le 𝔼\left[{X}_{n}\right].$

Proof of Lemma 6.

Since the ${Y}_{k}$’s are independent, then $\text{Var}\left({T}_{n}-{T}_{k}\right)=\left(n-k\right){\sigma }^{2}$ for $1\le k\le n$. Chebyshev’s Inequality tells us that

$ℙ\left[\left|{T}_{n}-{T}_{k}\right|\le 2\sigma \sqrt{n}\right]\ge 1-\frac{\text{Var}\left({T}_{n}-{T}_{k}\right)}{4{\sigma }^{2}n}=1-\frac{n-k}{4n}\ge \frac{3}{4}.$

Note that

Remark. Note that the second part of the Law of the Iterated Logarithm, ${liminf}_{n\to \infty }\frac{{S}_{n}-np}{\alpha \left(n\right)}=-1$ follows by symmetry from the ﬁrst part by replacing $p$ with $\left(1-p\right)$ and ${S}_{n}$ with $n-{S}_{n}$.

Remark. The proof of the Law of the Iterated Logarithm proceeds in two parts. First it suﬃces to show that

 (1)

The second part of the proof is to establish that

 (2)

It will only take a subsequence to prove (2). However this will not be easy because it will use the second Borel-Cantelli Lemma, which requires independence.

Remark. The following is a simpliﬁed proof giving a partial result for integer sequences with exponential growth. This simpliﬁed proof illustrates the basic ideas of the proof. Fix $\gamma >1$ and let ${n}_{k}:=⌊{\gamma }^{k}⌋$. Then

$\begin{array}{llll}\hfill ℙ\left[{S}_{{n}_{k}}-p{n}_{k}\ge \left(1+\eta \right)\alpha \left({n}_{k}\right)\right]& <{\left(ln{n}_{k}\right)}^{-{\left(1+\eta \right)}^{2}\left(1-\delta \right)}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =O\left({k}^{-{\left(1+\eta \right)}^{2}\left(1-\delta \right)}\right).\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

Choose $\delta$ so that ${\left(1+\eta \right)}^{2}\left(1-\delta \right)<1$. Then

$\sum _{k\ge 1}ℙ\left[{S}_{{n}_{k}}-{n}_{k}p\ge \left(1+\eta \right)\alpha \left({n}_{k}\right)\right]<\infty .$

By the ﬁrst Borel-Cantelli lemma,

and so

$ℙ\left[\underset{k\to \infty }{limsup}\frac{{S}_{{n}_{k}}-{n}_{k}p}{\alpha \left({n}_{k}\right)}\le \left(1+\eta \right)\right]=1,$

or

The full proof of the Law of the Iterated Logarithm takes more work to complete.

Proof of (1) in the Law of the Iterated Logarithm.

Fix $\eta >0$ and let $\gamma >1$ be a constant chosen later. For $k\in ℤ$, let ${n}_{k}=⌊{\gamma }^{k}⌋$. The proof consists of showing that

$\sum _{k\ge 1}ℙ\left[\underset{n\le {n}_{k+1}}{max}\left({S}_{n}-np\right)\ge \left(1+\eta \right)\alpha \left({n}_{k}\right)\right]<\infty .$

From Lemma 6

$\begin{array}{c}\sum _{k\ge 1}ℙ\left[\underset{n\le {n}_{k+1}}{max}\left({S}_{n}-np\right)\ge \left(1+\eta \right)\alpha \left({n}_{k}\right)\right]\\ \le \frac{4}{3}ℙ\left[{R}_{{n}_{k+1}}\ge \left(1+\eta \right)\alpha \left({n}_{k}\right)-2\sqrt{{n}_{k+1}p\left(1-p\right)}\right],\end{array}$

where ${R}_{n}={S}_{n}-np$. We do know that

$\begin{array}{cc}& ℙ\left[\underset{n\le {n}_{k+1}}{max}\left({S}_{n}-np\right)\ge \left(1+\eta \right)\alpha \left({n}_{k}\right)\right]\le \\ & \frac{4}{3}ℙ\left[{R}_{{n}_{k+1}}\ge \left(1+\eta \right)\alpha \left({n}_{k}\right)-2\sqrt{{n}_{k+1}p\left(1-p\right)}\right].& \text{(3)}\end{array}$

Note that $\sqrt{{n}_{k+1}}=o\left(\alpha \left({n}_{k}\right)\right)$ because this is approximately

which is the same as

Then $2\sqrt{{n}_{k+1}p\left(1-p\right)}<\frac{1}{2}\eta \alpha \left({n}_{k}\right)$ for large enough $k$. Using this inequality in the right hand side of Equation (3), we get

$ℙ\left[\underset{n\le {n}_{k+1}}{max}{S}_{n}-np\ge \left(1+\eta \right)\alpha \left({n}_{k}\right)\right]\le \frac{4}{3}ℙ\left[{S}_{{n}_{k+1}}-{n}_{k+1}p\ge \left(1+\eta ∕2\right)\alpha \left({n}_{k}\right)\right].$

Now, $\alpha \left({n}_{k+1}\right)\sim \sqrt{\gamma }\alpha \left({n}_{k}\right)$. Choose $\gamma$ so that $1+\eta ∕2>\left(1+\eta ∕4\right)\sqrt{\gamma }$. Then for large enough $k$, we have

$\left(1+\eta ∕2\right)\alpha \left({n}_{k}\right)>\left(1+\eta ∕4\right)\alpha \left({n}_{k+1}\right).$

Now

$ℙ\left[\underset{n\le {n}_{k+1}}{max}{S}_{n}-np\ge \left(1+\eta \right)\alpha \left({n}_{k}\right)\right]\le \frac{4}{3}ℙ\left[{S}_{{n}_{k+1}}-{n}_{k+1}p\ge \left(1+\eta ∕4\right)\alpha \left({n}_{k+1}\right)\right].$

Use Lemma 5 with $a={\left(1-\delta \right)}^{-1}=\left(1+\eta ∕4\right)$. Then we get

$ℙ\left[\underset{n\le {n}_{k+1}}{max}{S}_{n}-np\ge \left(1+\eta \right)\alpha \left({n}_{k}\right)\right]\le \frac{4}{3}{\left(ln{n}_{k+1}\right)}^{-\left(1+\eta ∕4\right)}$

for $k$ large. Note that

${\left(ln{n}_{k+1}\right)}^{-\left(1+\eta ∕4\right)}\sim {\left(ln\gamma \right)}^{-\left(1+\eta ∕4\right)}{k}^{-\left(1+\eta ∕4\right)},$

which is the general term of a convergent series so

$\sum _{k\ge 1}ℙ\left[\underset{n\le {n}_{k+1}}{max}{R}_{n}\ge \left(1+\eta \right)\alpha \left({n}_{k}\right)\right]<\infty .$

Then the ﬁrst Borel-Cantelli Lemma implies that

or equivalently

Then in particular

This in turn implies that almost surely

${S}_{n}-np<\left(1+\eta \right)\alpha \left(n\right).$

for $n>{n}_{k}$ and large enough $k$ which establishes (1). □

Proof of (2) in the Law of the Iterated Logarithm. Continue with the proof of Equation (2). To prove the second part, it suﬃces to show that there exists ${n}_{k}$ so that ${R}_{{n}_{k}}\ge \left(1-\eta \right)\alpha \left({n}_{k}\right)$ i.o. almost surely. Let ${n}_{k}={\gamma }^{k}$ for $\gamma$ chosen later with $\gamma \in ℤ$ suﬃciently large. The proof will show

 $\sum _{n\ge 1}ℙ\left[{R}_{{\gamma }^{n}}-{R}_{{\gamma }^{n-1}}\ge \left(1-\frac{\eta }{2}\right)\alpha \left({\gamma }^{n}\right)\right]=\infty ,$ (4)

and also

 (5)

Note that ${R}_{{\gamma }^{n}}-{R}_{{\gamma }^{n-1}}\stackrel{\text{dist.}}{=}{R}_{{\gamma }^{n}-{\gamma }^{n-1}}$. It suﬃces to consider

$ℙ\left[{R}_{{\gamma }^{n}-{\gamma }^{n-1}}\ge \left(1-\frac{\eta }{2}\right)\alpha \left({\gamma }^{n}\right)\right].$

Note that

$\begin{array}{llll}\hfill \frac{\alpha \left({\gamma }^{n}-{\gamma }^{n-1}\right)}{\alpha \left({\gamma }^{n}\right)}& =\frac{\sqrt{c\left({\gamma }^{n}-{\gamma }^{n-1}\right)ln\left(ln\left({\gamma }^{n}-{\gamma }^{n-1}\right)\right)}}{\sqrt{c{\gamma }^{n}ln\left(ln{\gamma }^{n}\right)}}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\sqrt{\left(1-\frac{1}{\gamma }\right)\frac{ln\left(nln\gamma +ln\left(1-\frac{1}{\gamma }\right)\right)}{ln\left(nln\gamma \right)}}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \to \sqrt{1-\frac{1}{\gamma }}.\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

Choose $\gamma \in ℤ$ so that

$\frac{1-\frac{\eta }{2}}{1-\frac{\eta }{4}}<\sqrt{1-\frac{1}{\gamma }}.$

Then note that we can choose $n$ large enough so that

$\frac{\left(1-\frac{\eta }{2}\right)}{\left(1-\frac{\eta }{4}\right)}<\frac{\alpha \left({\gamma }^{n}-{\gamma }^{n-1}\right)}{\alpha \left({\gamma }^{n}\right)}$

or

$\left(1-\frac{\eta }{2}\right)\alpha \left({\gamma }^{n}\right)<\left(1-\frac{\eta }{4}\right)\alpha \left({\gamma }^{n}-{\gamma }^{n-1}\right).$

Now considering equation (4), and the inequality above

$ℙ\left[{R}_{{\gamma }^{n}}-{R}_{{\gamma }^{n-1}}\ge \left(1-\frac{\eta }{2}\right)\alpha \left({\gamma }^{n}\right)\right]\ge ℙ\left[{R}_{{\gamma }^{n}-{\gamma }^{n-1}}\ge \left(1-\frac{\eta }{4}\right)\alpha \left({\gamma }^{n}-{\gamma }^{n-1}\right)\right].$

Now using Lemma 5, with $a={\left(1+\delta \right)}^{-1}=\left(1-\frac{\eta }{4}\right)$, we get

$\begin{array}{c}ℙ\left[{R}_{{\gamma }^{n}}-{R}_{{\gamma }^{n-1}}\ge \left(1-\frac{\eta }{2}\right)\alpha \left({\gamma }^{n}\right)\right]\ge \\ ln{\left({\gamma }^{n}-{\gamma }^{n-1}\right)}^{-\left(1-\frac{\eta }{4}\right)}={\left(nln\gamma +ln\left(1-\frac{1}{\gamma }\right)\right)}^{-\left(1-\frac{\eta }{4}\right)}.\end{array}$

The series with this as its terms diverges. Thus, we see that Equation (4) has been proven.

Now notice that

$\begin{array}{llll}\hfill \alpha \left({\gamma }^{n}\right)& =\sqrt{c{\gamma }^{n}ln\left(ln{\gamma }^{n}\right)}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\sqrt{c{\gamma }^{n}\left(lnn+lnln\gamma \right)}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

and so

$\alpha \left({\gamma }^{n-1}\right)=\sqrt{c{\gamma }^{n-1}\left(ln\left(n-1\right)+lnln\gamma \right)},$

which means that

$\sqrt{\gamma }\alpha \left({\gamma }^{n-1}\right)=\sqrt{c{\gamma }^{n}\left(ln\left(n-1\right)+lnln\gamma \right)}.$

Thus, $\alpha \left({\gamma }^{n}\right)\sim \sqrt{\gamma }\alpha \left({\gamma }^{n-1}\right)$. Now choose $\gamma$ so that $\eta \sqrt{\gamma }>4$. Then $\eta \alpha \left({\gamma }^{n}\right)\sim \eta \sqrt{\gamma }\alpha \left({\gamma }^{n-1}\right)>4\alpha \left({\gamma }^{n-1}\right)$ for large enough $n$.

Thus, we have

$\left[{R}_{{\gamma }^{n-1}}\le \frac{-\eta }{2}\alpha \left({\gamma }^{n}\right)\right]\subseteq \left[-{R}_{{\gamma }^{n-1}}\ge 2\alpha \left({\gamma }^{n-1}\right)\right]$

since

$\left[{R}_{{\gamma }^{n-1}}\le \frac{-\eta }{2}\alpha \left({\gamma }^{n}\right)\right]\subseteq \left[{R}_{{\gamma }^{n-1}}\le -2\alpha \left({\gamma }^{n-1}\right)\right].$

Now use (4) and we see that $-{R}_{{\gamma }^{n-1}}<2\alpha \left({\gamma }^{n-1}\right)$ happens almost surely for large enough $n$.

Now ${R}_{{\gamma }^{n}}-{R}_{{\gamma }^{n-1}}$ is a sequence of independent random variables, and so the second Borel-Cantelli Lemma says that almost surely

Adding this with Equation (5), we get that

This is enough to show that

which is enough to show the only remaining part of Khinchin’s Law of the Iterated Logarithm. □

#### Sources

This section is adapted from: W. Feller, in Introduction to Probability Theory and Volume I, Chapter III, and Chapter VIII, and also E. Lesigne, Heads or Tails: An Introduction to Limit Theorems in Probability, Chapter 12, American Mathematical Society, Student Mathematical Library, Volume 28, 2005. Some of the ideas in the proof of Hausdorﬀ’s Estimate are adapted from J. Lamperti, Probability: A Survey of the Mathematical Theory, Second Edition, Chapter 8. Figure 3 is a recreation of a ﬁgure in the Wikipedia article on the Law of the Iterated Law.

_______________________________________________________________________________________________

### Algorithms, Scripts, Simulations

#### Scripts

1p <- 0.5
2k <- 15
3n <- 100000
4coinFlips <- array(runif(n*k) <= p, dim=c(n,k))
5S <- apply(coinFlips, 2, cumsum)
6steps <- c(1:n)
7
8steps2 <- steps[2:n]
9S2 <- S[2:n, ]
10steps3 <- steps[3:n]
11S3 <- S[3:n, ]
12
13ones <- cbind( matrix(1,n-2,1), matrix(-1,n-2,1))
14
15par( mfrow = c(2,2))
16
17matplot((S-steps*p)/steps,
18        log="x", type="l", lty = 1, ylab="", main="Strong Law")
19matplot((S-steps*p)/sqrt(2*p*(1-p)*steps),
20        log="x", type="l", lty = 1, ylab="", main="Central Limit Theorem")
21matplot((S-steps*p)/(steps^(0.6)),
22        log="x", type="l", lty = 1, ylab="", main="Hausdorffs Estimate")
23## matplot((S2-steps2*p)/sqrt(steps2*log(steps2)), log="x", xlim=c(1,n), type="l", lty = 1)
24matplot(steps3, (S3-steps3*p)/sqrt(2*p*(1-p)*steps3*log(log(steps3))),
25        log="x", xlim=c(1,n), type="l", lty = 1, ylab="", main="Law of Iterated Logarithm")
26matlines(steps3, ones, type="l", col="black")
3cAp1x1-1300027:

_______________________________________________________________________________________________

### Problems to Work for Understanding

1. The “multiplier of the variance $\sqrt{2p\left(1-p\right)n}$” function $\sqrt{ln\left(ln\left(n\right)\right)}$ grows very slowly. To understand how very slowly, calculate a table with $n=1{0}^{j}$ and $\sqrt{2ln\left(ln\left(n\right)\right)}$ for $j=10,20,30,\dots ,100$. (Remember, in mathematical work above calculus, $ln\left(x\right)$ is the natural logarithm, base $e$, often written $ln\left(x\right)$ in calculus and below to distinguish it from the “common” or base-10 logarithm. Be careful, some software and technology cannot directly calculate with magnitudes this large.)
2. Consider the sequence
${a}_{n}={\left(-1\right)}^{⌊n∕2⌋}+\frac{{\left(-1\right)}^{n}}{n}$

for $n=1,2,3\dots$. Here $⌊x⌋$ is the “ﬂoor function”, the greatest integer less than or equal to $x$, so $⌊1⌋=1$, $⌊3∕2⌋=1$, $⌊8∕3⌋=2$, $⌊-3∕2⌋=-2$, etc. Find

$\underset{n\to \infty }{limsup}{a}_{n}$

and

$\underset{n\to \infty }{liminf}{a}_{n}.$

Does the sequence ${a}_{n}$ have a limit?

3. Show that the second part of the Law of the Iterated Logarithm, ${liminf}_{n\to \infty }\frac{{S}_{n}-np}{\alpha \left(n\right)}=-1$ follows by symmetry from the ﬁrst part by replacing $p$ with $\left(1-p\right)$ and ${S}_{n}$ with $n-{S}_{n}$.

_______________________________________________________________________________________________

### References

[1]   William Feller. An Introduction to Probability Theory and Its Applications, Volume I, volume I. John Wiley and Sons, third edition, 1973. QA 273 F3712.

[2]   John W. Lamperti. Probability: A Survey of the Mathematical Theory. Wiley Series in Probability and Statistics. Wiley, second edition edition, 1996.

[3]   Emmanuel Lesigne. Heads or Tails: An Introduction to Limit Theorems in Probability, volume 28 of Student Mathematical Library. American Mathematical Society, 2005.

__________________________________________________________________________

__________________________________________________________________________

I check all the information on each page for correctness and typographical errors. Nevertheless, some errors may occur and I would be grateful if you would alert me to such errors. I make every reasonable eﬀort to present current and accurate information for public use, however I do not guarantee the accuracy or timeliness of information on this website. Your use of the information from this website is strictly voluntary and at your risk.

I have checked the links to external sites for usefulness. Links to external websites are provided as a convenience. I do not endorse, control, monitor, or guarantee the information contained in any external website. I don’t guarantee that the links are active at all times. Use the links here with the same caution as you would all information on the Internet. This website reﬂects the thoughts, interests and opinions of its author. They do not explicitly represent oﬃcial positions or policies of my employer.

Information on this website is subject to change without notice.