Usenet Newsgroups : rec.puzzles Hall of FameThe rec.puzzles Hall of Fame is a compilation of over 500 of the most popular puzzles that have been posted and discussed in the rec.puzzles newsgroup. In most cases a detailed solution has been provided. Many of these puzzles also appear in Braingle's own collection. 

Waldo has lost his car keys! He's not using a very efficient search; in fact, he's doing a random walk. He starts at 0, and moves 1 unit to the left or right, with equal probability. On the next step, he moves 2 units to the left or right, again with equal probability. For subsequent turns he follows the pattern 1, 2, 1, etc. His keys, in truth, were right under his nose at point 0. Assuming that he'll spot them the next time he sees them, what is the probability that poor Waldo will eventually return to 0?
Solution