The CliffHanger
5 May 2015
Joseph is coming from “queima das fitas” and is a little tipsy. He stands near a cliff doing… something. If he takes one more step forward, he falls over the edge. He takes a series of infinite random steps either towards the cliff () or away (). What is his chance of escaping? ^{1}
Let be the probability of moving towards the cliff (), and of moving away (). Then:
outcome  probability 

…  
…  … 
The first few Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786.
Inside []
one can regard the valid combinations of arrows as the same problem of enumerating the valid combinations of balanced ()
’s in an expression. This sequence can be captured using the Catalan number:
Hence, the probability of the cliff hanger escaping is given by:
Which is kind of counterintuitive: in half of the infinite expansions Joseph ends up falls over the edge, and in the other half, not.

This is adapted from problem 35 of Frederick Mosteller’s “Fifty Challenging Problems in Probability”. ↩