Puzzle: a drunkard and a cliff

This article is about a classic brain teaser that is tantalizingly easy to state but much harder to solve.

I came across the puzzle in Frederick Mosteller’s Fifty Challenging Problems in Probability with Solutions:

From where he stands, one step toward the cliff would send the drunken man over the edge. He takes random steps, either toward or away from the cliff. At any step his probability of taking a step away is 2/3, of a step toward the cliff 1/3. What is the chance of falling off the cliff?

(wording in italics are mine)

Can you solve the puzzle?

As usual, there are several solution methods which I will describe below.

Method 1: the gambler’s ruin

This is the trick you can use to solve the puzzle.

We can translate our puzzle into a well-known financial problem whose solution is already known.

In the original setup, we have a drunk man one step away from a cliff, and with some probability he moves one step towards or away from the cliff. We wish to find the chance he falls into the cliff.

Instead, let’s think about this corresponding problem. Consider a gambler who starts with $1. He plays a game of chance in which he gains $1 with probability 2/3 and he loses $1 with probability 1/3. If he continues to play indefinitely, what is the chance he will lose all his money?

If you compare the two problems, you’ll see the chance the drunkard falls off the cliff is exactly the same as the chance the gambler loses all of his money.

The financial problem is known as the gambler’s ruin. As this is a famous problem, I will not restate it here but instead refer you to the Wikipedia article if you’re unfamiliar.

We can use the formula from the “unfair coin flipping” section:

In our application, we know that our gambler starts with $1 and wins with probability 2/3 so we have p = 2/3, q = 1/3, and n₁ = 1. The second player can be thought of as a banker with unlimited money (as there are unlimited steps possible) and so n₂ is infinite (or arbitrarily large).

Substituting those variables yields:

And so, there is a 1/2 chance the gambler avoids ruin and the drunk man avoids falling off the cliff.

Method 2: use of symmetry

Step 1: setup

We can think about the drunkard as a point on a number line with nodes labeled 0 = cliff, 1, 2, 3, …, etc.

The drunk man starts at node 1 and he moves either towards or away from the cliff at node 0.

The paths he take can be simple or more complicated. For instance, he might take a step directly to the cliff (1-> 0), or he might reach node 2 and then head back two steps to the cliff (1 -> 2 -> 1 -> 0), or he could take some other circuitous route like reading node 4, heading to node 2, looping back to 4, and then eventually walking towards the cliff (1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0).

Explicitly calculating the probabilities of these routes would be cumbersome. Instead, we use a short-cut and introduce the following notation.

Let p_n denote the probability of eventually falling off the cliff if the drunk man is currently at node n.

As the man starts from node 1, our goal is to solve for p₁.

Step 2: consider the first move

To proceed, we can break down the drunk man’s first move. There are two possible ways his first move could result in him falling off the cliff. One possibility is he could directly move toward the cliff and fall, with probability 1/3. Another possibility is he could move away to node 2, with probability 2/3, and then he might later fall off with probability p₂.

Combining these events, the following is evident:

p₁ = 1/3 + (2/3) p₂

In fact, it will be easier to deal with this problem more generally. Let q denote the probability he moves away from the cliff and 1 – q the chance he moves toward the cliff.

Then we have:

p₁ = 1 – q + q *p₂

Step 3: find a similar formula for p₂

Now it is necessary to consider p₂ and paths of falling off the cliff from node 2.

The drunk man may wander back and forth many times, but if he is to eventually fall from node 2 then two events must take place. First, he must take a route from node 2 to node 1. Second, that route must be followed by a step from node 1 to node 0.

The latter event, going from node 1 to node 0 clearly has a probability of p₁.

What about the former event–the chance he eventually ends up at node 1, if he is currently at node 2? This seems like a difficult question because the drunk man could take various routes. But in fact the answer is easy: it is p₁! The reason is symmetry: going from node 2 to node 1 is exactly the same situation as moving from node 1 to node 0 with the numbering shifted one-over.

We multiply the probabilities of those independent events to deduce that p₂ = p₁ * p₁.

Finally, we can substitute this back into the equation above to find:

p₁ = 1 – q + q * p₁²

Step 4: solve the equation and pick the right solution

This is a quadratic equation in p₁. There are correspondingly two solutions:

p₁ = 1 and p₁ = (1 – q) / q

The solution that is appropriate is dependent on the value of q.

Recall that q is the probability the drunk man moves away from the cliff.

If q = 1, then the drunk man always moves away from the cliff, and obviously the chance he falls off is 0. For this case, it is clear the second solution (1 – q) / q = 0 is the appropriate one.

For a slightly smaller q, say q = 0.99999, the answer depends on whether the probability of falling off is continuous. It turns out this is the case–as we can verify numerically through the gambler’s ruin solution–and so again the second solution equation is again appropriate.

The solution (1 – q) / q continues to be appropriate as long as q is 1/2 or larger. But once q < 1/2, this equation evaluates to a quantity larger than 1 – which doesn’t make sense as probabilities must be one or less.

So for q < 1/2 it is the case that p₁ = 1.

Putting this together, we can compactly write:

p₁ = min(1, (1 – q) / q)

Here is a plot from WolframAlpha:

For our specific problem, q = 2/3 which means the chance of falling off the cliff is (1 – 2/3) / (2/3) = 1/2.

Thus, the answer is 1/2.

Method 3: recursive relations

I read about this solution method at everything2.com

The idea is to find the recursive relation between the nodes and then solve. (I’m going to assume familiarity with recurrence relations for the rest of the solution…check out this Wikipedia article for an intro)

I’m going to describe the setup, skip over some of the details and then write out the solution.

Again let’s use the notation that p_n denotes the probability of eventually falling off given the drunk man is k steps away from the cliff.

We know that with probability 1/3 he moves towards the cliff and 2/3 he moves away from the cliff. With these transition probabilities, it must be the case that:

p_n = (1/3) p_{n – 1} + (2/3) p_{n + 1}

Here’s another way of seeing why the equation makes sense. From node n, you can either head towards the cliff, node n – 1, or you can head away from the cliff, node n + 1. So the probability of falling from node n is the sum of the probabilities from falling from those states, weighted by the chance you move to those states.

This equation can be rewritten as a recurrence formula where the largest node is written in terms of the previous nodes. Solving for p_n+1 yields:

p_n+1 = (3/2) p_n + (1/2) p_{n – 1}

The next step is to solve the characteristic polynomial:

x² – (3/2) x + 1/2 = 0

(And by the way, notice this is the same equation we found in method 2, step 3!)

This equation has two solutions x = 1, x = 1/2. The general form is thus:

p_n = c₁(1)ⁿ + c₂(1/2)ⁿ

To solve this equation, we need initial conditions. On the one hand, it is clearly the case that p₀ = 1 because that is saying someone already off the cliff is off the cliff with 100 percent probability.

Do we know any other conditions? We don’t know p₁ as that is what we are solving for, and we don’t know p₂, p₃, etc. either.

But we do know one thing: as you get farther away from the cliff, it is less likely you would ever fall off the cliff. In fact, that is the trick to figuring out the other initial condition. If you were infinitely away from the cliff, then you would never fall off. This means we could say p_∞ = 0.

Putting these together, we have

p₀ = c₁(1)¹ + c₂(1/2)¹ = c₁ + c₂ = 1

p_∞ = c₁(1)^∞ + c₂(1/2)^∞ = c_{1 = 0}

Thus, c₁ = 0 and c₂ = 1

The formula is therefore:

p_n = (1/2)ⁿ

As the drunk man starts from node 1, we can thus find p₁ = 1/2.

In other words, there is a 50 percent chance the drunk man falls off the cliff.