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