Random Walks

←Previous

Simple random walks

In the previous section we presented an example for a stochastic problem, namely the diffusion of a drop of milk in a cup of tea. We argued that on a microscopical level, individual "milk particles" would, for some time, move on a straight line with constant velocity, before a collision with another milk or tea particle would change their trajectory, altering mainly direction and possibly speed. Such a trajectory can be modelled by something known as random walk. In such a walk, the particle moves one step with fixed length at a time, in a random direction, according to certain rules (see later). Here the walker's steps correspond to the milk particle's movement along a straight trajectory between two collisions. Each walker, similar to the milk particles, thus zigzag's around.

The simplest walker to be implemented involves a walker that is able to take steps of unit length along a straight line, in one dimension. After each time interval (or step) it will decide, at random, whether the next step carries it to the left or the right, with equal probability. This is realised with a (pseudo-) random number generator. It is a routine that picks, seemingly at random, real numbers between 0 and 1, with a uniform probability density. Typically, involved mathematical routines underly such a generator, and typically the last number(s) generated will act as seed for the generation of the next one. In this respect, random number generators are deterministic: Fixing their initial state fixes the sequence of numbers. Therefore, the repetition rate, the emergence of patterns etc., are properties of a random number generator characterising its quality. However, without going into more detail let us assume here that we have perfect random numbers delivered by the corresponding routine. Then the pseudo-code for the one-dimensional random walker looks like:

Main program
  • Initialise the program.
  • Loop over the desired number of walkers m, each with the predefined number of steps imax.
  • Normalise the squared displacements to get the mean squared displacement averaged over all walkers. Plot the time evolution.
Initialisation
  • Initialise the random number generator
  • Initialise the list of squared displacements x²i from the starting position at each step i.
Loop
Loop over the walkers: j=1, 2, ..., m
  • Start each walker j at x1(j)=0. You do not have to keep track of the position of the walkers after each step, just add x²i(j) to the accumulated squared displacement x²i.
  • Loop through the number of steps i=1, 2, ..., imax for each walker.
    • At each step, draw a random number r between 0 and 1.
    • If r<0.5, then update xi(j) → xi+1(j)=xi(j)+1, otherwise xi(j) → xi+1(j)=xi(j)-1.
    • Accumulate the squared displacement: x²i = x²i + x²i(j).

Several quantitative results can be obtained from this simulation. Perhaps the most basic one is the mean displacement as a function of the number of steps. Since a walker is as likely to turn left as right, it is quite clear that this average, <xi>, must be zero. Here and in the following we adopt the notation that the brackets < X > denote the average (or expectation value) of a quantity X. This typically involves many measurements or similar of the same kind, to form a statistically meaningful average. A more interesting quantity is <x²i>. The results shown below motivate to assume that this can be described by a straight line in time (the number of steps),

\[ \langle x^2 (t) \rangle \,=\, 2Dt \, . \]
Here, for simplicity, we assume that each step can be identified with a unit in time. Results for a simple code with 1000 random walkers, each walking 100 steps, are depicted here:

Example results for a 1d random walk

The lower plot shows the squared average distance, simple inspection shows that it scales linearly with time, and therefore the average distance behaves like

\[ \langle x(t) \rangle \,\sim\, \sqrt{t}\, .\]
It is useful to compare this with a free particle: The distance it travels with constant velocity grows linearly with time. Therefore, a random walker escapes its starting position much slower than a free particle. This is also true for diffusive motion - in fact, as indicated before, random walks describe diffusion. This will be discussed later in even more detail, here it should suffice to announce that in the example of the drop of milk in a cup of tea, perfect mixing is roughly achieved when √(< x² >) is approximately the size of the cup.

Before discussing this, let us consider the value of the diffusion constant, D, introduced in the equation above. According to the plot, the value of the slope of < x² > is about 1, leading to D = ½. This result can also be obtained analytically:
Writing the position of a walker after n steps, xn, as a sum of the separate steps yields

\[ x_n\,=\, \sum_{i=1}^n s_i \,\, ,\]
where si=±1 with equal probability. For the squared displacement therefore:
\[ x_n^2\,=\, \sum_{i=1}^n \left( \sum_{j=1}^n s_i s_j \right)\, . \]
Since the steps are independent of each other, all products with i≠j will yield ±1 with equal probability and all products with i=j will yield 1. Therefore, averaging over a large number of separate walks translates into averaging out the i≠j terms and retaining only the i=j contributions. Therefore
\[ \langle x_n^2 \rangle \,=\, \sum_{i=1}^n s_i^2 \,=\, \sum_{i=1}^n 1 \,=\, n\, . \]
Since n is also identical to time (due to the unit size of the time step), we see that D = ½, as advertised.

Let us finally try to understand how the squared displacements of different walkers fluctuate, i.e. how the differences between two walkers such as the ones on the top half of the plot above evolve with time. Naively, one would assume that these fluctuations decrease with n, i.e. that differences "average out". this is however not the case, as we will see now. In order to calculate the fluctuations of x²n with respect to its mean we need to evaluate

\[ \sqrt{\langle (x_n^2\,-\, \langle x_n^2 \rangle )^2 \rangle}\,=\, \sqrt{\langle x_n^4 \rangle \,-\, \langle x_n^2 \rangle ^2}\,\, , \]
i.e. the expectation value of the quartic displacement. From the reasoning above we have
\[\begin{eqnarray*} \langle x_n^4\rangle\,&=&\,\sum_{i,j,k,l=1}^n\langle s_i s_j s_k s_l \rangle \\ &=&\, \sum_{i=1}^n s_i^4+3\sum_{i=1}^n s_i^2 \left[ \sum_{j\neq i}^n s_j^2 \right] \,=\, n\,+\,3n(n-1)\,=\,3n^2-2n\,\, . \end{eqnarray*} \]
Therefore, the root-mean-square fluctuation is given by
\[ \sqrt{\langle x_n^4 \rangle - \langle x_n^2 \rangle ^2}\,=\, \sqrt{2n^2-2n} \sim \sqrt{2}n\,=\, \sqrt{2} \langle x_n^2 \rangle \]
for large n. It is thus itself proportional to the mean of the square displacement and increases with n. Interpreting this implies that no single random walk behaves like the average random walk, independent of n!
There are many ways to make such random walks more realistic, for instance by leaving the step size open and choose it at random between -1 and 1 rather than fixing the step size and choosing the direction at random. In such a case, again diffusive behaviour emerges, albeit with a different diffusion constant. Another generalisation is to make the walker move in more dimensions, again leading to diffusive behaviour. Random walks in more than one dimension will be treated later on.

Next→




Frank Krauss and Daniel Maitre
Last modified: Tue Oct 3 14:43:58 BST 2017