How often does a one-dimensional lazy random walk end at the origin?

Question

This seems like it's probably a solved problem, but I don't seem to be googling the right keywords.

I want to know the probability that a lazy random walk on $\mathbb{Z}$ ends where it started. To be specific, let $$ X_\ell = \sum_{i=1}^\ell x_i $$ where the $x_i$s are independently and identically distributed, with $$ P(x_i = 1) = P(x_i = -1) = \frac{1}{n} $$ and $$ P(x_i = 0) = \frac{n-2}{n} $$

What is the probability that $X_\ell = 0$?

Answer 1

You can identify the following regimes as $n$ and $\ell$ grow large together:

(1) If $\ell/n\to0$, then the expected number of jumps goes to $0$, and the probability of ending at $0$ goes to $1$.

(2) If $\ell/n$ converges to a constant, say $c$, then the number of jumps converges to a Poisson($2c$) random variable. More precisely, the joint distribution of the number of up jumps and the number of down jumps converges to a pair of independent Poisson($c$) random variables. The probability of being at the origin converges to the probability that two independent Poisson($c$) variables are equal, namely $$ \sum_{r=0}^\infty [ e^{-c} c^r / r! ] ^2, $$ which is $$ e^{-2c} \sum_{r=0}^\infty c^{2r}/(r!)^2. $$

(3) If $\ell/n\to\infty$, then a Gaussian approximation applies as given in the answer by mjqxxxx. To get the convergence of the probability to the value given in that answer, the standard "central limit theorem" (giving convergence of the rescaled sum to a Gaussian distribution) is not enough - what you need is a "local limit theorem".

Answer 2

The probability of $X=t$ ($t\geq 0$) equals the coefficient of $x^t$ in $$\left(\frac{1}{n}x+\frac{1}{n}x^{-1}+\frac{n-2}{n}\right)^\ell=\frac{1}{n^\ell x^\ell}(x^2+(n-2)x+1)^\ell.$$ This coefficient is $$\frac{1}{n^\ell}\sum_{j=0}^{[(\ell+t)/2]}\binom{\ell}{j}\binom{\ell-j}{\ell+t-2j}(n-2)^{\ell+t-2j}.$$

Answer 3

Note that the variance of $X_{\ell}$ is $$ E[X_{\ell}^2]=E\left[\left(\sum_{i=1}^{\ell}x_i\right)^2\right]=\sum_{i=1}^{\ell}E[x_i^2]=\sum_{i=1}^{\ell}\frac{1}{n}=\frac{\ell}{n}, $$ so assuming a Gaussian form for large $\ell$ (as expected from the central limit theorem) gives $$ P[X_{\ell}=0]\sim\sqrt{\frac{n}{2\pi\ell}} $$ as $\ell/n\rightarrow\infty$.