# Intuition of law of iterated logarithm?

Let $X_i$ be iid random variables with $EX_i = 0$ and $Var X_i=1$ and $S_n=X_1+\cdots+X_n$. Then the law of the iterated logarithm says almost everywhere we have

$$\limsup_{n\to\infty}\frac{S_n}{\sqrt{n\log{\log{n}}}} = \sqrt{2}$$

On the other hand the central limit theorem says

$$\frac{S_n}{\sqrt{n}} \to N(0,1)$$

Can anyone explain why dividing by an extra $\sqrt{\log{\log{n}}}$ should go from giving $N(0,1)$ to something bounded by the constant $\sqrt{2}$?

To try to understand I considered the simple case when each $X_n$ is $N(0,1)$ so that $S_n/\sqrt{n}$ is also normally distributed as $N(0,1)$. Then $S_n/\sqrt{n\log{\log{n}}}$ is distributed as $N(0,1/\log{\log{n}})$. Then it would seem to me that to even have just $\limsup_{n\to\infty}\frac{S_n}{\sqrt{n\log{\log{n}}}} \le \sqrt{2}$ requires either

$$\sum_{n=3}^\infty P\left(\frac{S_n}{\sqrt{n\log{\log{n}}}} > \sqrt{2}\right) < \infty$$

or if

$$\sum_{n=3}^\infty P\left(\frac{S_n}{\sqrt{n\log{\log{n}}}} > \sqrt{2}\right) = \infty$$

then to achieve $\limsup_{n\to\infty}\frac{S_n}{\sqrt{n\log{\log{n}}}} \le \sqrt{2}$ the sets {$\omega : \frac{S_n}{\sqrt{n\log{\log{n}}}} > \sqrt{2}$} cannot for example cover the probability space over and over infinitely forever. I don't know the value of $\sum_{n=3}^\infty P\left(\frac{S_n}{\sqrt{n\log{\log{n}}}} > \sqrt{2}\right)$ but since it is the sum of the probability of the tail ends of a bunch of normal distributions you would expect there to be no closed form even for partial sums.

In the other direction for $\limsup_{n\to\infty}\frac{S_n}{\sqrt{n\log{\log{n}}}}$ to not have a value lower than $\sqrt{2}$ isn't it necessary that something like the following holds

$$\sum_{n=3}^\infty P\left(\sqrt{2}-\epsilon < \frac{S_n}{\sqrt{n\log{\log{n}}}} \le \sqrt{2}\right) = \infty$$

Can anyone explain why this number $\sqrt{2}$ should pop up?

I already asked the above on math.stackexchange (link) but apparently moving it here was impossible hence the duplicate post.

-
The proof goes via lots of Borel-Cantelli. Heuristically if you believe the central limit theorem, $S_n$ should be normal with mean 0 and variance $n$, so that $S_n/\sqrt n$ is approximately $N(0,1)$. The appearance of the $\sqrt{2\log\log n}$ is roughly because $\mathbb P(N>\sqrt{2\log\log n})$ is on the cusp of summability. So that $\mathbb P(N>\sqrt{2.000001\log\log n})$ is summable, so happens finitely many times (this is the easier part), whereas $\mathbb P(N>\sqrt{1.999999\log\log n})$ is not summable and so [quite a lot of annoying technical details skipped] happens infinitely often. –  Anthony Quas May 31 '13 at 6:09
To supplement Anthony's comment slightly: recall that the normal distribution in the central limit theorem (with variance $1$) is $\frac{1}{ \sqrt{2\pi}} e^{\frac{x^2}{2 }}$. Roughly speaking, it's the 2 in the denominator of the exponent that ultimately gives rise to the $\sqrt{2}$ in the law of the iterated logarithm. –  Mark Lewko May 31 '13 at 6:40
@Anthony: Are you saying that with $S_n$ having mean $0$ and variance $n$ that it is in fact true that $$\sum_{n=3}^\infty P\left(\frac{S_n}{\sqrt{n}} > \sqrt{(2+\epsilon)\log{\log{n}}}\right) < \infty$$ and $$\sum_{n=3}^\infty P\left(\frac{S_n}{\sqrt{n}} > \sqrt{(2-\epsilon)\log{\log{n}}}\right) = \infty$$ –  user16557 May 31 '13 at 7:38
@unknown: that's clearly false, but I think it's true if the summand is divided by n. –  George Lowther May 31 '13 at 13:30
George: That is a very curious property that I find surprising. I would have thought that convergence would depend on the asymptotics of $K=O(f(n))$ and not on the constant coefficient of $K$. –  user16557 Jun 1 '13 at 2:31

One nice fact that helps intuition is that

## the $\log\log n$ factor "disappears on a sparse subsequence".

To be precise, let's first look at the following equivalent statement of the Law of the iterated logarithm (Khintchine 1924):

Let $X=(X_{0},X_{1},\ldots)$ be a random variable on $\{0,1\}^{\mathbb N}$ having the fair-coin distribution. Let $S_{n}=\sum_{k=0}^{n-1}X_{k}$. Then with probability one, $$\limsup_{n\to\infty}\frac{S_{n}-\frac{n}{2}}{\varphi(n)\sqrt{n}}=1,$$ where $\varphi(n)=\sqrt{\frac{1}{2}\log\log n}$.

Now, the question is, since the standard deviation of $S_{n}$ is simply $\sqrt{n}$, why is there that strange $\varphi(n)$?

Michel Weber (Law of the iterated logarithm for subsequences, 1990) gave the following answer: we can replace $\varphi$ by an arbitrarily slow-growing function if we replace $\limsup_{n\rightarrow\infty}$ by $\limsup_{n\in N}$ for a sufficiently sparse set $N\subseteq\mathbb N$. In detail:

Let $N=\{\nu_{1}<\nu_{2}<\cdots\}\subseteq\mathbb N$ and let $\{Y_{n}\}$ be an i.i.d. sequence with $\mathbb E(Y_{n})=0$ and $\mathbb E(Y_{n}^{2})=1$. Let $S_{n}=Y_{1}+\cdots+Y_{n}$. Let $$p_{n}=|\{m\le n: N\cap (2^{m-1},2^{m}]\ne\varnothing\}|,$$ $$\mathcal L(k)=\ln p_{n}\quad\text{if}\quad k\in (2^{n-1},2^{n}].$$ Then we have $$\limsup_{j\to\infty}\frac{S_{\nu_{j}}}{\sqrt{2\nu_{j}\mathcal L(\nu_{j})}}=1 \quad\text{a.s.}$$

For $N=\mathbb N$ we get the usual law of the iterated logarithm. For sparse sets $N$, the function $\mathcal L(\nu_{j})$ is an arbitrarily slow-growing function, so the dominator is standard deviation ($\sqrt{\nu_{j}}$) times a small factor.

What is happening is that we are looking at the finite sums $S_n$ only for $n\in N$ where $N$ is sparse. But $S_n$ is still $\sum_{k=0}^{n-1}X_k$ with no restriction of $k$ being in $N$. So the computation of $S_n$ is running uninterrupted but we are only opening our eyes to inspect it rather rarely.

-