0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – user217285 Dec 12 '15 at 2:06
  • $\begingroup$ But it still returns infinitely often for $d = 1, 2$, right? $\endgroup$ – Brian Tung Dec 12 '15 at 3:06
  • 1
    $\begingroup$ @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. $\endgroup$ – user138530 Dec 12 '15 at 3:25
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This argument makes no sense if the expected time to return is infinite. $\endgroup$ – Paul Dec 12 '15 at 3:18
  • $\begingroup$ @Paul: Maybe you can make one more try to understand the (very simple and correct) argument? $\endgroup$ – user138530 Dec 12 '15 at 3:23
  • 1
    $\begingroup$ This basically works, but the last sentence makes use of the Markov property, which the OP may or may not have proved yet. $\endgroup$ – Nate Eldredge Dec 12 '15 at 3:35
  • $\begingroup$ @NateEldredge: What could be more obvious than this, plus the OP mentions the "memoryless nature of the RW." $\endgroup$ – user138530 Dec 12 '15 at 3:37
  • 3
    $\begingroup$ @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. $\endgroup$ – Kibble Dec 12 '15 at 13:36
0
$\begingroup$

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

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

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.