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.
Best Answer
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}