Expected # of Returns in a Symmetric Simple Random Walk

1,290

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}

Share:
1,290

Related videos on Youtube

kdrozd
Author by

kdrozd

Updated on August 01, 2022

Comments

  • kdrozd
    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
    kdrozd over 7 years
    Thank you so much. Can you explain the properties you used to get the second to last line?
  • joriki
    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)} \;. $$