# Biased random walk away from cliff

A drunken probabilist stands $n$ steps from a cliff's edge. He takes random steps, either towards or away from the cliff, each step independent of the past. At any point, the probability of taking a step away is $2/3$, or a step toward, $1/3$. What are his chances of eventually falling off the cliff?

The textbook has no answer. This is how I did it:

Let $p(i)$ represent the probability of death if you start $i$ steps from the cliff. I first start with the case where $i=1$. Clearly, $$p(1)=\frac{1}{3} + \frac{2}{3}p(2)$$ and $p(2)=(p(1))^2$ so we have the equation $$2(p(1))^2 + 1 - 3(p(1))=0$$ which we can easily solve.

Then to get the case where $i=n$ simply raise $p(1)$ to the $n^\text{th}$ power.

Is this correct? It seems a bit counterintuitive, since it seems as if no matter how far away the drunkard gets, sooner or later some fluke of chance will send him walking straight and steady down the cliff, with probability $1$.

-
It's not that bad. In fact the probability is not $1$ as long as the probability of a step away is $\gt 1/2$. It is $1$ at $1/2$, no matter what $n$ is. –  André Nicolas Apr 13 '13 at 0:46
Hmm. So if the probability is exactly 1/2, then the drunkard is bound to eventually run off the cliff, no matter how ridiculously far he starts? An interesting question might be having two cliffs with, say, 100km between, and placing the drunkard at a position in between, and betting on which side the drunkard falls down first. –  user54609 Apr 13 '13 at 0:49
That too is an old problem, not with cliffs, but stated as a gambling problem. You can google Gambler's Ruin. Two gamblers start out with fortunes $A$ and $B$, and play repeatedly a game in which the one who starts with $A$ has probability $p$ of winning a dollar. When one of them is broke, the game enda. We want the probability $A$ ultimately goes broke. The problem was already studied (and solved) in the $17$th century, when real probability theory started. –  André Nicolas Apr 13 '13 at 1:13

A start. Let $p_1,p_2,p_3,\dots$ be the probabilities of (ultimate) disaster if we start $1,2,3,\dots$ paces from the cliff edge. Then, as you wrote, $p(1)=\frac{1}{3}+\frac{2}{3}p_2$.

Similarly, if $k\ge 2$, then $$p_k=\frac{1}{3}p_{k-1}+\frac{2}{3}p_{k+1}.\tag{1}$$ You can also fit the first equation into this pattern, by defining $p_0$ to be $1$.

Equation $(1)$ is a linear second-order recurrence. You can solve it by general techniques for such recurrences, either generating functions or by working with the characteristic equation. You can also solve the recurrence by ad-hoc techniques. For Equation $(1)$ can be rewritten as $$\frac{2}{3}(p_{k+1}-p_k)=\frac{1}{3}(p_k-p_{k-1}).$$ So if $a_k=p_{k+1}-p_k$, then $a_k$ satisfies a very simple recurrence, for which you can find an explicit solution.

-

I am not quite sure what you are doing above, but here's how I did it. The person will fall off if he takes n+1 steps forward. Let's start with looking at the cases by which the man can take n+1 steps forward.

1. Takes all n+1 steps forward. Probability = (1/3)^(n+1)
2. Takes n+2 steps forward and 1 step backward. Probability = (1/3)^(n+2)*(2/3)
3. Takes n+3 steps forward and 2 steps backward. Probability = (1/3)^(n+3)*(2/3)^2
4. Takes n+4 steps forward and 3 steps backward. Probability = (1/3)^(n+4)*(2/3)^3 ...

So the probability that the man jumps off will be the sum of this infinite series.

Which comes out to (9/7)*(1/3)^(n+1)

-