I'm trying to solve the following variation of the Drunkard Walk:
From where he stands, one step toward the cliff would send the drunken man over the edge. He takes random steps, either toward or away from the cliff. At any step his probability of taking a step away is $\frac{2}{3}$, of a step toward the cliff $\frac{1}{3}$. What is his chance of escaping the cliff?
My initial idea was to draw a tree and come up with an infinite sum that looked like this:
$$ \sum_{n=0}^{\infty} \left(\frac{2}{3}\right)^n\left(\frac{1}{3}\right)^{n+1} $$
But this doesn't take into consideration the scenario where the man walks back and forth from, say, position 2 to 1 for a couple turns, and then walks off. So I corrected with this sum:
$$ \sum_{n=0}^{\infty} \binom{2n+1}{n} \left(\frac{2}{3}\right)^n\left(\frac{1}{3}\right)^{n+1} $$
Which is intuitive, at least to me, because it sums up all scenarios where the man takes exactly n steps backwards, and then that $+1$ $(n+1)$ steps forward and walks off the cliff. But this sum converges to $1.5$ $(>1)$ and is not a valid probability.
Could someone please explain where I'm going wrong? Also, how would I solve this problem using a Markov Chain/transition matrix (I'm not very familiar with either)
EDIT: If anyone else is interested, I found another really neat solution:https://medium.com/i-math/the-drunkards-walk-explained-48a0205d304
In order to compute the probability $p$ of falling down the cliff we just have to sum up the probabilities of doing so in $2n+1$ steps for $n=0,1,2,\dots$. The Catalan number $C_n$ counts the ways of taking $2n$ steps starting and ending at the initial point before falling down in the $(2n+1)$-th and final step. The probability of each of those paths (inluding the last step) is clearly $(2/3)^n$ times $(1/3)^{n+1}$, so $$ p=\sum_{n=0}^\infty C_n\,\frac{2^n}{3^{2n+1}} = \frac 1 3\,\sum_{n=0}^\infty C_n\,\big(\,\frac 2 9\,\big)^n = \frac 1 3\,f(\,2/9\,)\,, $$ where $f$ is the well-known generating function given by $$ f(x)=\sum_{n=0}^\infty C_n\,x^n = \frac{1-\sqrt{1-4x}}{2x}\,. $$ Since $f(\,2/9\,)=3/2$ we conclude that $p=1/2$, and then the probability of escaping is $1/2$ as well.