4
$\begingroup$

It is well known that if you perform a random walk on a 2 dimensional lattice then you will almost certainly reach every lattice point infinitely many times. Is the same result true if, instead of walking on a lattice, we walk in a random orientation (always using a distance of 1)?

Of course, we cannot expect to land on any given point with positive probability, so we modify the question to ask: in any disk, is the probability 1 that the random walk will eventually enter? I think this is equivalent to asking if the random walk will eventually any specific disk infinitely many times (e.g. one around the origin), because then there is a positive probability of taking any set of paths with a positive probability to get to the other disk, which is in theory not hard to construct.

What I have tried:

One approach is to use the result on the lattice (by converting a random walk on the plane to a random walk in the lattice) to prove this result, but I haven't made any meaningful progress in this direction.

Another approach is to mimic a proof that works over the lattice. The only proof strategy I am somewhat familiar with to prove the result over the lattice (although I am aware that there are others) is to show that the sum of the probabilities that you are at the origin after $n$ steps for each $n$ diverges, and then showing that this implies that the probability that you will return infinitely many times is 1. But it seems neither step generalizes directly. Something we could try is to prove that. for any point $P$ and any circle of radius $r$ containing $P$, the sum of the probabilities that the walk (re-)enters that circle on step $n$ is infinite; I think this would fix the second step to work in this case by using the argument from page 163 of https://services.math.duke.edu/~rtd/PTE/PTE4_1.pdf (the proof of theorem 4.2.2) by letting $r$ be half the radius of the original disk and always choosing a circle containing the origin.

$\endgroup$
  • $\begingroup$ nice question${}{}$ $\endgroup$ – Jorge Fernández Hidalgo Dec 3 '17 at 5:25
  • $\begingroup$ Is it easy to prove that we arrive at a point with $x$ coordinate in any open interval? $\endgroup$ – Jorge Fernández Hidalgo Dec 3 '17 at 5:29
  • $\begingroup$ @JorgeFernández I think we can use the central limit theorem to say that the sum of the changes in $x$ coordinates follows a normal distribution with certain parameters, with standard deviation at most $O(\sqrt{n})$ because that is what it would be if the steps were always 1; we can then apply that argument from the book mentioned in the post (I have not done the calculations, but I think this should work). $\endgroup$ – alphacapture Dec 3 '17 at 5:47
  • $\begingroup$ Since any Brownian motion is neighborhood recurrent and any random walk of bounded variance will rescale to a Brownian motion in limit (which is often called invariance principle), we can expect that your random walk (which I think is called Pearson random walk) is also neighborhood recurrent. As one possible direction, we may couple your random walk with Brownian motion evaluated at random times to prove the claim. $\endgroup$ – Sangchul Lee Dec 3 '17 at 5:58
1
$\begingroup$

I think that a sufficiently accurate approximation of your random walk is given by a random walk on a hexagonal lattice. Let us assume that the starting point is the red point and the arrival point is the green one. Let us surround the green point with hexagons having unit diameter.

enter image description here

When performing a step we always leave the hexagon we are in. We may give a color to each hexagon in a particular annulus around the arrival point, like in the picture. If we are in the red zone, we have a positive probability of staying there, a positive probability of going outside and a positive probability of going into the yellow zone. These probabilities are pretty close to $\frac{1}{3},\frac{1}{3},\frac{1}{3}$. Thus, if we are at a distance $d$ from the arrival point, we have a probability $\geq \frac{1}{3^n}$ of entering the green zone in $n$ steps, where $n=\lceil d\rceil$. This should be enough to ensure we eventually enter in a $\frac{1}{2}$-neighbourhood of any point.

In more rigorous terms: assume to start at the origin of the complex plane. For any $R\geq 0$, the probability to be forever trapped in the region $|z|\leq R+\frac{1}{2}$ is clearly zero, so we almost surely leave such region. Let $P_1,\ldots,P_m$ be the vertices of a regular $m$-agon with unit side length inscribed in $\|z\|=R+\frac{1}{2}$. When we leave the region $|z|\leq R+\frac{1}{2}$, we necessarily cross one of the $\approx \pi(2R+1)$ neighbourhoods of radius $\frac{1}{2}$ of $P_1,\ldots,P_m$. Due to radial symmetry, among the paths leaving $|z|\leq R+\frac{1}{2}$ in $k$ steps, about $\frac{1}{\pi(2R+1)}$ of them visit a $\frac{1}{2}$-neighbourhood of $P_j$, for any $j\in[1,m]$. It follows that our random walk almost surely visits a $\frac{1}{2}$-neighbourhood of any point.

$\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.