Waldo has lost his car keys!

probability/random.walk

Problem

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?

Show solution

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.