Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
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

1 Answer 1

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.