Random walks

In one dimension, a random walk with t steps of length 1 starting at position 0 can be generated from

NestList[(# + (-1)^Random[Integer])&, 0, t]

or equivalently

FoldList[Plus, 0, Table[(-1)^Random[Integer], {t}]]

A generalization to d dimensions is then

FoldList[Plus, Table[0, {d}], Table[RotateLeft[PadLeft[{(-1)^Random[Integer]}, d], Random[Integer, d - 1]], {t}]]

A fundamental property of random walks is that after t steps the root mean square displacement from the starting position is proportional to √t. In general, the probability distribution for the displacement of a particle that executes a random walk is

With[{σ = 1}, (d/(2 π σ t))^d/2 Exp[-d r²/(2 σ t)]]

The same results are obtained, with a different value of σ, for other random microscopic rules, so long as the variance of the distribution of step lengths is bounded (as in the Central Limit Theorem).

As mentioned on page 1082, the frequency spectrum Abs[Fourier[list]]² for a 1D random walk goes like 1/ω².

The character of random walks changes somewhat in different numbers of dimensions. For example, in 1D and 2D, there is probability 1 that a particle will eventually return to its starting point. But in 3D, this probability (on a simple cubic lattice) drops to about 0.341, and in d dimensions the probability falls roughly like 1/(2d). After a large number of steps t, the number of distinct positions visited will be proportional to t, at least above 2 dimensions (in 2D, it is proportional to t/Log[t] and in 1D √t). Note that the outer boundaries of patterns like those on page 330 formed by n random walks tend to become rougher when t is much larger than Log[n].

To make a random walk on a lattice with k directions in two dimensions, one can set up

e = Table[{Cos[2 π s/k], Sin[2 π s/k]}, {s, 0, k - 1}]

then use

FoldList[Plus, {0, 0}, Table[e〚Random[Integer, {1, k}]〛, {t}]]

It turns out that on any regular lattice, in any number of dimensions, the average behavior of a random walk is always isotropic. As discussed in the note below, this can be viewed as a consequence of the fact that the probability distribution in a random walk depends only on

Sum[Outer[Times, e〚s〛, e〚s〛], {s, Length[e]}]

and not on products of more of the e〚s〛.

There are nevertheless some properties of random walks that are not isotropic. The picture below, for example, shows the so-called extreme value distribution of positions furthest from the origin reached after 10 steps and 100 steps by random walks on various lattices.

In the pictures in the main text, all particles start out at a particular position, and progressively spread out from there. But in general, one can consider sources that emit new particles every step, or absorbers and reflectors of particles. The average distribution of particles is given in general by the diffusion equation shown on page 163. The solutions to this equation are always smooth and continuous.

A physical example of an approximation to a random walk is the spreading of ink on blotting paper.