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 moderate amount of (discrete) Fourier theory allows to provide an explicit formula for, and to estimate the asymptotic behaviour of $$P(X_n=0)$$ when $n\to\infty$, where $(X_n)_{n\geqslant0}$ is the random walk described in the question.

1. Namely, the steps $Z_n=X_n-X_{n-1}$ are i.i.d. and their distribution has Fourier transform $$u(t)=E(\mathrm e^{\mathrm i tZ})=\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 $$

2. This already yields an explicit formula for $p_n$, expanding the integrand, since, for every $k$, $$\int_{-\pi}^\pi\cos^{2k}t\,\mathrm dt=2\pi\cdot{2k\choose k}\frac1{2^{2k}}\qquad\int_{-\pi}^\pi\cos^{2k+1}t\,\mathrm dt=0 $$ hence the binomial identity $$u(t)^n=\frac1{3^n}\sum_k{n\choose k}\cdot\cos^kt\cdot2^{n-k} $$ yields $$P(X_n=0)=\frac1{3^n}\sum_k{n\choose2k}\cdot{2k\choose k}\frac1{2^{2k}}\cdot2^{n-2k}$$ or, equivalently,

$$P(X_n=0)=\left(\frac23\right)^n\sum_k{n\choose2k}\cdot{2k\choose k}\frac1{2^{4k}}$$

3. But, perhaps more interestingly than the cumbersome sum above, this approach also yields precise asymptotics of $P(X_n=0)$ when $n\to\infty$, since one can rewrite the integral formula above as $$ 2\pi\sqrt{n}\cdot P(X_n=0)=\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}$ allows to apply Lebesgue dominated convergence theorem, showing that $$ 2\pi\sqrt{n}\cdot P(X_n=0)\to\int_{-\infty}^\infty\mathrm e^{-s^2/6}\mathrm ds=\sqrt{6\pi}, $$ that is,

$$ \lim_{n\to\infty}\sqrt{n}\cdot P(X_n=0)=\sqrt{\frac3{2\pi}}. $$


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} $$

  • $\begingroup$ Thank you although now I need to find a way to approximate it! What is the $[n/2]$ notation? $\endgroup$ – Erhart Mar 31 '14 at 19:49
  • $\begingroup$ this is the largest integer $\le n/2$. $\endgroup$ – mookid Mar 31 '14 at 19:49
  • $\begingroup$ Why not $\lfloor n/2 \rfloor$ ? $\endgroup$ – Erhart Mar 31 '14 at 19:50
  • $\begingroup$ because of $\LaTeX$ issues ;) $\endgroup$ – mookid Mar 31 '14 at 19:50
  • 1
    $\begingroup$ @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. $\endgroup$ – user940 Mar 31 '14 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.