The Cliff-Hanger

May 5, 2015 in Mathematics

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 (\(p=~^1/_3\)) or away (\(q=1-p=~^2/_3\)). What is his chance of escaping? 1

Let \(p\) be the probability of moving towards the cliff (\(←\)), and \(q\) of moving away (\(→\)). Then:

outcome probability
\(←\) \(p\)
\([→←]←\) \(p[1\cdot q^1p^1]\)
\([→→←←]← \\ [→←→←]←\) \(p[2\cdot q^2p^2]\)
\([→→→←←←]← \\ [→←→←→←]← \\ [→→←→←←]← \\ [→←→→←←]← \\ [→→←←→←]←\) \(p[5\cdot q^3p^3]\)
… \(p[14\cdot q^4p^4]\)
… …

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:

\[\frac{(2 n)!}{(n + 1)! n!}\]

Hence, the probability of the cliff hanger escaping is given by:

\[p+p\sum_{n=1}^{\infty}{\frac{(2 n)!}{(n + 1)! n!}p^n q^n} = 0.5\]

Which is kind of counter-intuitive: in half of the infinite expansions Joseph ends up falls over the edge, and in the other half, not.

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

who am i

I am a Principal Research Engineer at Arm, ex-Professor of Software Engineering at the Faculty of Engineering, University of Porto and Research Associate at INESC TEC. Here you can find my PhD Thesis, my Résumé (not updated since 2020), and my Publications.

what is this

This is a blog about software, some mathematics, and the occasional philosophy. Not necessarily in that order.

© MMXIII — MMXXIV by Hugo Sereno Ferreira.
Content available under Creative Commons (BY-NC-SA) unless otherwise noted.
This site is hosted at Github Pages and created with Jekyll and Bootstrap.