The problem involves a 1-D symmetric simple random walk starting from the origin.

Let $N_{n}$ denote the the number of returns by time n. Show that:

$$ E[N_{2n}]=(2n+1) \dbinom{2n}{n} (\frac{1}{2})^{2n}-1 $$

I know that the Probability of being at zero after 2n steps is $P_{00}^{(2n)} = \dbinom{2n}{n} (\frac{1}{2})^{2n}$, but I'm not sure how to use this to solve for $ E[N_{2n}]$. Any help would be greatly appreciated.


By linearity of expectation, the expected number of returns is the sum of the probabilities of return. Thus we can prove the claim by induction.

Base case: For $n=0$, $E[N_0]=0$, as required.

Induction step: Given $E[N_{2n}]=(2n+1) \dbinom{2n}{n} \left(\frac12\right)^{2n}-1$, we have

\begin{align} E[N_{2(n+1)}]&=E[N_{2n}]+P_{00}^{(2(n+1))}\\ &=(2n+1) \dbinom{2n}{n} \left(\frac12\right)^{2n}-1+\binom{2(n+1)}{n+1}\left(\frac12\right)^{2(n+1)}\\ &=(2n+1) \dbinom{2n}{n} \left(\frac12\right)^{2n}-1+\binom{2(n+1)}{n+1}\left(\frac12\right)^{2(n+1)}\\ &=\left(\frac{(n+1)^2}{2(n+1)}\cdot2^2+1\right)\binom{2(n+1)}{n+1}\left(\frac12\right)^{2(n+1)}-1\\ &=(2(n+1)+1)\binom{2(n+1)}{n+1}\left(\frac12\right)^{2(n+1)}-1\;. \end{align}

  • $\begingroup$ Thank you so much. Can you explain the properties you used to get the second to last line? $\endgroup$
    – kdrozd
    Mar 5 '16 at 22:45
  • $\begingroup$ @kdrozd: I used $$ \binom{2n}{n} = \frac{(2n)!}{n!^2} = \frac{(n+1)^2}{(2n+1)(2n+2)}\frac{(2n+2)!}{(n+1)!} = \frac{(n+1)^2}{(2n+1)(2n+2)}\binom{2(n+1)}{n+1} $$ and $$ \left(\frac12\right)^{2n}=2^2\left(\frac12\right)^{2(n+1)} \;. $$ $\endgroup$
    – joriki
    Mar 6 '16 at 7:41

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.