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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s