Jorge 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, 2 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 Jorge will eventually return to 0?

Note: For purposes of the problem, assume that Jorge is not looking while he is merely passing through a point. For example, he will not look for his keys while he passes through 0.

(In reply to huh? by Steve Herman)

You're correct of course.  The fact that a jump of 3 consists of a 2 and a 1 makes each pass through the origin more likely to hit the origin than I allowed, that is, more than 1/3. As you say, it still makes the probability of eventual return 100%, just sooner.

You've also discovered a bug in my simulation program.  The line:

     x = x + mv * 2 * mv * (INT(RND(1) * 2) - .5)

has mv, which is the absolute value of the size of the current move, as a factor twice, turning a 2 into a 4. One of the "mv *"'s should be removed. The alternating 1's and 4's, rather than 1's and 2's, is what makes the smallest return to the origin 4 steps.  I'll later post a corrected version. Right now I'll post a warning on my first comment.

Thanks for keeping me honest.

Posted by Charlie on 2009-01-18 13:06:45