The Drunkard’s Random Walk

It’s the wise man who stays home when he’s drunk.

— Euripedes, ancient Greek tragedian

The Drunkard’s Random Walk is one of the most recognized problems in probability. In its core, the problem is to find the probability of a drunk man dying due to the sheer randomness with which he walks :

A drunk man stands with a cliff one step to his left. He takes steps randomly left and right. Each step has probability 1/3 of going left and probability 2/3 of going right. Each step is of the same size.The man dies if he reaches the cliff. Find the probability of the man dying eventually.

Before delving deeper into the problem we must analyse the term “eventually”. Now, at any point probability of taking a step left is 1/3 but the man might move towards his left in many other ways as well. For example, he might have moved in the below fashions (R: right step and L: left step) :

• L
• (RL)L
• (RLRL)L
• (RRLL)L
• (RRR..LL…RR…LL….)L

The last case is the general movement possible; the only condition being that number of right steps must be more than or equal to the number of left steps at any given time inside the bracketed part and the total number of rights and lefts should be equal inside the brackets.

Now, let the probability of him eventually taking a step left be P. So,

P = ⅓+⅔ * P^2

How do we write the above relation ? Fairly simple, the probability of the man taking a step “eventually left” = probability of taking a step left in the very next move or probability of taking a step right in the very next move and then taking two “eventually left” steps.

P=1 , ½

So, possible values of P are 1 and half. We can neglect P=1 intuitively since we know that at any point the drunkard takes an immediate right step with more probability and therefore his probability of eventually dying should not be 1.

Hence, we get the probability of the drunkard dying to be 1/2 .

But, we now progress to a more general problem and try to do away with the dicey “intuition” part that I mentioned previously. The problem in hand now :

Let us consider the drunkard standing on the number line. Cliff is at x=a and home at x=b (a<b). The drunkard dies on reaching the cliff and is saved on reaching home. In any case he stops moving as soon as he reaches either the cliff or his home.

Probability of taking a step left is p and right is (1-p). Let d(x) be the probability that the drunkard falls off the cliff, given that the drunkard is currently at position x. Therefore, we have a recurrence relation :

d(x)=p*d(x−1)+(1−p)*d(x+1)

How do we interpret the above relation? The probability that the drunkard dies if he starts at position x = (the probability that he takes a step left in the very next move and dies as if he started at position x-1) or (the probability that he takes a step right in the very next move and dies as if he started at position x+1)

Base conditions :

d(a)=1 (i.e. probability of dying starting at cliff x=a is 1)

d(b)=0 (i.e. probability of dying starting at home x=b is 0)

If you have ever gone through university calculus you may have come across the Linear Differential Operator(the D operator) for solving Linear Differential Equations. A similar concept exists to solve linear recurrences, both of homogenous and non-homogenous types (don’t fret if you have not done LDEs, you can quickly go through this pdf for a simple and lucid introduction to solving linear recurrences).

The characteristic polynomial of this recurrence is :

(1−p)*r²−r+p=0

If we assume p≠1/2, this polynomial has two distinct roots:

r=1, r=p/(1−p)

This means that d(x) has the form :

d(x)=c1+c2*((p/(1−p))^x)

where c1 and c2 are some unknown constants. How should we find them? We have two base conditions and two unknowns. We can easily solve the simultaneous equations to get the values of the unknowns :

Before finishing this article, let us once again look at this:

• (RRR...LL…RR…LL….)L

One might notice the similarity of the condition that I have imposed on the bracketed part earlier and Catalan numbers. I found this blog, by Matt Baker of Georgia Tech where he finds the solution to the drunkard’s problem using generating functions. Do check it for some more beautiful maths.

Resources : puzzling.stackexchange/random-walk-problem