Random Walk in 2D

Probability Level 3

Consider a random walk along the lattice points of the 2D coordinate plane, starting at the origin. Each step, the walk progresses randomly to an adjacent point in any of the four cardinal directions (positive $y$ , negative $y$ , positive $x$ , negative $x$ ), and this process continues forever.

Will the walk inevitably (i.e., with probability 1) return to the origin at some point in time? What about in 1D?

Yes in 1D; yes in 2D Yes in 1D; no in 2D No in 1D; yes in 2D No in 1D; no in 2D

1 solution

Henry Maltby
Apr 28, 2016

The answer is $\boxed{\text{yes}}$ in both cases.

First, consider the 1-dimensional case. Note that the probability that the process returns after $2n$ steps is $\frac{\binom{2n}{n}}{2^{2n}}$ and the probability after $2n+1$ steps is 0. Then, the expected number of times the walk returns to the origin is $\sum_{n=1}^\infty \frac{\binom{2n}{n}}{2^{2n}} \sim \sum_{n=1}^\infty \frac{1}{\sqrt{\pi n}}.$ Note this statement regarding asymptotic behavior follows from Stirling's approximation . Because this sum diverges to infinity, the walk is expected to return to the origin an infinite number of times. It follows that the process is positive recurrent and returns to the origin with probability $1$ .

Now, consider the 2-dimensional case. Note that this is equivalent to "rotating" (and rescaling) the axes so that each move is now of the form $(+1, \, +1)$ , $(+1, \, -1)$ , $(-1, \, +1)$ , or $(-1, \, -1)$ . Then, each move may be viewed as independently choosing a step in the $x$ direction and a step in the $y$ direction; that is, the 2-dimensional random walk may be seen as a composition of two 1-dimensional random walks. Note the movement in the $x$ and $y$ directions is independent (e.g. $P(x = +1) = P(x = +1 \mid y = +1)$ . Thus, the expected number of times the walk returns to the origin is $\sum_{n=1}^\infty \left(\frac{\binom{2n}{n}}{2^{2n}}\right)^2 \sim \sum_{n=1}^\infty \frac{1}{\pi n}.$ Because this sum diverges to infinity, the walk is expected to return to the origin an infinite number of times. It follows that the probability the process returns to the origin eventually is $1$ .

Note that this rotation trick for the 2-dimensional case fails in any higher dimension (try it yourself!). In fact, an analogous process in any higher dimension does not necessarily return to the origin!

Henry, you write:

Because the probabilities that the x-dimensional random walk returns to the origin and the probability that the y-dimensional random walk returns to the origin are independent, it follows that the probability that the 2-dimensional random walk returns to the origin is their product and therefore 1.

However, isn't this product rather the chance that both events happen sometime or other ? I.e., it's the probability that both there is some point at which the walk recrosses the x axis and there is some point at which the walk recrosses the y axis. If that's right, you might need a slightly fancier argument, perhaps to the effect that, since for both x and y there is some finite expected period for attaining the value zero, there will be infinitely many returns in both dimensions with probability one, and since there is always some nonzero chance that the next returns will be simultaneous, there will be zero chance that the returns to zero never happen simultaneously.

Mark C - 5 years, 1 month ago

Hi, Mark. You are absolutely correct, and the solution I have presented is not exactly rigorous; I hoped instead to provide intuition for a neat approach to the problem, albeit at the cost of formality (and, to the careful reader, clarity). Indeed, not only did I skip over the details you outlined, but I omitted the condition for even having such details (see next paragraph). Arguably, the most straightforward approach to the problem is to calculate the expectation directly, but that method shares nothing in common with my approach, alternatively requiring a statement akin to Stirling's factorial approximation.

As you noted, the step I skimmed over is noting that the 1-D case is actually positive recurrent , i.e. has nonfinite expectation (as opposed to null recurrent where the probability of return is still 1 but the expectation is finite). I'll try later to see if I can rework the beginning of my solution to include that fact :).

I did wonder if there was a way to conclude the argument without relying on such nuance, to avoid detracting from the main ideas here (i.e., without relying on Stirling's approximation). Maybe not?

Henry Maltby - 5 years, 1 month ago

It's a surprising result, especially in 2-D, and was proven by Pólya in 1921 with his Recurrence Theorem . An exact calculation exists for a 3-D walk , but no closed forms are known for any higher dimensions. For asymmetric random walks the probability is less than 1 in any dimension.

Brian Charlesworth - 5 years, 1 month ago

I thought of it as being a little analogous to the Infinite Monkey Theorem. An infinite walk over the x-y plane with a uniform step size would almost surely cover all the points of the form (n step size, m step size), where n and m are integers.

Vibhor Bhagat - 5 years, 1 month ago

The problem is worded rather vaguely - It doesn't specify whether each step is of integer length, or even of the same length as the other steps.

Ariel Gershon - 5 years, 1 month ago

This may be going deeper than most want to go, but if you do consider steps of various length, including irrational lengths, it seems the probability would be zero. Even if one puts an upper bound on the step lengths, it seems the probability would still be zero, based on the implications of what I know of aleph-null and aleph-one. Actually, I am rather skeptical of my conjecture. My head hurts thinking about it.

Brad Morin - 5 years, 1 month ago

Random Walk in 2D

1 solution

0 pending reports