# Probability a random walk is back at the origin

I have a symmetric random walk that starts at the origin. With probability $1/6$ it goes right by one and with probability $1/6$ it goes left by one. With probability $4/6$ it stays put. After $n$ time steps, what is the probability that it is at the origin?

The answer should be the probability that you go left by the same amount you go right. I am having difficulty working this out however.

-

The behaviour of the chain is described by the multinomial distribution with three possible results. Let

1. $X_1=$ be the number of steps to the left,
2. $X_2=$ be the number of steps that the chain stays put and
3. $X_3=$ be the number of steps to the right.

Then the vector $(X_1,X_2,X_3)$ follows a multinomial distribution with parameters $n$ (assumed number of steps) and $$p=\left(\frac16, \frac46,\frac16\right)$$ In order to return back to $0$ in $n$ steps you should make equal number of steps to the right and to the left - say $k$ - and to stay put in the remaining $n-2k$ steps (if any). Due to the last equation we have that $$2k\le n \implies k \le \frac n2$$ and since $k$ is an integer, the above inequality can be written as $$k \le \lfloor \frac n2 \rfloor$$ Thus the required probability is equal to $$p_{00}=\sum_{k=0}^{\lfloor \frac n2 \rfloor}\frac{n!}{k!(n-2k)!k!}\left(\frac16\right)^k\left(\frac46\right)^{n-2k}\left(\frac16\right)^k$$

-

A little bit of (discrete) Fourier theory may help to estimate the asymptotic behaviour of $p_n=P(X_n=0)$ when $n\to\infty$.

Namely, the steps $Z_n=X_n-X_{n-1}$ are i.i.d. and their distribution has Fourier transform $E(\mathrm e^{\mathrm i tZ})=u(t)$ with $u(t)=\frac13(2+\cos t)$, hence $$2\pi\cdot P(X_n=0)=\int_{-\pi}^\pi E(\mathrm e^{\mathrm itX_n})\mathrm dt=\int_{-\pi}^\pi u(t)^n\mathrm dt,$$ or, equivalently, $$2\pi\sqrt{n}\cdot p_n=\int_{-\pi\sqrt{n}}^{\pi\sqrt{n}} u(s/\sqrt{n})^n\mathrm ds.$$ When $t\to0$, $u(t)=1-\frac16t^2+o(t^2)$ hence $u(s/\sqrt{n})^n\to\mathrm e^{-s^2/6}$. Furthermore, $\pi\sqrt{n}\to+\infty$, hence a dominating condition such as $u(s/\sqrt{n})^n\leqslant\mathrm e^{-s^2/12}$ for every $|s|\leqslant\pi\sqrt{n}$ yields $$2\pi\sqrt{n}\cdot p_n\to\int_{-\infty}^\infty\mathrm e^{-s^2/6}\mathrm ds=\sqrt{6\pi},$$ that is, $$p_n\sim\sqrt{\frac3{2\pi n}}.$$

-
Thank you very much. – Erhart Mar 31 '14 at 20:59

Let $k$ be the number of left (and right) moves.

Then $$p = \sum_{k\le n/2} \frac{n!}{(k!)^2(n-2k)!} \frac 1{6^{2k}} \left( \frac{2}{3} \right)^{n-2k} = \sum_{k=0}^{⌊n/2⌋} \frac{n!}{(k!)^2(n-2k)!} \frac {2^{2n-4k}}{6^n}$$

-
Thank you although now I need to find a way to approximate it! What is the $[n/2]$ notation? – Erhart Mar 31 '14 at 19:49
this is the largest integer $\le n/2$. – mookid Mar 31 '14 at 19:49
Why not $\lfloor n/2 \rfloor$ ? – Erhart Mar 31 '14 at 19:50
because of $\LaTeX$ issues ;) – mookid Mar 31 '14 at 19:50
@Erhart See Theorem 3.5.2 (page 122) in Richard Durrett's Probability: Theory and Examples. You can get a copy of this book from his website. – Byron Schmuland Mar 31 '14 at 21:02