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

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

Answer 2

Define the function $ f_{p} = f : \mathbb{R} \to (0, \infty) $ by \begin{equation*} f_p (\lambda) = p \exp (-\lambda) + q \exp( \lambda ) . \end{equation*} We have \begin{equation*} f^{\prime}(\lambda) = -p \exp (-\lambda) + q \exp( \lambda ) \begin{cases} < 0 & \text{ if } \lambda < \log \bigl( (p/q)^{1/2} \bigr) \\ = 0 &\text{ if } \lambda = \log \bigl( (p/q)^{1/2} \bigr) \\ > 0 &\text{ if } \lambda > \log \bigl( (p/q)^{1/2} \bigr) . \end{cases} \end{equation*} If $ p \leq q $, then $ f^{\prime} (\lambda) > 0 $ for all $ \lambda > 0 $. Note, $ f(0) = 1 $. Thus, for $ p \leq q $, we have $ f(\lambda) > 1 $ for $ \lambda > 0$.

Let $ {\cal F}_n = \sigma ( S_0, S_1, S_2, \dotsc, S_n) $ for $ n \geq 0 $. For any $ n \geq 1 $ and $ \lambda \in \mathbb{R} $, we have \begin{equation*} \mathbb{E} \Bigl( \exp \bigl( - \lambda (S_{n+1} - S_n ) \bigr) \mid {\cal F}_n \Bigr) = p \exp (-\lambda) + q \exp( \lambda ) = f(\lambda). \end{equation*}

Now, define, for $ n \geq 0 $ and $ \lambda \in \mathbb{R} $, \begin{equation*} M_n = M_n (\lambda) = \exp ( - \lambda S_n ) \bigl(f(\lambda) \bigr)^{-n} . \end{equation*} Clearly, for any $ n \geq 1, \mathbb{E} ( |M_n| ) < \infty $. Observe that \begin{align*} \mathbb{E} ( M_{n+1} \mid {\cal F}_n ) & = \exp ( - \lambda S_n ) \bigl(f(\lambda) \bigr)^{-n-1} \mathbb{E} \Bigl( \exp \bigl( - \lambda (S_{n+1} - S_n ) \bigr) \mid {\cal F}_n \Bigr) \\ & = \exp ( - \lambda S_n ) \bigl(f(\lambda) \bigr)^{-n} = M_n. \end{align*} Thus, $ \{ M_n : n\geq 0 \} $ is a ${\cal F}_n$ martingale.

Now, $ \tau $ is a ${\cal F}_n $ stopping time. Thus, we have $ \{ M_{ n \wedge \tau} : n\geq 0 \} $ is also ${\cal F}_n$ martingale. So, for any $ n \geq 1 $, we have \begin{equation*} \mathbb{E} \bigl( \exp( - \lambda S_{ n \wedge \tau} ) \bigl(f(\lambda) \bigr)^{- n \wedge \tau} \bigr) = \mathbb{E} \bigl( M_{ n \wedge \tau} \bigr) = \mathbb{E} \bigl( M_{ 0 \wedge \tau} \bigr) = \mathbb{E} \bigl( M_{ 0 } \bigr) = \exp( - \lambda x) . \end{equation*}

Now, we concentrate on $ \lambda > 0$. Define, \begin{equation*} M =\begin{cases} \exp( - \lambda S_{ \tau} ) \bigl(f(\lambda) \bigr)^{- \tau} & \text{ if } \tau < \infty \\ 0 & \text{ if } \tau = \infty \end{cases} = \bigl(f(\lambda) \bigr)^{- \tau} \mathbb{I} ( \tau < \infty ) \end{equation*} where $ \mathbb{I} ( A) $ is the indicator of the set $A$. Note that the last expression follows from the fact that on the event $ \tau < \infty $, we must have $ S_{ \tau} = 0 $ and hence $ \exp( - \lambda S_{ \tau} ) = 1 $.

Clearly, $ M < \infty $. Now, we claim that $ M_{ n \wedge \tau} \to M $. If we take $ \omega $ in the event $ \tau < \infty $, for every $ n \geq \tau (\omega) $, we have $ M_{ n \wedge \tau (\omega)} (\omega) = \exp( - \lambda S_{ n \wedge \tau(\omega)} (\omega) ) \bigl(f(\lambda) \bigr)^{- n \wedge \tau (\omega)} = \exp( - \lambda S_{ \tau (\omega) } (\omega) ) \bigl(f(\lambda) \bigr)^{- \tau (\omega) } M (\omega) \to M(\omega) $. If $ \tau(\omega) = \infty $, we note that $ M_{ n \wedge \tau} \leq ( f(\lambda) )^{ -n } \to 0 = M_{\tau} (\omega) $ as $ S_{ n \wedge \tau} \geq 0 $ and hence $ \exp ( - \lambda S_{ n \wedge \tau} ) \leq 1 $.

Now, we note $ S_{ n \wedge \tau} \geq 0 $ and $ f(\lambda) > 1 $ and hence $ \exp( - \lambda S_{ n \wedge \tau} ) \bigl(f(\lambda) \bigr)^{- n \wedge \tau} \leq \bigl(f(\lambda) \bigr)^{- 1} $ for all $ n \geq 1 $. Further, we note that $ M = f(\lambda)^{-\tau} $ as $ S_{ \tau} = 0 $ for $ \tau < \infty $. Thus, by DCT, we have, for any $ \lambda > 0 $,
\begin{equation*} \mathbb{E} \Bigl( \bigl( f(\lambda) \bigr)^{-\tau} \mathbb{I} ( \tau < \infty ) \Bigr) = \exp ( - \lambda x ). \end{equation*} If we let $ \lambda \downarrow 0$, we have that $ f(\lambda) \downarrow 1 $ and $ \bigl( f(\lambda) \bigr)^{-\tau} \uparrow 1 $. So, as $ \lambda \downarrow 0$, we have \begin{equation*} \bigl( f(\lambda) \bigr)^{-\tau} \mathbb{I} ( \tau < \infty ) \uparrow \mathbb{I} ( \tau < \infty ) . \end{equation*} Thus, by MCT, we have, \begin{equation*} \mathbb{E} \Bigl( \mathbb{I} ( \tau < \infty ) \Bigr) = \mathbb{P} \bigl( \tau < \infty \bigr) = \lim_{ \lambda \downarrow 0} \exp ( - \lambda x ) = 1. \end{equation*} This proves that $ \tau < \infty $ almost surely. Hence, we obtain, \begin{equation} \mathbb{E} \Bigl( \bigl( f(\lambda) \bigr)^{-\tau} \Bigr) = \exp ( - \lambda x ). \tag*{(1)} \end{equation} This is the main equation.

Take $ s = \bigl(f(\lambda) \bigr)^{-1} $. Then $ s \leq 1 $. Set $ \exp (-\lambda) = t < 1$. Now, we have \begin{equation*} s = \frac{ 1}{ p \exp ( - \lambda ) + q \exp ( - \lambda) } = \frac{ 1}{ p t + q \frac{ 1}{ t} } = \frac{ t}{ pt^2 + q } \end{equation*} so that \begin{equation*} spt^2 - t + qs = 0 . \end{equation*} Solving this we have, \begin{equation*} t = \frac{ 1 + \sqrt{ 1 - 4pqs^2 } }{ 2ps } \quad \text{ or } t = \frac{ 1 - \sqrt{ 1 - 4pqs^2 } }{ 2ps } . \end{equation*} Since $ t < 1 $, we get \begin{equation*} \exp ( - \lambda ) = t = \frac{ 1 - \sqrt{ 1 - 4pqs^2 } }{ 2ps } . \end{equation*} Thus, we have \begin{equation*} \lambda = - \log \Bigl( \frac{ 1 - \sqrt{ 1 - 4pqs^2 } }{ 2ps } \Bigr). \end{equation*}

Now, from equation (1), setting $ s = \bigl(f(\lambda) \bigr)^{-1} $, we have \begin{equation*} \mathbb{E} \bigl( s^{\tau} \bigr) = \exp ( - \lambda x ) = \exp \biggl( x \log \Bigl( \frac{ 1 - \sqrt{ 1 - 4pqs^2 } }{ 2ps } \Bigr) \biggr) = \Bigl( \frac{ 1 - \sqrt{ 1 - 4pqs^2 } }{ 2ps } \Bigr)^{x} . \end{equation*}

Not only that we have proved $ \tau < \infty $ almost surely, we have evaluated the probability generating function of this. Now, to evaluate, mean or variance, we just need to differentiate it at $1$. In fact now the whole distribution is accessible. For example, take $x = 1 $ and then we have the probability $ \tau = n $ is given by the coefficient of $s^n $. Clearly, for even values of $n$, the probability is $ 0 $, but odd values we have \begin{equation*} \mathbb{P} \bigl( \tau = 2n-1 \bigr) = (-1)^n \frac{1}{2p} \binom{\frac{1}{2}}{n} (4pq)^{n} . \end{equation*}