# Probability of random walk returning to 0

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

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}.$$
• 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$? – Slug Pue May 20 '14 at 10:01
• 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$. – Did May 20 '14 at 10:10