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.

(Image courtesy of https://medium.com/i-math/the-drunkards-walk-explained-48a0205d304)

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s