*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) / 2^{n} 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* = 2*m* 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* = 2*m* 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.

### Like this:

Like Loading...