I have a random walk $S_n$ (the increments are Bernoulli $\pm 1$ with probability $1/2$ each). I'd like to test numerically the Law of iterated logarithm:

$$\limsup_{n \rightarrow \infty} \underbrace{\frac{S_n}{\sqrt{2 n (\log \log n)}}}_{Y_n} = 1, \qquad \rm{a.s.}$$

My attemps have failed (see this question) since, when you do a numerical simulation, you can never evaluate this quantity that would be required for the $\limsup$ evaluation (because the computer memory is not infinite...):

$$Z_k=\sup_{\ell \geq k}Y_{\ell}$$

but only:

$$Y_{k,n}=\max_{k\leq \ell \leq n}Y_\ell$$

Question: how can you do a simulation that showcases that the $\limsup$ is $1$? (and have a plot showing a convergence to 1, in the contrary of this failed attempt).

Sidenote: in my case, the increments are not exactly independent, but close to it. I'd like to numerically test if a law-of-iterated-logarithm-like result holds. But for now, I would already be more than happy if I could get a numerical evidence of the standard law in the standard case where increments are independent.

Sidenote2: code for failed attempt:

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()
  • $\begingroup$ You can "test" the theorem by reproducing the illustrations with iterated logarithms in the linked Wikipedia article. If we had $\limsup > 1$, we would exepct curves exceeding the green bounds more frequently on the right side of the graph. If we had $\limsup < 1$, we would expect sparse areas inside the green curves, with curves entering those areas most rarely on the right side of the graph. Of course these tests are not conclusive, but they illustrate the theorem well. $\endgroup$ – user210229 Feb 1 '19 at 5:24

The good news is that for a given value of $n$, the walk value at $n$ only affects lower values of our sequence. Which we don't care about, our interest is in the limiting behaviour. There should be no need to store the sequence.

The problem is $f(n) = \frac{S_n}{\sqrt{2 n \times log(log(n))}}$ doesn't converge, so the graphical proof of a line tending to a value is going to involve some other property of $S_n$,other than a smooth function will be necessary. As you point out the sup cannot be this property. It can't be calculated.

That doesn't mean we can't have a stab at a numerical demonstration, and if we have infinity time, maybe even something stronger.

For example, it would suffice to show

$\forall \epsilon > 0, \forall k: \exists n > k, \text{ s.t. } f(n) > 1 - \epsilon$


$\forall \epsilon > 0, \exists k, \text{ s.t. } \forall n > k : f(n) < 1 + \epsilon$

This is not easily directly testable as is.

For example, I have run this for around a billion with just any old prng. Even with $\epsilon = 0.5$ there was no pattern that made this clear.

However, if we knew the relation between $k$ and $\epsilon$ we could try to prove it by counting the in the above 2 relations.

If we didn't know this relation we could try something like successively halving $\epsilon$, starting at $0.5$. For each value of $\epsilon$ we can 'show' the first equation holds by counting the instances $f(n) exceeds $1 - \epsilon$ and checking that for the next 1000 times this happens the gap is not increasing on average. We can 'show' the second even less well but the ratio of these 'hits' to those of eqn 1 should tend to zero.

There are some practical issues though:

These numbers are going to get huge. In practice there is no way to do this with finite memory as the floating point maths size is going to grow uncontrollably.

The PRNG will have to be perfect for this to work. In practice this is not possible. eventually you will reach the period, at which point all the theory (and practice) disappears and gets replaced by something a lot more linear...

| cite | improve this answer | |

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.