# Random Walk Stopping Time Calculations

Let $$S_n$$ be a random walk with $$P(S_{n+1}=S_n+1|S_n)=p<\frac{1}{2}$$ and $$1-p=q=P(S_{n+1}=S_n-1|S_n)$$.

Let $$\tau=min(n:S_n=0)$$

How may we show that for any positive integer $$x,\mathbb{E}[\tau|S_0=x]=\frac{x}{1-2p}$$?

Similarly how can we verify that the variance of $$\tau$$ equals $$x\frac{1-(p-q)^2}{(q-p)^3}$$?

Can we see that $$E[\tau|S_n]=S_{n+1}=(S_n+1)p+(S_n-1)(1-p)=2p-1+S_n$$ when $$n=0$$ $$S_n=S_0=x$$?

So $$S_n+1=2p-1+x=0$$ since $$\tau$$ is a stopping time once $$S_n \rightarrow 0$$.

Therefore, $$E[\tau|S_n]=2p-1=-x$$,$$E[\tau|S_n]=\frac{x}{1-2p}$$.

• Your last line makes no sense; if $E[\tau|S_n]=2p-1$, that's what it equals, not $x/(1-2p)$, unless of course $x = (1-2p)(2p-1)$. – jbowman Nov 13 '19 at 20:35
• Try calculating the expected time to go from $S_0$ to $S_0-1$, i.e., go down 1 step, then note that this implies that the expected time to go down $x$ steps is just $x$ times that. – jbowman Nov 13 '19 at 22:00

We start off by observing that in order to get from $$x$$ to $$0$$, we first have to pass through $$x-1$$; the time to get from $$x$$ to $$0$$ will be equal to the first-passage time from $$x$$ to $$x-1$$ + the time from $$x-1$$ to 0, and obviously this applies to expectations as well.

Applying this logic recursively establishes the following relationship:

$$\mathbb{E}(\tau|S_0=x) = x\mathbb{E}(\tau|S_0=1)$$

Now for $$\mathbb{E}(\tau|S=1)$$. If we are at $$S=1$$, we have a probability $$1-p$$ of reaching $$0$$ in one step and a probability $$p$$ of transitioning to $$S=2$$, at which time (now time $$1$$ instead of time $$0$$) we have an expected time-to-$$0$$ of $$2\mathbb{E}(\tau|S=1)$$:

$$\mathbb{E}(\tau|S=1) = (1-p)\cdot 1 + p(1 + 2\mathbb{E}(\tau|S=1))$$

Rearranging terms gives us:

$$\mathbb{E}(\tau|S=1) (1-2p) = (1-p) + p = 1$$

$$\mathbb{E}(\tau|S=1) = {1 \over 1-2p}$$

Combining this with our first equation gives us the desired result:

$$\mathbb{E}(\tau|S_0=x) = {x \over 1-2p}$$

The variance can be found in a similar way.