Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 7 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer
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} $$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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