Solution to the Drunk Guy on a Cliff Puzzle (idea)

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 p_n in terms of p_n-1, p_n-2, and so on. So we shift our definition to the right by one unit of n, and solve for p_n:

Let k = n - 1.
Then, p_k-1 = (1/3)⋅p_k-2 + (2/3)⋅p_k
Therefore p_k=(3/2)⋅p_k-1 - (1/2)⋅p_k-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 recurrence relation:

x² - (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:

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

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: two values of n for which you know the probability p_n.
One initial condition presents itself immediately: p₀ = 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 p₁ , or p₂, or p₃...except in terms of other p_n. 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.

p₀ = 1 = c₁⋅1⁰ + c₂⋅(1/2)⁰ = c₁ + c₂
p_∞ = 0 = c₁⋅1^∞ + c₂⋅(1/2)^∞ = c₁ + 0 = c₁.

So, c₁ = 0, and c₂ = 1.
Plugging that in, you get:
p_n = 0⋅1ⁿ + 1⋅(1/2)ⁿ = (1/2)ⁿ.

Our original problem was to see whether he eventually falls off from one step away, and that's just p₁ = 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*/

#include <stdio.h>

#define RECURSE_STEPS 30

double prob(int dist, int recursiveSteps);

int main()
{
   printf("%f", prob(1, RECURSE_STEPS));
}

double prob(int dist, int recurseSteps)
{
   if (dist <= 0)
      return 1;
   if (recurseSteps <= 0)
      return 0;

   return ((1.0 / 3.0) * prob(dist - 1, recurseSteps - 1))
      + ((2.0 / 3.0) * prob(dist + 1, recurseSteps - 1));
}