1
$\begingroup$

We have a random walk in 2D. In this many dimensions, we return to the origin with probability $1$. However, the number of steps it takes to do so seems to vary greatly from computer simulations I've ran.

Thus, I'm curious about the distribution concerning the number of steps required for one to return to the origin in a 2D random walk. An explicit probability for each $n$ steps would be fantastic, but an expected value will do, too. I'm just curious about the topic in general.

For what it's worth, I have looked into the 1D case, which seems a quite bit easier.

$\endgroup$
  • 2
    $\begingroup$ The expected number of steps for a 1-d symmetric random walk to return to the origin is infinity. The 2-d random walk is harder to return, so its expected recurrence time is also infinity. $\endgroup$ – Michael Mar 19 '16 at 7:01
  • 1
    $\begingroup$ You might want to look at oeis.org/A054474. $\endgroup$ – Ivan Neretin Mar 19 '16 at 9:22
  • $\begingroup$ @Michael That makes sense. Most simulations took a single digit amoutn of steps, but ones that didn't tended to be very strong outliers taking 1000+ steps. The variance is certainly notable. $\endgroup$ – MCT Mar 19 '16 at 16:06
  • $\begingroup$ A simple way to see that a symmetric 1-d random walk takes an average of $\infty$ steps to move one step to the left is as follows: Define $m_1$ as the average time to move one step to the left and $m_2$ as the average time to move 2 steps to the left. Then $$ m_1 = 1 + (1/2)m_2 \quad , \quad m_2 = m_1 + m_1 $$ So $m_1 = 1 + (1/2)(2m_1)=1+m_1$. So $m_1=\infty$. $\endgroup$ – Michael Mar 19 '16 at 17:18
4
$\begingroup$

For a symmetric random walk in two dimensions the probability that you are back at the origin after the $2n$th step is:

$$p_0(2n) = \left(\frac{1}{4}\right)^{2n} \sum_{m=0}^{n}\frac{(2n)!}{(m!)^2[(n-m)!]^2} = \left(\frac{1}{2}\right)^{4n} \:{2n\choose n}^{\!\!2}$$

$\endgroup$
  • 2
    $\begingroup$ could you hint at how you computed this sum? $\endgroup$ – Yotam Alon Apr 1 '17 at 12:38
1
$\begingroup$

Following on JKnecht's calculation we see that $$p_0(2n)=\left({2n\choose n}{1\over 2^{2n}}\right)^{\!\!2} = {1\over (2n)^2}\, \prod_{j=1}^{n-1}\left(1+{1\over 2j}\right)^{\!\!2} \geq {1\over 4n^2}\, n ={1\over 4n},\quad n\geq1.$$ Since $\sum_{n=1}^\infty P(X_{2n}=0)\geq\sum_{n=1}^\infty {1\over 4n}=\infty$, the 2-$d$ walk is recurrent.

$\endgroup$

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.