mathematics - Does the drunk man fall off the cliff? (a random walk problem)

A drunk man stands with a cliff one step to his left. He takes steps randomly left and right. Each step has probability $p$ of going left and probability $q=1-p$ of going right. Each step is the same size.

If allowed to randomly step indefinitely, what is the probability that the drunk falls off the cliff?

In purely mathematical terms, the drunkard starts at $x=0$ and steps $+1$ or $-1$ with each step. If he ever gets to $x=-1$ he falls off the cliff.

Answer

First, let's consider a modified problem. Suppose that the position of the cliff is moved from $x=-1$ to $x=a$ for some integer $a<0$. Suppose also that the drunkard has a home at $x=b$ for some integer $b>0$, and that if the drunkard reaches his home, he stops walking. Let $d(x)= d_{a,b}(x)$ be the probability the drunkard falls of the cliff, given that the drunkard is at position $x$. We have a recurrence relation $$ d(x)=p\,d(x-1)+(1-p)\,d(x+1). $$ The characteristic polynomial of this recurrence is $(1-p)r^2-r+p$. If we assume $p\neq\frac{1}{2}$, this polynomial has two distinct roots: $$ r=1,\hspace{1cm} r=\frac{p}{1-p}. $$ This means that $d(x)$ has the form $$ d(x)=c_1+c_2\left(\frac{p}{1-p}\right)^x, $$ where $c_1$ and $c_2$ are constants which may depend on $a$, $b$, and $p$ but are independent of $x$. We have boundary conditions $d(a)=1$ and $d(b)=0$, so we can solve for $c_1$ and $c_2$: $$ c_1=\frac{1}{1-\left(\frac{p}{1-p}\right)^{a-b}},\,\,\,c_2=\frac{1}{\left(\frac{p}{1-p}\right)^a-\left(\frac{p}{1-p}\right)^b}. $$

---

We recover the original question by taking $x=0$, $a=-1$, and letting $b$ go to infinity. The probability the drunkard falls in the original question is $$ \begin{align*} \lim_{b\to\infty} d_{-1,b}(0)&=\lim_{b\to\infty}\frac{1}{1-\left(\frac{p}{1-p}\right)^{-1-b}}+\frac{1}{\left(\frac{p}{1-p}\right)^{-1}-\left(\frac{p}{1-p}\right)^b}\left(\frac{p}{1-p}\right)^0\\ &=\lim_{b\to\infty}\frac{\left(\frac{p}{1-p}\right)^b-1}{\left(\frac{p}{1-p}\right)^b-\frac{1-p}{p}}\\ &=\begin{cases}1:p>\frac{1}{2},\\\frac{p}{1-p}:p<\frac{1}{2}.\end{cases} \end{align*} $$ Since the probability of falling approaches $1$ as $p$ approaches $\frac{1}{2}$ from below, the probability of falling must be $1$ when $p=\frac{1}{2}$.