# A Note on the Symmetric Random Walk

This is fairly standard. Let Xi be a symmetric random walk and let Ei be the event that Xi = 0. Then ${\cal P}(E_0) = 1$ and ${\cal P}(E_{2i+1}) = 0$. 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 2n, the number of ways of getting to 0 is $\binom{2n}{n}$. Thus

${\cal P}(E_{2n}) = \frac{\binom{2n}{n}}{2^{2n}}$

Stirling’s approximation tells us that

$n! \approx \sqrt{2\pi n}(\frac{n}{e})^n$

Thus we have:

${\cal P}(E_{2n}) \approx \dfrac{\sqrt{2\pi 2n}\left(\dfrac{2n}{e}\right)^{2n}}{\sqrt{2\pi n}\left(\dfrac{n}{e}\right)^n \sqrt{2\pi n}\left(\dfrac{n}{e}\right)^n 2^{2n}} \\ = \dfrac{1}{\sqrt{n\pi}}$

and therefore

$\sum_{i=0}^\infty \cal P(E_i) = \infty$

By the second Borel-Cantelli Lemma, since the Ei are independent,

${\cal P}(E_{\rm i.o.}) = {\cal P}(\bigcap_{n=0}^\infty\bigcup_{i=n}^\infty E_i) = 1$

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

Advertisements