Mathematics in action: returning from a random walk


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(nn/2) / 2n if n is even, where C(nk) is the number of ways of choosing k items out of n, which is defined by C(nk) = n! / (k! (nk)!).

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.


Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s