Random walk on a grid, do you ever get home?

Question

A walker starts at the origin of an infinite 2D grid. Each step it moves one block north, south, east, or west, each with probability $1/4$ , and it walks forever.

What is the probability the walker eventually returns to its starting point?

Accepted Answer

This is Polya's classic recurrence question. In one and two dimensions a symmetric lattice walk is recurrent: it returns to its starting point with probability exactly 1, and because of that it actually returns infinitely often. The rough reason is that in low dimensions there is simply not enough room to escape to infinity; the walk keeps drifting back across the origin. So on the 2D grid, P(	ext{eventual return}) = 1. The picture changes in three dimensions, where there is enough room to wander off for good and the return probability drops below 1. Takeaway. Symmetric random walks are recu…

Random walk on a grid, do you ever get home?

Your answer

Discussion

Learn the concepts

Related questions