Expected Crossings of Zero Line in Random Walk

probabilityrandom walk

Suppose we have a simple random walk:

$$
x_t = x_{t-1} + \epsilon_{t}
$$

Where

$$
\epsilon_{t} = iid\ \mathcal{N} (0,1)
$$

Assume that x starts at 0 what is the expected number of times x will cross the 0 point for N number of periods?

I am more interested in the method of obtaining the answer than the answer itself.

What I have so far: I was looking at simple case where N = 2, and in this case expected number of crosses seems to be 0.25. Intuitively, this makes sense, in the first period we moved somewhere, and on the second the probability that we move in the right direction is 0.5, and of that 0.5, the probability (on average) that we move back far enough to cross is 0.5, so 0.5 * 0.5 => 0.25.

I validated this with simulation:

import numpy as np

def simulations(n, n_iterations):
    return sum(my_one_run(n) for _ in xrange(n_iterations)) / float(n_iterations)

def my_one_run(n):
    path = [0]
    n_crosses = 0
    for i in xrange(n):
        prev = path[-1]
        new_x = prev + np.random.normal(0,1)
        path.append(new_x)
        if prev * new_x < 0:
            n_crosses += 1
    return n_crosses

And my results have been confirmed:

In [66]: simulations(2, 1000000)
Out[66]: 0.250249

However, I don't see how to proceed for a more complicated case, even more general case.

(This is not a homework question, if this matters. I am just trying to explore something in this area and wanted to start with a basic case.).

Best Answer

The location density after $n$ moves is $$ \frac1{\sqrt{n}}f\left(\frac{x}{\sqrt{n}}\right) $$ Given that we are currently at $x$, the probability that we will cross the origin on the next move is $$ \int_{t\ge|x|}f(t)\,\mathrm{d}t $$ So the probability that on move $n+1$, we cross the origin is $$ \int_{\mathbb{R}}\int_{t\ge|x|}\frac1{\sqrt{n}}f\left(\frac{x}{\sqrt{n}}\right)f(t)\,\mathrm{d}t\,\mathrm{d}x =\int_{\mathbb{R}}\int_{t\ge|x|\sqrt{n}}f(x)f(t)\,\mathrm{d}t\,\mathrm{d}x $$ which is the probability that given a Gaussian distribution on $\mathbb{R}^2$ that we end up in the wedge $\{(x,t):t\ge|x|\sqrt{n}\}$, which is $$ p_n=\frac1\pi\tan^{-1}\left(\frac1{\sqrt{n}}\right) $$ Thus, the expected number of zero-crossings in $n$ moves would be $$ e_n=\frac1\pi\sum_{k=1}^{n-1}\tan^{-1}\left(\frac1{\sqrt{k}}\right) $$ Apply this to $n=2$, and we get $\frac14$ precisely.

Here is a short table $$ \begin{array}{r|l} n&e_n\\ \hline 2&0.250000\\ 3&0.445913\\ 4&0.612580\\ 5&0.760164\\ 6&0.894024\\ 7&1.017400\\ 8&1.132426\\ 9&1.240600\\ 10&1.343016 \end{array} $$ Asymptotically, the expected number of zero crossings is $$ \frac{2n^{1/2}}\pi+C+\frac1{6\pi n^{1/2}}-\frac1{120\pi n^{3/2}}-\frac1{840\pi n^{5/2}}+\frac5{8064\pi n^{7/2}}+\frac1{4224\pi n^{9/2}} $$ where $C=-0.686843660075987093$

Related Question