(See The Drunk Guy on a Cliff Puzzle
if you haven't read the
Well, the first step to solving any math puzzle is to
figure out some kind of equation to model the situation.
In this case, the best we can do is express the
likelihood that he will eventually fall off when he's
steps away in terms of the probability when he's n + 1 steps
away and the probability when he's n - 1 steps away. We
define p(n) to be: "The probability, when n steps away from
the cliff edge, that the drunk person will eventually fall off." So:
p(n) = (1/3)⋅p(n - 1) + (2/3)⋅p(n + 1)
Makes sense, right? The probability at node a in your
state machine graph is (the
probability at node b)⋅(the probability of
getting to node b from a) + (the probability at
node c)⋅(the probability of getting to node c
from a)...and so on for all nodes you can reach from a.
Now, this is fascinating, but doesn't lead to an immediate solution. The key insight
here is to see this recursively defined function as a
recurrence relation. To be able to treat it a recurrence relation,
you need to have pn in terms of pn-1, pn-2,
and so on. So we shift our definition to the right by one unit of n,
and solve for pn:
Let k = n - 1.
Then, pk-1 = (1/3)⋅pk-2 + (2/3)⋅pk
Therefore pk=(3/2)⋅pk-1 - (1/2)⋅pk-2
The next step is where this solution stops making sense if
you haven't had discrete math or differential
equations. Read up on
recurrence relations, or just trust that this works.
You have to find and solve the characteristic polynomial of this
x2 - (3/2)⋅x + (1/2)=0
Immediately you recognize that you can't factor this in
integers, and dredge the Quadratic Formula from your
memory of high school days.
Then you know that:
x = ((3/2) ± √((9/4) - 4⋅1⋅(1/2)))/2
x = ((3/2) ± √(1/4))/2
x = ((3/2) ± (1/2))/2
x = 1 or 1/2
Now that you have the roots of the characteristic
polynomial, you can state the general solution for recurrence relations
of this type:
pn = c1⋅1n + c2⋅(1/2)n
Again, if you don't believe me, look it up. I can't explain all of
discrete mathematics in a single node, but there are plenty of
helpful references out there.
Now, to get the full solution, you need some initial conditions:
values of n for which you know the probability pn.
One initial condition presents itself immediately: p0 = 1.
It seems pretty clear that if he's 0 steps away from the cliff, he's
already fallen off and he's certain to die.
But a second initial condition eludes you. You don't know p1
, or p2, or p3...except in terms of other pn.
The light bulb moment this time is that you do know p∞:
if he's an infinite number of steps away from the cliff, he's sure to
survive, so p∞ = 0.
Now you have the two initial conditions you need to solve the
problem. Go plug 'em in.
p0 = 1 = c1⋅10 + c2⋅(1/2)0
= c1 + c2
p∞ = 0 = c1⋅1∞ + c2⋅(1/2)∞
= c1 + 0 = c1.
So, c1 = 0, and c2 = 1.
Plugging that in, you get:
pn = 0⋅1n + 1⋅(1/2)n
Our original problem was to see whether he eventually falls off from
one step away, and that's just p1 = 1/2 = 50%.
So, whaddaya know? That jerk was right after all! Lucky bastard.
Now, I know some of you are saying to yourselves (I did too):
"Hey! That's a random walk! He's walking randomly, so he's guaranteed
to eventually get there! Look, someone proved it and everything! What a
moron JavaBean is."
To those of you I say: Well, yes. The random walk (or drunkard's
walk), guarantees that a randomly walking person will, in an infinite
time span, eventually walk out of any finite area. But the area in this
puzzle is infinite, so it doesn't actually apply: he's got lots of
space behind him.
For the curious who don't like using infinity as a number, here's a
C program that estimates this value: with larger values of RECURSE_STEPS
the result gets closer and closer to .5.
/*Some C file*/
#define RECURSE_STEPS 30
double prob(int dist, int recursiveSteps);
printf("%f", prob(1, RECURSE_STEPS));
double prob(int dist, int recurseSteps)
if (dist <= 0)
if (recurseSteps <= 0)
return ((1.0 / 3.0) * prob(dist - 1, recurseSteps - 1))
+ ((2.0 / 3.0) * prob(dist + 1,
recurseSteps - 1));