# Does a random walk is recurrent'' mean it returns to $0$ with probability 1, or returns infinitely often with probability 1?

For example, consider the simple random walk on $\mathbb{Z}$ starting at $0$. If $E_{2m}$ is the event that the walker is at position $0$ after $2m$ steps, then $\sum_{m=0}^\infty P(E_{2m}) = \infty$. I conclude that the walker will return eventually to $0$ with probability 1. But does this mean the walker will return infinitely often? One cannot apply the Borel-Cantelli lemma because the events are not pairwise independent.

I'm guessing this has something to do with the memoryless nature of the random walk. Thanks for any help.

• There are two types of recurrent natures. A positive recurrent random walk will return to a given position in finite expected time, and a null recurrent random walk returns to a given position with probability 1, but with infinite expected time. Polya showed that a random walk on $\mathbb Z^d$ is null recurrent if $d = 1,2$ and transient if $d > 2$. – user217285 Dec 12 '15 at 2:06
• But it still returns infinitely often for $d = 1, 2$, right? – Brian Tung Dec 12 '15 at 3:06
• @BrianTung: Of course it does. The expected return time is totally irrelevant for this, it follows from the Markov property (no memory). See my answer. – user138530 Dec 12 '15 at 3:25

Yes, the random walk returns infinitely often with prob $1$. You could argue as follows: if not, then at least one of the events "random walk returns only finitely many times, and the last return happens at step $N$" has positive probability. This is absurd because we know that the (conditional) probability that the RW will not return after step $N$ is zero.

• This argument makes no sense if the expected time to return is infinite. – Paul Dec 12 '15 at 3:18
• @Paul: Maybe you can make one more try to understand the (very simple and correct) argument? – user138530 Dec 12 '15 at 3:23
• This basically works, but the last sentence makes use of the Markov property, which the OP may or may not have proved yet. – Nate Eldredge Dec 12 '15 at 3:35
• @NateEldredge: What could be more obvious than this, plus the OP mentions the "memoryless nature of the RW." – user138530 Dec 12 '15 at 3:37
• @Paul The expected return time is not the right thing to look at here. It's a very low fraction of walkers that take a very long time to return and it's these walkers that makes the expected return time infinite. However most walkers returns after a few steps. Note that "with probabillity $1$" does not mean that every possible walker returns infinitely often, it means that almost all of them do. – Kibble Dec 12 '15 at 13:36

This is really Christian's answer; I'm just rewriting it for my own edification (and that of any other readers). Let me know if there are any mistakes.

Let $A_{m}$ be the event that the walker is at the origin after $m$ steps and $B_{m}$ be the event that the walker does not return to the origin after the $m$th step.

Then the events $A_m \cap B_m$ are all disjoint and $\bigcup_{m=0}^\infty A_m \cap B_m$ is the event that the walker steps on the origin only finitely many times. We have that $P(A_m \cap B_m) \leq P(B_m) = 0$ if we can show that the probability of a walker never returning to the origin is $0$, which is what I assumed in my original statement.

Thus $\left(\bigcup_{m=0}^\infty A_m \cap B_m \right)^C$ is the event that the walker returns to the origin infinitely often, and $P\left( \left(\bigcup_{m=0}^\infty A_m \cap B_m \right)^C \right) = 1$.

• This looks good, it's a clean write-up of what I tried to describe verbally. – user138530 Dec 13 '15 at 17:51