The 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.