2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ This doesn't really seem like a suitable question here to me. $\endgroup$ Jun 16 '15 at 4:28
  • 1
    $\begingroup$ Why? Where would you suggest I ask it? $\endgroup$ Jun 16 '15 at 4:50
  • $\begingroup$ Are you looking for an exact answer for $\ell$ and $n$ fixed? Or something asymptotic when $\ell$ and maybe $n$ get large? (and if they both get large, how quickly does $\ell$ grow relative to $n$?) $\endgroup$ Jun 16 '15 at 8:06
  • $\begingroup$ Asymptotic would be fine, with both $n$ and $\ell$ growing. I'm interested in a range of polynomial relationships between $n$ and $\ell$. $\endgroup$ Jun 16 '15 at 14:31
1
$\begingroup$

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".

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This didn't end up being the best way for me to move forward in this case, but this is a really cool way of doing this and I hadn't thought of it before. $\endgroup$ Jun 18 '15 at 23:13
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I missed something. Why does the square of the sum equal the sum of the squares? Aren't there terms $x_i x_j$ where $i \ne j$? $\endgroup$ Jun 18 '15 at 23:16
  • 1
    $\begingroup$ No, because $E[x_i]=0$ for each $i$, and $x_i$ and $x_j$ are independent when $i$ and $j$ are not the same. $\endgroup$ Jun 18 '15 at 23:18
  • $\begingroup$ Oh I see, very cool. $\endgroup$ Jun 18 '15 at 23:35
  • $\begingroup$ (It's the same fact as Var($X+Y$)=Var($X$)+Var($Y$) when $X$ and $Y$ are independent.) $\endgroup$ Jun 19 '15 at 9:26

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.