Always home on a plane, and one time in three in space
A walker stands on the crossing of a grid and takes a step to a neighbouring crossing, in a direction chosen at random, and then another, for ever. Will it ever stand where it started again? On a line, certainly. On a flat grid, certainly — though after 4,000 steps — of walkers on a plane still have not. In a grid of three dimensions, where every crossing has six neighbours instead of four, it comes back — of the time, and the other two walkers in three never do.
One walk
Four thousand steps, drawn from where the walker starts, which is ringed. On a plane and in space every visit home is to that one crossing, so how many there were is written above the figure. On a line, time runs across the figure and the walker’s place runs up it, so every visit home is a dot on the middle line. In space the walk is drawn as a cube is, seen from one corner.
Home by step n
The chance that the walker has been home at least once by a given step, worked out exactly rather than by walking. The steps run across on a scale where each mark is ten times the last, because on a plane nothing much happens in any fixed stretch of steps: each tenfold brings a few more walkers home, and it never stops doing so.
Why it is all or nothing
Each time the walker stands at home it is exactly where it was at the start, with the same chance of ever coming back as it had then — call that chance p. So it comes back at least once with chance p, at least twice with p², and the visits stop the first time the chance fails. The average number of times it stands at home, counting the start, is then 1 ⁄ (1 − p).
That average can be counted a second way, one step at a time: it is the chance of being home at step 2, plus the chance at step 4, plus the chance at step 6, and so on, plus one for the start. If that sum never stops growing, 1 ⁄ (1 − p) is infinite, and p is exactly one. Whether the walker must come home is only the question of whether that sum is finite.
At step 2n the chance of being home falls like 1 ⁄ √n on a line, like 1 ⁄ n on a plane and like 1 ⁄ n3/2 in space. The first two sums grow for ever — on a plane, by about ln 10 ⁄ π = — of a visit for every tenfold of steps, which is why it is so slow. The third does not.
More room, fewer returns
Nothing about three is special except that it is the first dimension where the sum stops. Every dimension after it has more ways to leave and the same one way home, and the chance of ever returning falls towards the chance of simply stepping straight back on the second step, which is one in the number of neighbours.
How the numbers are got
Nothing on this page is simulated except the walk at the top and one check below. The chance of being home at step 2n is exact: on a line it is the number of ways to take n steps each way, over 22n; on a plane it is the square of that, because a walk on a grid seen along its diagonals is two walks on lines at once; in space it comes from a three-term recurrence for the number of closed walks, checked below against summing every way of sharing the steps among the three axes. The chance of being home for the first time at each step comes from those by taking away every earlier first return followed by a return.
The limits — the 34.05% and the table for more dimensions — come from a different place: the expected number of visits home in d dimensions is also d times the integral of (e−x I₀(x))d over x from zero to infinity, where I₀ is a Bessel function. The page does that integral numerically, and checks it against the step-by-step sum with an allowance for what the sum has not reached yet.