Probability for a $1$D biased random walk to reach one wall before another

Question

Suppose we have random walk $S_n = \sum_{j=1}^n X_j$, where $P(X_j=1) = p$, and $P(X_j=-1)=q=1-p$, $\tau_a=\inf_n (S_n=a)$.

How do we find $p(\tau_b<\tau_{-a})$ where $a>0,b>0$?

Any ideas would be appreciated.

Answer 1

I thought I’d seen this on the site somewhere, but I can’t find it and instead there are two unanswered identical questions, so I’ll answer this one and mark the others as duplicates.

Define a martingale by $M_0=1$ and

$$ M_j=\begin{cases}\frac pqM_{j-1}&X_j=-1\;,\\\frac qpM_{j-1}&X_j=1\;,\\\end{cases} $$

with the stopping rule to stop when one of the walls is hit. The expected value at the stopping time is $1$; the value at the wall $-a$ is $\left(\frac pq\right)^a$; and the value at the wall $b$ is $\left(\frac qp\right)^b$. Thus, with $x=p(\tau_b\lt\tau_{-a})$, we have

$$ x\left(\frac qp\right)^b+(1-x)\left(\frac pq\right)^a=1\;, $$

with the solution

\begin{eqnarray} x &=& \frac{1-\left(\frac pq\right)^a}{\left(\frac qp\right)^b-\left(\frac pq\right)^a} \\ &=& \frac{1-\left(\frac qp\right)^a}{1-\left(\frac qp\right)^{a+b}} \;. \end{eqnarray}

Answer 2

Another way to go is to write down the difference equation for $u(x)=P(\tau_b < \tau_{-a} \mid S_0=x)$ by conditioning on the first step, assuming you start inside the interval.

You obtain $u(x)=pu(x+1)+qu(x-1)$ with $u(b)=1,u(-a)=0$. Rearranging you have $pu(x+1)-u(x)+qu(x-1)=0$ so the roots of the characteristic polynomial are $\frac{1 \pm \sqrt{1-4pq}}{2p}=\frac{1 \pm (1-2p)}{2p}=q/p,1$. So $u(x)=c_1 + c_2 (q/p)^x$ for some $c_1,c_2$ and you can use the boundary conditions to figure out what $c_1,c_2$ are.

Annoyingly, the details of this method have to be adjusted slightly in the unbiased case (since the solution to the equation becomes linear instead of constant plus exponential). The optional stopping approach used in joriki's answer also needs a tweak in this case; going that way in the unbiased case, the $M_j$ you want to consider is just the original random walk itself, so you get $bx-a(1-x)=0$.