Drunk Guy on a Cliff Puzzle

A lovely puzzle to delight casual
mathematicians, this puzzle is particularly prominent in
university circles.

The setup goes like this:

- We have a sheer cliff.

- Standing on the edge of said cliff
is a man.

- He is no ordinary man. He is
holding an infinitely large container of vodka and, needless to say,
he is staggeringly drunk. And, holding his infinite vodka bottle, he
will be drunk for an infinite amount of time. Or, as
mathematicians prefer to say, he will be drunk arbitrarily
long.

- He is staggering drunkenly
back and forth, perpendicular to the cliff edge. So, a single step
forward from his present location at the edge will send him hurtling
into the abyss, and a step backward will bring him closer to safety.

Now, given all of these things, we
say that the chance of him staggering forward (on any given step, or
any given minute, etc. - it really doesnâ€™t matter) is one third,
and the chance of him staggering backward is two thirds. The question
this puzzle poses is:

What is the chance he will
*eventually* fall
off of the cliff?

Your first stab at an answer is likely to be: one third. But
you answered that without thinking, so you can be forgiven.
He might stagger backwards once and then forwards twice. He'd still
die, after all. So your answer has to include the possibility of
staggering backwards 10,000,000 times and then staggering
forwards
the same number of times. Pretty slim chance, but hey, it could
happen.

So, you've got an infinite amount of time, a sheer cliff, and an
infinite number of possible ways to fall off it. What could go wrong?
You need to figure out some concise answer to this problem, or it will
haunt you for the rest of your days. Of course, when I first heard
this problem, some flippant guy in the room said, Well, it's
50-50. Either he falls or he doesn't. Duh.

What a jerk, huh?

Anyway, the answer to this problem is left as the proverbial
exercise for the reader. (Hint: If you've never heard of a
recurrence relation, don't bother.)

Or, if you're impatient or just prefer cheating, you can check out
the Solution to the Drunk Guy on a Cliff Puzzle.