Hitting probability of biased random walk on the integer line

One asks for the probability $r$ starting at $1$ to eventually reach $0$. The dynamics is invariant by translations hence $r$ is also the probability starting at $2$ to eventually reach $1$. Consider the first step of a random walk starting at $1$. Either the first step is to $0$ then one hits $0$ eventually since one is already at $0$. Or the first step is to $2$ then to hit $0$, one must first hit $1$ starting from $2$ and after that, hit $0$ starting from $1$. This yields the equation $r=\frac13+\frac23r^2$, whose solutions are $r=1$ and $r=\frac12$.

If $r=1$, let us assume the random walk continues with the same dynamics after its first return to $0$. The new portion of the walk is distributed as before hence one returns to $0$ a second time. And so on, hence, calling $X_n$ the position at time $n$, one sees that $X_n=0$ for infinitely many times $n$.

Consider now the homogeneous random walk $(Y_n)$ on the whole integer line whose steps are $+1$ and $-1$ with probabilities $\frac23$ and $\frac13$ respectively. Then $Y_n=Z_1+\cdots+Z_n$ where $(Z_n)$ is i.i.d. and $\mathrm E(Z_n)=\frac13(-1)+\frac23(+1)=\frac13\gt0$. By the strong law of large numbers, $\frac1nY_n\to\frac13$. One can recover $(X_n)$ from $(Y_n)$ through the change of time $\tau_{n+1}=\min\{k\gt\tau_n\mid Y_k\geqslant0,\,Y_k\ne Y_{\tau_n}\}$ for every $n\geqslant0$, and $\tau_0=0$. Then $X_n=Y_{\tau_n}$ and $\tau_n\geqslant n$ hence $\frac1nX_n=\frac1nY_{\tau_n}\geqslant\frac1{\tau_n}Y_{\tau_n}$. One sees that $\liminf\limits_{n\to\infty}\frac1nX_n\geqslant\lim\limits_{n\to\infty}\frac1nY_n=\frac13$.

This is impossible if $X_n=0$ infinitely often, hence $r=\frac12$.

For a random walk whose steps are $+1$ and $-1$ with probability $p\gt\frac12$ and $1-p$ respectively, the same argument yields $r=\frac{1-p}p$.

For a random walk whose steps are $+2$ and $-1$ with probability $p$ and $1-p$ respectively, the crucial argument that to reach $0$ from $n\gt0$, one must reach $n-1$ from $n$, then reach $n-2$ from $n-1$, and so on, is still valid. Hence $r=pr^3+1-p$. If $r\gt\frac13$ the drift $p(+2)+(1-p)(-1)=3p-1$ is positive and one knows that $r\lt1$ hence $r$ is the positive root of the equation $p(r^2+r)=1-p$, that is, $r=\frac1{2p}\left(\sqrt{4p-3p^2}-p\right)$.

The same trick can be applied to any random walk whose steps are almost surely $\geqslant-1$.

With fancier tools one can extract a bit more information from the problem. Let $p>\frac12$ be the probability of stepping to the right, and let $q=1-p$. For $n\in\Bbb N$ let $P_n$ be the probability of first hitting $0$ in exactly $n$ steps. Clearly $P_n=0$ when $n$ is even, and $P_1=q$. In order to hit $0$ for the first time on the third step you must go RLL, so $P_3=pq^2$. To hit $0$ for the first time in exactly $2k+1$ steps, you must go right $k$ times and left $k+1$ times, your last step must be to the left, and through the first $2k$ steps you must always have made at least as many right steps as left steps. It’s well known that the number of such paths is $C_k$, the $k$-th Catalan number. Thus,

$$P_{2k+1}=C_kp^kq^{k+1}=C_kq(pq)^k=\frac{q(pq)^k}{k+1}\binom{2k}k\;,$$

since $C_k=\dfrac1{k+1}\dbinom{2k}k$. It’s also well known that the generating function for the Catalan numbers is $$c(x)=\sum_{k\ge 0}C_kx^k=\frac{1-\sqrt{1-4x}}{2x}\;,$$ so the probability that the random walk will hit $0$ is

$$\begin{align*} \sum_{k\ge 0}P_{2k+1}&=q\sum_{k\ge 0}C_k(pq)^k\\\\ &=qc(pq)\\\\ &=q\left(\frac{1-\sqrt{1-4pq}}{2pq}\right)\\\\ &=\frac{1-\sqrt{1-4pq}}{2p}\\\\ &=\frac{1-\sqrt{1-4q(1-q)}}{2p}\\\\ &=\frac{1-\sqrt{1-4q+4q^2}}{2p}\\\\ &=\frac{1-(1-2q)}{2p}\\\\ &=\frac{q}p\\\\ &=\frac{1-p}p\;. \end{align*}$$

For the present case, $p=\dfrac23$, this yields the probability $\dfrac12$. Rounded to four decimal places, the probabilities of first hitting $0$ in $1,3,5,7,9,11$, and $13$ steps are:

$$\begin{array}{rcc} \text{Steps}:&1&3&5&7&9&11&13\\ \text{Probability}:&0.3333&0.0747&0.0329&0.0183&0.0114&0.0076&0.0053 \end{array}$$

These already account for $0.4829$ (total calculated before rounding) out of the total probability of $0.5$.

Let $P$ be the probability that the drunk will eventually move one unit left. Then $P = \frac13 + \frac23P^2$, because he has a $\frac13$ chance of moving left immediately, and a $\frac23$ chance of moving right, after which he has a $P^2$ chance of eventually moving left twice. Solving this using the usual methods, we get $P=\frac12$.

(Hmm, there's another root at $P=1$. I don't know what to make of that. I hope someone will help out.)

Setting up and solving the equation in a more general case is not hard.

(I first heard this problem posed about a drunk walking home after a long night. His home is at the top of a hill, and he is only one step from the door…)