# Numerical evidence of law of iterated logarithm (random walk)

The law of iterated logarithm states that for a random walk $$S_n = X_1 + X_2 + ... X_n$$ with $$X_i$$ independent random variables such that $$P(X_i = 1) = P(X_i = -1) = 1/2$$, we have

$$\limsup_{n \rightarrow \infty} S_n / \sqrt{2 n \log \log n} = 1, \qquad \rm{a.s.}$$

Here is Python code to test it:

import numpy as np
import matplotlib.pyplot as plt

N = 10*1000*1000
B = 2 * np.random.binomial(1, 0.5, N) - 1       # N independent +1/-1 each of them with probability 1/2
B = np.cumsum(B)                                # random walk
plt.plot(B)
plt.show()

C = B / np.sqrt(2 * np.arange(N) * np.log(np.log(np.arange(N))))
M = np.maximum.accumulate(C[::-1])[::-1]        # limsup, see http://stackoverflow.com/questions/35149843/running-max-limsup-in-numpy-what-optimization
plt.plot(M)
plt.show()


# Question:

I have done it lots of times, but the ratio is nearly always decreasing to 0, instead of having a limit 1.

Where is the problem?

Here's the kind of plot I have most often for the ratio (which should approach $$1$$): I think the problem is that the number of attempts that can be used in a numerical simulation $n$ is finite.
Notice this: if $Y_n=\frac{S_n}{\sqrt{2n\log\log n}}$, by properties of random walk we know $\mathbb{E}[Y_n]=\frac{\mathbb{E}[S_n]}{\sqrt{2n\log\log n}}=0$ and $$Var[Y_n]=\frac{Var[S_n]}{2n\log\log n}=\frac{n}{2n\log\log n}=\frac{1}{2\log\log n}\to 0$$ which implies $Y_n$ converges to 0 in distribution (we can prove it using Chebyshev's inequality). In particular, if we define $Y_{k,n}=\max_{k\leq \ell \leq n}Y_\ell$ (which is the variable you are using in your code, instead of the variable $Z_k=\sup_{\ell \geq k}Y_{\ell}$ which is the variable one should use), then "$Y_{k,n}\searrow_{k\to n} Y_n$", which in turn converges to 0. So, in the large majority of cases, in your simulations $Y_{k,n}$ should converge to 0.
• @Basj "in the large majority of cases, in your simulations Yk,n should converge to 0." Indeed, for samples of length $10^n$, one obtains a limit at least $\alpha$ with probability roughly $10^{-n\alpha^2}$. For example, to observe a limit at least $.9$ in samples of length $10^7$ requires to repeat the simulation a number of times of the order of $5\cdot10^5$. – Did Feb 2 '16 at 15:45
• Many thanks @NateRiver. You're right: without noticing it, I was indeed working with $max_{k \leq \ell \leq n} Y_\ell \rightarrow_{k \rightarrow n} Y_n$ and not with $sup_{k \leq \ell} Y_\ell$. That clearly explains why it converges to $0$. Thanks for that. Now do you have an idea how I could do a numerical simulation showing that $(2 n \log \log n)^{1/2}$ is the right magnitude order, and that $\sqrt{n} (\log \log n)^{2/3}$ is not the right order of magnitude? Because of the double log (very small values), it's difficult to see this in a simulation. – Basj Feb 2 '16 at 16:50
• @Did Could I get something by considering $Y_{n/2, n} = \max_{n/2 \leq \ell \leq n} Y_\ell$ ? – Basj Feb 2 '16 at 16:53
• @Basj one quick and dirty idea to avoid the problem of your simulations going almost certainly to 0, is to consider the same variables $Y_{k,n}$, but only plot them for $k\in \{1,...,n/2\}$. That said, I ran some simulations with this trick and while they didn't converge to 0 as $k\to n/2$, they didn't converge to 1, either. I'm kind of afraid that the only way to get results somewhat closer to 1 is to use way larger values of $n$ than the ones being used, which sadly results in memory problems : (. – Nate River Feb 4 '16 at 0:56