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

  • $\begingroup$ 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)$. $\endgroup$ – jbowman Nov 13 '19 at 20:35
  • $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.