The random walk

A random walk is a path made of steps, each taken in a direction chosen by chance. The English mathematician Karl Pearson gave it its name in a letter to Nature in 1905, "The Problem of the Random Walk".^1, 2, 3

Pearson's problem

Pearson described a walker who starts at a point, walks a fixed distance of l yards in a straight line in a random direction, turns, walks another l yards in another random direction, and goes on like this n times. He wanted a formula for the probability that, after those n steps, the walker ends up at a distance r from the start. He had solved only the case of two steps.¹

The rule is the whole method: a starting point, a step length, and a source of random directions. In a computer the random directions come from a pseudo-random number generator, such as the linear congruential generator.

How far does it get?

Not very far, and not in any one direction. The steps cancel each other out much of the time. On average the distance from the start grows like the square root of the number of steps: after 100 steps a walker is typically of the order of 10 step lengths away, after 10,000 steps of the order of 100.³ So a long walk spends most of its time near where it started and crosses its own path again and again, which is why a drawn walk looks like tangled knots joined by a few long runs.

New drawing

In art

Random walks were among Manfred Mohr's first programs. His own list of his work begins in 1969 with "P-10 Random Walk drawings with alternating horizontal and vertical lines" and "P-16 - P-18 Random Walk drawings with horizontal and vertical lines". He ran P-18 on a high-resolution light-beam plotter at Brookhaven National Laboratory.⁴

The walk is also a working part inside other methods. In diffusion-limited aggregation thousands of particles take random walks until they touch a growing cluster, and the branching form comes entirely from where those walks tend to end. See also Generative Art.