4
$\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$
4
  • 3
    $\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
    Commented Mar 19, 2016 at 7:01
  • 1
    $\begingroup$ You might want to look at oeis.org/A054474. $\endgroup$
    – Ivan Neretin
    Commented Mar 19, 2016 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$
    – MT_
    Commented Mar 19, 2016 at 16:06
  • 1
    $\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
    Commented Mar 19, 2016 at 17:18

2 Answers 2

Reset to default
7
$\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
  • 4
    $\begingroup$ could you hint at how you computed this sum? $\endgroup$
    – Yotam Alon
    Commented Apr 1, 2017 at 12:38
  • 2
    $\begingroup$ Caveat: Neither the question nor (either) answer explain what a "symmetric random walk in two dimensions" means. Does it mean every step we pick either North, South, East, West, equally likely? Or does it mean we have a North-South walk that is independent from an East-West walk, so we can go North and West at the same time? The answer above seems to fit the latter case. $\endgroup$
    – Michael
    Commented Jul 14, 2020 at 22:03
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .