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

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


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$): enter image description here


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.

| cite | improve this answer | |
  • 1
    $\begingroup$ @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$. $\endgroup$ – Did Feb 2 '16 at 15:45
  • $\begingroup$ 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. $\endgroup$ – Basj Feb 2 '16 at 16:50
  • $\begingroup$ @Did Could I get something by considering $Y_{n/2, n} = \max_{n/2 \leq \ell \leq n} Y_\ell$ ? $\endgroup$ – Basj Feb 2 '16 at 16:53
  • $\begingroup$ Did and @NateRiver, maybe you would have an idea for this really linked question math.stackexchange.com/questions/1637989/… ? $\endgroup$ – Basj Feb 2 '16 at 22:02
  • $\begingroup$ @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 : (. $\endgroup$ – Nate River Feb 4 '16 at 0:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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