Does a random walker always come home?

Question

A random walker starts at the origin and takes unit steps forever, each step in a direction chosen uniformly at random from the available directions.

On a line (two directions), is the walker certain to return to the origin eventually?
On a square grid in the plane (four directions)?
In a cubic lattice in three dimensions (six directions)?

Give the answers and the idea behind them; the exact return probability in three dimensions is not required, but say roughly what it is.

Accepted Answer

On a line and in the plane the walker returns with certainty. In three dimensions there is only about a 34 per cent chance of ever returning. The criterion. Let p(2n) be the probability that the walker is back at the origin after 2n steps. If the sum of p(2n) over all n is infinite, the walker returns infinitely often with probability 1; if the sum is finite, there is a positive chance of never returning. (The link: the expected number of visits is that sum, and a walker that returns with certainty keeps returning forever, making the expected number of visits infinite.) One dimension. Being h…

Does a random walker always come home?

Your answer

Discussion

Learn the concepts

Related questions