In this post, I’d like to present an amusing and off-the-beaten-path solution to the classical “Drunkard’s Walk” problem which at the same time derives the well-known generating function for the Catalan numbers.  This solution evolved from a suggestion by my former undergraduate student Stefan Froehlich during a discussion in my Math 4802 (Mathematical Problem Solving) class at Georgia Tech in Fall 2007.

In case you’re not familiar with it, here’s the problem (in a formulation I learned from this book by Frederick Mosteller):

A drunken man standing one step from the edge of a cliff takes a sequence of random steps either away from or toward the cliff. At any step, his probability of taking a step away from the cliff is  (and therefore his probability of taking a step toward the cliff is ). What is the probability that the man will eventually fall off the cliff?

Solution: Imagine that the man starts at on the real number line and that he steps one unit to the left with probability and one unit to the right with probability .  He falls off the cliff if and only if he at some point reaches .

Let be the probability that the man eventually falls off the cliff if he starts off at position . (Although we’re interested in the value of , it is convenient to study a more general problem.) It’s easy to see that and that . Thus and therefore or .  Which answer is correct, though?

Well, if the two possible solutions agree, and if then so the only possibility is  The tricky part of the problem is to show that if then the correct solution is

To resolve the ambiguity, we proceed as follows. The probability that the drunkard falls off the cliff in exactly one step is , and the probability that he falls off in exactly 3 steps is .  (It’s impossible for the drunkard to fall off the cliff in an even number of steps.) For 5 steps, the answer is , where the coefficient of 2 corresponds to the two sequences and .  More generally, the probability that the drunkard falls off the cliff in exactly steps is where is the nth Catalan number enumerating all sequences of R’s and L’s in which (reading left to right) the cumulative number of R’s is always at least the cumulative number of L’s.  Therefore , which we can rewrite more symmetrically as

This last formula shows that the expression is symmetric in and . It follows that for we have  Thus as desired.

This not only solves the Drunkard’s Walk problem, it gives us the formula valid for all  If we set , then by the quadratic formula we have and therefore (after a little algebra) valid for  This is the generating function for the Catalan numbers.

Conclusion: The generating function for the Catalan numbers is equivalent to the fact that the solution to the Drunkard’s Walk problem is And the above argument gives a “probabilistic” interpretation of this generating function.