Three 2-dimensional random walks. All three start at the black circle and finish, after 100 steps, at a coloured square. Later steps are in darker colours. Considerable backtracking occurs.
We have discussed one-dimensional random walks, but it is possible to have random walks in more than one dimension. In two dimensions (above), we can go left, right, forward, and back. A random walk in two dimensions can be played as a kind of game (as can one-dimensional random walks). In three dimensions (below) we can also move vertically. Three-dimensional random walks are related to the motion of molecules in a gas or liquid.
Three 3-dimensional random walks. All three start at the black circle (in the centre of the cube) and finish, after 100 steps, at a coloured square. Later steps are in darker colours.
One very interesting question is whether a random walk ever returns to its starting point. In one dimension, the probability of returning in exactly n ≥ 1 steps is 0 if n is odd, and C(n, n/2) / 2n if n is even, where C(n, k) is the number of ways of choosing k items out of n, which is defined by C(n, k) = n! / (k! (n−k)!).
For large numbers n, Stirling’s approximation says that n! is approximately sqrt(2πn)(n/e)n. If we let m = n/2, some tedious algebra gives the probability of returning in exactly n = 2m steps as 1/sqrt(πm) ≈ 0.56/sqrt(m). When I ran some experiments I actually got a factor of 0.55, which is pretty close. Given infinite time, the expected number of times we return to the starting point is then:
0.56 (1 + 1/sqrt(2) + 1/sqrt(3) + 1/sqrt(4) + …) = ∞
This means that an eventual return to the starting point is certain. It may take a while, however – in 100 random walks, summarised in the histogram below, I once had to wait for 11452 steps for a return to the starting point.
Random walks in two dimensions can be understood as two random walks in one dimension happening simultaneously. We return in exactly n = 2m steps if both one-dimensional walks return together. The probability is therefore the one above squared, i.e. 1/(πm) ≈ 0.318/m. Again, given infinite time, the expected number of times we return to the starting point is:
0.318 (1 + 1/2 + 1/3 + 1/4 + …) = ∞
This means that a return to the starting point is also theoretically certain, although it will take much, much longer than for the one-dimensional case. In a simple experiment, four random walks returned to the starting point in 6814, 2, 21876, and 38 steps respectively, but the fifth attempt took so long that I gave up. In three or more dimensions, a return to the starting point might never occur.
Scientific Gems 