The Drunkard and the Bird

The problem
random walk on a latticeorigindoes the walker eventually return to start?

A walker stands at the origin of an infinite lattice. Every second, they take one step in a uniformly random direction along the lattice axes.

  • 1D: left or right.
  • 2D: up, down, left, or right.
  • 3D: six choices (add forward, back).

Does the walker eventually return to the origin? Does the answer depend on dimension?

Tempting (but wrong)
"randomness eventually returns"true in 1D, 2D — false in 3D

"Randomness eventually returns." Given infinite time, every lattice point gets visited, so the walker must come home. Either dimension shouldn't matter, or higher dimensions should help (more directions to wander, more directions back).

This is right in 1D and 2D, and dramatically wrong in 3D.