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}$.
 A: 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$.
A: 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*}
