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$.
 A: 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. 
A: 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.


*

*Takes all n+1 steps forward. Probability = (1/3)^(n+1)

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

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

*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)
