Random Walk Stopping Time Calculations

Question

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}$.

Answer 1

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.