5
$\begingroup$

Given a symmetric 1-dimensional random walk starting at 0 -- what is the probability of the walk returning $k$ times to 0 after $2N$ steps?

I know that the total number of paths it can take is $2^{2N}$. My problem is finding the total number of paths returning to 0. Also, since you can only return at even $k$'s, the no. of possible hitting points is $ {{N}\choose{k}}. $

$\endgroup$
4
$\begingroup$

Let $T$ denote the first return time to $0$. The generating function $E_0(s^T)$ of $T$ for the random walk starting at $0$ is such that $$E_0(s^T)=sE_1(s^T),$$ where $E_1(s^T)$ is the generating function of $T$ for the random walk starting at $1$. By the same first-step argument, $$E_1(s^T)=\frac12s(1+E_2(s^T)),$$ where $E_2(s^T)$ is the generating function of $T$ for the random walk starting at $2$. By the Markov property, $$E_2(s^T)=E_1(s^T)^2.$$ Solving this system in $E_0(s^T)$, $E_1(s^T)$ and $E_2(s^T)$ yields $$E_0(s^T)=1-\sqrt{1-s^2}.$$ Thus, the generating function of the $k$th return to $0$ starting from $0$ is $$E_0(s^T)^k=\left(1-\sqrt{1-s^2}\right)^k.$$ These functions have series expansions in powers of $s^2$. The probability that the $k$th return to $0$ occurs after exactly $2N$ steps is the coefficient of $s^{2N}$ in $E_0(s^T)^k$, that is, $$ (-1)^N\sum_{i=1}^k(-1)^i{k\choose i}{i/2\choose N}. $$

$\endgroup$
  • $\begingroup$ But what if the $k$th return happens before $2N$ steps? Will we need to calculate this for all possible $k$th returns for $2M \leq 2N$? $\endgroup$ – Slug Pue May 20 '14 at 10:01
  • $\begingroup$ You could do that, or use the identity $\sum\limits_nP(R\leqslant n)s^n=E(s^R)/(1-s)$, valid for every integer valued nonnegative random variable $R$. $\endgroup$ – Did May 20 '14 at 10:10

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.