Asymmetric simple random walk.

Question

For an asymmetric simple random walk (the probability $p$ of a positive increment is not equal to the probability $q$ of a negative increment), it is true that the probability of ever reaching $+1$ is $p/q$ provided that $p < q$ (equivalently, $p < 1/2$). Apparently there is an easy argument which explains why, given this fact, the probability of ever reaching $n$, for a positive integer $n$ is $(p/q)^n$. I can't really determine what the argument is, though. I assume it will have to do with independence/Markov property of the random walk?

Answer 1

Let $P_n$ denote the probability of ever reaching $n$ and let $\tau_n$ denote the corresponding hitting-time of $n$. Then $P_{n+1}=P(\tau_{n+1}<\infty|\tau_{n}<\infty)P(\tau_{n}<\infty)$, since if $\tau_{n}=\infty$, you couldn't possibly reach $n+1$. By definition, this implies $P_{n+1}=P(\tau_{n+1}<\infty|\tau_n<\infty)P_n$. By the markovian property of hitting times, this is equivalent to $P_{n+1}=P(\tau_1<\infty)P_n$. In other words, after the walk hits $n$, it effectively restarts and now needs to hit $n+1$, which is distributionally equivalent to $\tau_1<\infty$.

From this it follows that $P_{n}=P_1^n$.

Answer 2

To ever reach $n$, you need to successfully move a net distance of $1$ to the right $n$ times. Each attempt to do so is independent, and they all have the same probability by the homogeneity in space, so the probability of ever reaching $n$ is $r^n$ where $r$ is the probability to ever move a net distance of $1$ to the right. If you take the result $r=\min \{ 1,p/q \}$ as a black box, then this gives your desired result.

Alternatively, you can derive it using a recurrence relation. Define $u_m(x)$ to be the probability to hit $n$ before hitting $m$ starting from $x$ between $m$ and $n$ inclusive. Then $u_m(n)=1,u_m(m)=0$, and for $m<x<n$ you have $u_m(x)=pu_m(x+1)+qu_m(x-1)$, which you can prove using the total probability formula. This recurrence relation with boundary conditions can be explicitly solved; the desired quantity is $\lim_{m \to -\infty} u_m(0)$.