# A question on calculating probabilities for the random walk

I am currently working on a high school project revolving around the 'Cliff Hanger Problem' taken from ”Fifty Challenging Problems in Probability with Solutions” by Frederick Mosteller.

The problem is 'From where he stands, one step toward the cliff would send the drunken man over the bridge. 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?'

Although the book provided a solution for the eventual probability of falling via the use of recursive equations, I decided to see if I can derive an expression to compute the probability of one falling down prior step N.

What I did was to calculate the number of paths that one can take such that he reaches $X_n=1$, where n=2m-1 for some m (this is because at even steps the person would not fall so I'm only considering the case with odd steps) without reaching $X_j=1$ for any $0\le j< 2m-1$.

The following expression is what I have calculated.

$P_n=1-\sum\limits_{i=0}^{m} p_{2i+1}\\ =1-\sum\limits_{i=0}^{m} \left({{2i+1}\choose{i+1}} - \sum\limits_{k=1}^{i}{{2k}\choose{k}}\right)\left(\left(\frac{1}{3}\right)^{i+1}\left(\frac{2}{3}\right)^{i}\right)$

(I actually made a mistake here as I considered 2m+1 rather than 2m-1, which left the summation sign with $\sum\limits_{k=1}^{i}{{2k}\choose{k}}$ undefined when i=0)

Where $p_2i+1=$ the probability of the path touching 1 at $n=2i+1$ without touching $1$ prior to the step.

The first binomial expression corresponds to choosing n+1 steps towards the cliff out of the 2n+1 steps. The second binomial expression is to subtract the paths that stemmed from previous 1's (in order to ensure that the path did not touch 1 prior to $n=2i+1$.)

However as I plotted this into excel I found that the probability does not converge to $\frac{1}{2}$ as n->infinity, which is the answer the book obtained through recursive relations.

I reviewed my argument but I don't know what did I do wrong (whether I've overcounted or undercounted).

Can anyone help?

-

I'll try a slightly different approach -- for each $n>0$, find the probability $P_n$ that he falls off exactly on step $n$. As you noticed, $P_{2k}=0$ since an even number of steps can only end in him having moved an even number of spots away from his starting position; hence he either is safe, or fell off a turn earlier.

A useful observation here is that if you consider moves to the right as open parentheses, and moves to the left as closed parentheses, and arrange them in order as he takes the respective move, then a sequence of moves which end in him falling on turn $n$ must look like a 'proper' (or correctly matched) arrangement of parentheses, followed by one extra close parens. That is, he must return to his original location eventually without ever having stepped past it, and then finally stepping past it (verify this for yourself if it isn't clear). So, for $n=2k+1$, the number of ways he can fall on turn $n$ is $C_k$, the $k^\text{th}$ Catalan number, which counts the number of ways to correctly match $k$ pairs of parentheses. Each of these paths to fall have equal likelihood, $\left(\dfrac{1}{3}\right)^{k+1} \left(\dfrac{2}{3}\right)^k$ . Further, as we have that $C_k = \frac{1}{k+1}{2k \choose k}$ , then
$$P_{2k+1} = \frac{1}{k+1}{2k \choose k} \frac{2^k}{3^{2k+1}} ~~.$$ So, the probability that after turn $n=2k+1$ , the man has not yet fallen, is $$1 - \sum_{\ell=0}^k P_{2\ell+1} ~~.$$ W|A can't seem to find a closed-form for the summation, but we just want to proceed straight to the limit, and see what the probability $P$ is that he survives indefinitely. So, enlisting this or using the generating function as detailed by Brian's comment, $$P = 1 - \sum_{\ell=0}^\infty P_{2\ell+1} = 1 - \frac{1}{2} = \frac{1}{2} ~~.$$ It is natural that he should survive about half of the time; (I believe that) there is a bijection between those infinite strings of (properly placed) parentheses for which no finite cutoff is balanced, and those which at some point are.

-
You have $$\sum_{k\ge 0}P_{2k+1}=\frac13\sum_{k\ge 0}C_k\left(\frac29\right)^k\;.$$ The generating function of the Catalan numbers is $$g(x)=\sum_{k\ge 0}C_kx^k=\frac{1-\sqrt{1-4x}}{2x}\;;$$ setting $x=2/9$, we have $$\sum_{k\ge 0}P_{2k+1}=\frac{1-\sqrt{1-8/9}}{6(2/9)}=\frac{2/3}{4/3}=\frac12\;.$$ –  Brian M. Scott Aug 14 '12 at 11:53
@BrianM.Scott Lovely -- thanks for that. –  Eugene Shvarts Aug 14 '12 at 16:01
Ah! I see it now! Apparently I subtracting too many paths in my previous expression. Thanks for the great help! :D p.s. Catalan numbers are interesting! –  user37864 Aug 14 '12 at 16:39

I worked on this a while back, and I believe one can generalize from the technique above to show that if the prob. of advancing toward the cliff is p (with p<.5), the prob of falling somewhere in the inf. walk is p/(1-p). In the base case described above the walker starts 1 step away from falling to death. With induction you further show that if the initial distance from the cliff is n, the prob of falling to death somewhere in the inf. walk is [p/(1-p)]^n

-