Random Walk Stopping Time Calculations

random variablesrandom walkstochastic-processes

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

Best Answer

Note that the problem is equivalent to the following: a random walk with i.i.d. increments $\{X_i\}$ ($\mathsf{P}(X_i=1)=p$ and $\mathsf{P}(X_i=-1)=q$) starting at $0$ hits $-x<0$, i.e. $\tau=\min\{n:S_n=-x\}$ with $S_0\equiv 0$.

Then the results follow from the Wald equations ($\because \mathsf{E}\tau<\infty$ for $p<1/2$ and $x>0$): $$ \mathsf{E}S_{\tau}=\mu\cdot\mathsf{E}\tau \quad\text{and}\quad \mathsf{E}(S_{\tau}-\mu\tau)^2=\sigma^2\cdot\mathsf{E}\tau, $$ where $\mu\equiv\mathsf{E}{X_1}$ and $\sigma^2\equiv\operatorname{Var}(X_1)$. In your case $S_{\tau}=-x$, $\mu=2p-1$, and $\sigma^2=1-(p-q)^2$.

Related Question