Expected # of Returns in a Symmetric Simple Random Walk
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}
Related videos on Youtube
kdrozd
Updated on August 01, 2022Comments
-
kdrozd over 1 year
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.
-
kdrozd over 7 yearsThank you so much. Can you explain the properties you used to get the second to last line?
-
joriki over 7 years@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)} \;. $$