V.5.1 Introduction

Envision the following process: a person takes a step in a randomly chosen direction, then takes another step in a randomly chosen direction, and again takes another step in a randomly chosen direction, and so on until a total of n steps have been taken. The process is known as the random walk model and it has been extremely useful to scientists in many fields who are studying stochastic (probabilistic) processes: physicists modelling the transport of molecules, biologists modelling the locomotion of organisms and economists modelling the time behaviour of financial markets. The widespread use of the random walk model makes it a good jumping-off point for our explorations in the world of computer simulation.

V.5.2 Random Walk Programs

The One-Dimensional Random Walk

The simplest random walk model consists of steps of equal length, back-and-forth along a line. A step (or step increment) in the positive x-direction corresponds to a value of 1 and a step in the negative x-direction corresponds to a value of -1. A list of the successive step increments of an -step random walk in one dimension is therefore a list of randomly selected 1's and -1's. This list can be generated in many ways. We will use

OPTIONAL
V.5.2a Run StepIncrements for a large number of arguments, is the behaviour random?

A list generated with StepIncrements[n] can be used to generate a list of the ( + 1) locations of a one-dimensional -step walk which starts at the origin.

Using the right hand side (rhs) of the StepIncrements program in the FoldList function, we can write the program, called walk1D, to generate a list of the step locations of an -step random walk, originating at the origin,

A typical run of the Walk1D program is shown below for a value of n equal to 10.

OPTIONAL
V.5.2b Generate plots of 1D random walks. What would you expect? Is the behaviour random?

Next, we'll look at the random walk model in higher dimensions.

The Two-Dimensional Lattice Walk

The random walk model in higher dimensions is a bit more complicated then the random walk in one dimension. In  one dimension, each step of the walk is either 0 degrees (i.e., a forward step) or 180 degrees (i.e., a backward step) with respect to the preceding step. In higher dimensions, a step can take a range of orientations with respect to previous steps.

We will consider a random walk on a square lattice. This kind of walk is appropriately referred to as a lattice walk. Specifically, we will look at a lattice walk on the two-dimensional square lattice. This walk consists of steps of uniform length, randomly taken in the North, East, South or West direction. The list of the possible increments for a step in this walk is

A list of n step increments can be created from this, using

OPTIONAL
V.5.2c By analogy to the one-dimensional random walk computation, write a program, called Walk2D[n_], to generate a list of the step locations of an -step lattice walk which starts at the origin {0, 0}, using the generation of increments shown above.

A typical output of your Walk2D program should look like

OPTIONAL
V.5.2d Describe a procedure to show the correctness of your Walk2D[n_] program.

OPTIONAL
V.5.2e  Adapt Walk2D to DiagonalWalk2D for a walk starting from {0,0} and the walker only allowed to walk along the diagonals of the lattice.

V.5.3 Numerical Study of The Two-Dimensional Lattice Walk

Mean Shape of a Two-Dimensional Lattice Walk

In studying a process that is random in nature often  one is interested in its mean, or average, properties. To obtain the mean value of a quantity, the quantity is computed a number of times, the values that are obtained are summed, and the result is divided by the number of computations. It is instructive to examine two measures of the mean 'size' of a two-dimensional lattice walk:
[1] The mean-square end-to-end distance
[2] The mean-square radius of gyration.

These mean 'sizes' can be connected to real physical quantities. For instance, if you model the movement of molecules in a gas as a random walk, it is possible to calculate an important physical quantity, called the diffusion coefficient, by measuring the mean-square end-to-end distance.

Mean-Square End-To-End Distance

The square end-to-end distance, , of a two-dimensional lattice walk is given by where and are the initial and final locations of the walk, respectively. Choosing the origin {0, 0} as the starting point of the lattice walk, simplifies the formula to
The square end-to-end distance of a lattice walk starting at {0, 0} and ending at is given by

REQUIRED
V.5.3a Write a program, called SquareDistance[walk_List] using the above formula to compute for the two-dimensional lattice walk. The argument walk_List is the output of your Walk2D program. Show the correctness of your program. Hint: using Last allows you to select the last item on a list.

The SquareDistance of a random walk is a random variable. A -step random walk can be characterised by calculating its mean SquareDistance . A program, called MeanSquareDistance, for computing the mean-square end-to-end distance for -step lattice walks can be written very easily, using the Sum function

With a proper definition of Walk2D a typical result of the MeanSquareDistance program can be obtained by evaluating the following cell. In this case the program is called for 25 10-step walks.

REQUIRED
V.5.3b Study the behaviour of the MeanSquareDistance as a function of . How large should be in order to find reliable values of the MeanSquareDistance. (Hint: you can do this by plotting the MeanSquareDistance, or the variance of the SquareDistance, as a function of for certain values of ).

REQIRED
V.5.3c Find the MeanSquareDistance for the 2D lattice walk as a function of the length of the walk .

OPTIONAL
V.5.3d Carry out the same experiment for the diagonal lattice walk. Explain your results.

REQUIRED
V.5.3e For a molecule randomly moving in a fluid we can calculate the diffusion constant D by:
             ,
where indicates the mean-square end-to-end distance after t seconds on a lattice with dimensionality d. Simulate the system to get the diffusion constants in one and two dimensions.

V.5.4 Visualizing the Random Walk

Simple Graphics

We can create a snapshot of the path of the lattice walk using the graphics primitive Line, to draw lines between successive points in the walk.

Here we have set the value of the AspectRatio option to Automatic so that steps in the x and y directions have equal lengths. This option can be overwritten by specifying a different value in the list of options given by opts. Note the use of the triple blank in the definition of ShowWalk2D. The pattern opts___ matches any sequence (possibly empty) of rules which are used here to govern the display of the graphic by changing certain options to the Graphics function.

Here is a simple example of a two-dimensional lattice walk.

We can show a random walk of length 1000 using some additional options to change the color of the line segments as well as the background.

OPTIONAL
V.5.4a Make graphs of a number of 2-D random walks (also for different lengths) and relate the graphs to the mean square end-to-end distance of the random walks.

As the graphics indicate, a lattice walk repeatedly revisits sites that have been previously visited in the course of its meandering. As a result, it is difficult, and usually impossible, to discern the history of the walk from a snapshot of the path. The best way to see the entire evolution process of the walk in an unobscured fashion is to create  animation.

Animation

We will create animation using an eight-step two-dimensional lattice walk.

Creating animation in Mathematica is straightforward. The animation consists of a sequence of graphics cells where the first cell shows the first step (consisting of a line drawn between the first two elements in w8 for example) and each succeeding cell shows one more step than the previous cell. In general then, the mth cell is drawn using the Line function and the first m + 1 elements in w8. All of the graphics cells are drawn using

In general, objects in a graphics cell are scaled to fill the monitor screen. Therefore, if we simply create cells, each containing a different number of steps of the walk using the above graphics command, steps in one cell will appear to be of a different length then the same steps in other cells. This will result in a jerky-looking animation.

We can use the PlotRange option to make all of the step lengths in all of the graphics cells uniform. The ordered pair of the minimum and maximum values of the components of the random walk in each direction, can be determined by separating the - and -components of the walk using Transpose and then mapping an anonymous function containing Min and Max onto it.

Here then is the command for creating the animation using PlotRange to control the size of each cell produced. In addition, we have added a red ball that moves to the current position in the walk. This is helpful when visualizing the animation as oftentimes the walk crosses back upon itself. It is not difficult to change this ``marker'' to any shape or color.

Note: We have added .2 to the maximum x and y values and subtracted .2 from the minimum x and y values in order to enhance the display by making the graphics a little smaller inside its bounding box.

The easiest way to see all of the cells of the animation simultaneously is to take the animation as an argument of the GraphicsArray function, using Partition to specify the number of cells in each line of the resulting graphics. Note the use of DisplayFunction to turn off the display of each graphic to the screen --- GraphicsArray automatically overrides this value and so this construction only shows the entire array.

When the animation is run, the red ball can be seen moving around the screen landing on each successive step of the walk. This is especially striking when run on walks of length 100 or 1000.

OPTIONAL
V.5.4b Animate the 2D diagonal lattice walk.

OPTIONAL
V.5.4c Animate the 2D lattice walk and at the same time plot (e.g. as a circle) the mean-square end-to-end distance. Conclusion?

Visualizing the Three-Dimensional Lattice Walk

OPTIONAL
V.5.4d Modify the function 'showRandomWalk3D' given in this section by coloring each step according to its total length.