The Drunkard’s Walk Explained
Stochastic Processes, Markov Chains & Random Walks
There once was a drunk man who wandered far too close to a cliff. From where he stands, one step forward would send the drunk man over the edge. He takes random steps, either towards or away from the cliff. At any step, his probability of taking a step away is 2/3 and a step towards the cliff is 1/3.
What is his chance of escaping the cliff?
Stochastic Processes, Random Walks, & Markov Chains
This classic problem is a wonderful example of topics typically discussed in advanced statistics, but are simple enough for the novice to understand. The problem falls into the general category of Stochastic Processes, specifically a type of Random Walk called a Markov Chain.
Let’s go over what all these terms mean, just in case you’re curious.
A Stochastic Process is a random process that describes the evolution of a system over a unit such as time.
A Random Walk describes a path derived from a series of random steps on some mathematical space, in our case we’ll use integers to describe the drunkards movement in relation to the cliff.
A Markov Chain is a random walk that maintains the memoryless property. In other words, each step, or probability, in the system is independent of the previous. In our scenario, each step the drunk man takes maintains the same probability of moving forwards or backwards whether he’s on the cliff’s edge or many steps away from it.
Starter Calculations
Let’s get a feel for how these probabilities play out by crunching some numbers.
Imagine the drunk man is standing at 1 on a number line. At zero he falls off the cliff. Each number increasing from 0 represents how many steps he is from the cliff.
Let’s visualize the walk in a chart of probabilities.
The man starts 1 step away from the cliff with a probability of 1. The probabilities of moving toward the cliff is 1/3 and the probability of stepping away from the cliff is 2/3.
We’ll place 1/3 at the intersection of 1st step taken, 0 distance from cliff and 2/3 at 1st step taken, 2 steps from cliff.
The branch ends when the man falls off the cliff, leaving us with the righthand path to continue. The man has the option of stepping forward to 1 or backwards to 3 on the imaginary number line.
Since he maintains the initial probabilities at each step, we can multiply the current probability by 1/3 for forward and 2/3 for backward movement.
The possible 3 step paths and probabilities are:
If we total the paths that end with the man falling off the cliff (i.e. the zero column) we find that after three steps the drunkard has 1/3 + 2/27 = 11/27 or 40.7% chance of doom.
When we add the 4 and 5 step paths an interesting pattern emerges. It seems that the man can only fall off the cliff on odd numbered steps. Also after 5 steps we see that the probability of falling off the cliff has creeped up to 0.44 (1/3 + 2/27 + 8/243).
Deriving a Formula
This problem is only one of many variations. The probabilities 1/3 and 2/3 might as well have been any other probabilities summing to 1.
Now that we have an idea of how it works, let’s generalize the problem.
Let the probability of stepping right be some value p and the probability of stepping left be 1 – p (since 1 – p + p = 1) where p is between 0 and 1.
Define the probability of falling off the cliff from 1 as P1. This is of interest since it is always the prerequisite step for falling off the cliff.
The probability P1 is
- the probability of stepping immediately left to 0 (which is 1 – p)
or (+)
- the probability of stepping right to 2 (p) and the probability, P2, of reaching 0 from a path originating from 2.
Combining the above information we obtain the following formula for P1:
What is P2?
P2 is the probability of falling off the cliff on a path originating from 2 steps away. In order to fall off the cliff you have to move from 2 → 1 and from 1 → 0.
Because each step in the walk is independent, we know that moving from 2 → 1 is the same as the probability calculation used to obtain P1 the only difference is we are shifted one step to the right. But this is inconsequential since the memoryless property holds, meaning it is the same mathematically as moving from 1 → 0.
Therefore the probability of moving from 2 → 1 is P1.
Then we must move from 1 → 0, which is the exact definition of P1. Hence P2 is the same as P1•P1, or P1-squared. Making this substitution for P2 in the formula for P1, we obtain:
Solving for P1, the Probability of Eventual Doom
Now we have a quadratic to solve. All these p’s are a little confusing, so I’ll temporarily let P1=x to make the equation look more familiar to us.
A little rearranging and we have the standard form of a quadratic:
When p=0, P1=x=1. This makes sense. When the probability of moving right is zero, we have a 100% chance of falling off the cliff.
When p=1, P1=x=0, meaning that when the probability of moving right is 100%, we are guaranteed not to fall off the cliff.
So what about the probabilities between p=0 and p=1? Such as our original scenario of p=2/3?
This is where solving the above quadratic comes in handy. When you do so, you’ll obtain two solutions:
When we plug p=1/2 into the second solution, we find that the two solutions agree, since (1 – 1/2)/(1/2) also equals 1.
If we plug in a value for p that is less than 1/2, such as 1/4 we find that the probabilities are invalid since they are greater than 1.
What does this mean to us?
This means that we should model this problem with a piecewise function, where values for p less than 1/2 are modeled by x=1, values larger than 1/2 are modeled by (1 – p)/p, and p=1/2 can be modeled by either equation since they both yield x=1.
Back to our original scenario
Given a probability of 2/3 of stepping away from the cliff, and since 2/3 is greater than 1/2, we’ll plug it into the second solution to find the probability that the drunk man will fall off the cliff.
So even with a probability of 2/3 of stepping away from the cliff, the drunk man still has a 50% chance of falling off the cliff! That’s a pretty surprising result!
The Most Surprising Result
In fact, if his probability of stepping away from the cliff is less than or equal to 1/2, our function defaults to the P1=x=1 solution. Meaning that even at a 1/2 chance of stepping in either direction he is guaranteed to eventually fall off the cliff! There is no escaping it.
Turns out that being drunk and standing near a cliff is a mathematically bad idea to say the least…
Thanks for reading!
