Probability a random walk is back at the origin

Solution 1:

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

Solution 2:

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