# The Drunkard’s Walk and Catalan Numbers

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 $p$ (and therefore his probability of taking a step toward the cliff is $1-p$). What is the probability that the man will eventually fall off the cliff?

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

Let $P_i$ be the probability that the man eventually falls off the cliff if he starts off at position $i$. (Although we’re interested in the value of $x(p) = P_1$, it is convenient to study a more general problem.) It’s easy to see that $P_1 = 1-p + pP_2$ and that $P_2 = P_1^2$. Thus $P_1 = 1-p + pP_1^2$ and therefore $x(p) = 1$ or $x(p) = \frac{1-p}{p}$.  Which answer is correct, though?

Well, if $p = \frac{1}{2}$ the two possible solutions agree, and if $p < \frac{1}{2}$ then $\frac{1-p}{p} > 1$ so the only possibility is $x(p) = 1.$  The tricky part of the problem is to show that if $p > \frac{1}{2}$ then the correct solution is $x(p) = \frac{1-p}{p}.$

To resolve the ambiguity, we proceed as follows. The probability that the drunkard falls off the cliff in exactly one step is $1-p$, and the probability that he falls off in exactly 3 steps is $p(1-p)^2$.  (It’s impossible for the drunkard to fall off the cliff in an even number of steps.) For 5 steps, the answer is $2p^2(1-p)^3$, where the coefficient of 2 corresponds to the two sequences $RRLLL$ and $RLRLL$.  More generally, the probability that the drunkard falls off the cliff in exactly $2n+1$ steps is $C_n p^n (1-p)^{n+1},$ where $C_n$ is the nth Catalan number enumerating all sequences of $n$ R’s and $n$ 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 $x(p) = \sum_{n=0}^\infty C_n p^n (1-p)^{n+1}$, which we can rewrite more symmetrically as $\frac{x(p)}{1-p} = \sum_{n=0}^\infty C_n p^n (1-p)^n.$

This last formula shows that the expression $\frac{x(p)}{1-p}$ is symmetric in $p$ and $1-p$. It follows that for $p > \frac{1}{2}$ we have $\frac{x(p)}{1-p} = \frac{x(1-p)}{p} = \frac{1}{p}.$ Thus $x(p)=\frac{1-p}{p}$ as desired.

This not only solves the Drunkard’s Walk problem, it gives us the formula $\frac{x(p)}{1-p} = \sum_{n=0}^\infty C_n p^n (1-p)^n = \frac{1}{\max(p,1-p)},$ valid for all $0 \leq p \leq 1.$  If we set $z = p(1-p)$, then by the quadratic formula we have $\max(p,1-p) = \frac{1+\sqrt{1-4z}}{2}$ and therefore (after a little algebra) $\sum_{n=0}^\infty C_n z^n = \frac{1}{\max(p,1-p)} = \frac{1-\sqrt{1-4z}}{2z},$ valid for $0 \leq z \leq \frac{1}{4}.$  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 $x(p) = \frac{1-p}{\max(p,1-p)}.$ And the above argument gives a “probabilistic” interpretation of this generating function.

## 2 thoughts on “The Drunkard’s Walk and Catalan Numbers”

1. Very nice. There is a typo in the first paragraph. The expression should be $P_1=(1-p)+pP_1^2$.