This is fairly standard. Let *X*_{i} be a symmetric random walk and let *E*_{i} be the event that *X*_{i} = 0. Then and . The diagram shows the number of ways of getting to a particular node. The dashed arrows are meant to represent that the random walk then continues.

In general, at time 2*n*, the number of ways of getting to 0 is . Thus

Stirling’s approximation tells us that

Thus we have:

and therefore

By the second Borel-Cantelli Lemma, since the *E*_{i} are independent,

Thus the symmetric random walk returns to the origin infinitely often.

Advertisements