# 418 probability/random.walk.p

## Description

This article is from the Puzzles FAQ,
by Chris Cole chris@questrel.questrel.com and Matthew Daly
mwdaly@pobox.com with numerous contributions by others.

# 418 probability/random.walk.p

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?

probability/random.walk.s

I can show the probability that Waldo returns to 0 is 1. Waldo's

wanderings map to an integer grid in the plane as follows. Let

(X_t,Y_t) be the cumulative sums of the length 1 and length 2 steps

respectively taken by Waldo through time t. By looking only at even t,

we get the ordinary random walk in the plane, which returns to the

origin (0,0) with probability 1. In fact, landing at (2n, n) for any n

will land Waldo on top of his keys too. There's no need to look at odd

t.

Similar considerations apply for step sizes of arbitrary (fixed) size.

Continue to: