Simple random walk bounded below

Question

How to show that for a simple random walk $S_n$, which stops when $S_n=-1$ has expected value of $ES_n=0$ for any $n$? I tried this for up to $n=7$ steps and hoped to see a pattern so I could use $ES_n=\sum_{i=-1}^{n} i\cdot P(S_i=i)$, but it tended to get too complicated. Perhaps there is a simpler way to show this (e.g. by recursion)?

Answer 1

Consider $E[S_n \mid S_{n-1}=k]$:

• when $k=-1$ you have $E[S_n \mid S_{n-1}=-1] = -1 = k$ since you have stopped
• when $k >-1$ you have $E[S_n \mid S_{n-1}=k] = \frac12(k+1)+\frac12(k-1) = k$

So $E[S_n \mid S_{n-1}=k]=k$ for $k \ge -1$ while $S_{n-1} <-1$ is not possible

and so $E[S_n \mid S_{n-1}]=S_{n-1}$ and $E[S_n]=E[S_{n-1}]$, which by induction is equal to $E[S_0]=0$

Answer 2

Say we've taken $n$ random steps (equallly likely to be left or right, except if we're at spot $-1$, in which case we are stepping on the spot, without moving). For each spot $k$, we have probability $p_k$ of being on that spot (with $p_k = 0$ for $k>n$). Thus the expected spot to be in is $$ ES_n\sum_{k = -1}^\infty kp_k = -p_{-1} + 0p_0 + 1p_1+2p_2+\cdots +np_n $$ Now we take one more step. What are the probabilities of being in spot $k$ now? If $k = -1$, it's $p_{-1}+\frac12p_0$, if $k = 0$ it's $\frac12p_1$, and otherwise it's $\frac12p_{k-1} + \frac12p_{k+1}$. The expected value is therefore $$\begin{align} ES_{n+1} = -&\left(p_{-1} + \frac12p_0\right) + 0\left(\frac12p_1\right) + 1\left(\frac12p_0 + \frac12p_2\right) + \cdots \\ &+ n\left(\frac12p_{n-1} + \frac12p_{n+1}\right) + (n+1)\left(\frac12p_n + \frac12p_{n+2}\right) \end{align}$$ Some simple rearranging will tell you that this is actually equal to $ES_n$ (focus on a single $p_k$, and see what its coefficient is). So no matter what the probability distribution for the different spots are, taking a step doesn't change the expected value, and therefore the expected value must stay constant at $ES_0 = 0$.

This argument generalizes to any random walk where at each point you're equally likely to move left as you are to move right, regardless of what probability you have of standing still.