The Random Walk

by
Richard J. Gaylord
Deparment of Materials Science and Engineering
University of Illinois at Champaign Urbana
Urbana, IL 61801
gaylord@ux1.cso.uiuc.edu

and 

Paul R. Wellin
Department of Mathematics 
Sonoma State University
Rohnert Park, CA 94928
wellin@telospub.com

Mathematica in Education
Vol.3 No.3
Summer 1994
(c) TELOS/Springer-Verlag

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 then 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 (probabilisitc) processes: physicists modelling the transport of molecules, biologists modelling the locomotion of organisms and economists modelling the time behavior 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.

Random Walk Programs

The One-Dimensional Random Walk

The simplest random walk model consists of n 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 n-step random walk in one dimension is therefore a list of n randomly selected 1's and -1's. This list can be generated in many ways. We will use

Table[(-1)^Random[Integer], {n}]

Using this Table, we can write a program, called stepIncrements, which generates a sequence of n step increments

stepIncrements[n_] := Table[(-1)^Random[Integer], {n}]

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

stepIncrementss[10]

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

FoldList[Plus, 0, stepIncrements[n]]

For example, using the result just obtained

FoldList[Plus, 0, %]

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 n-step random walk, originating at the origin,

Walk1D[n_] :=  FoldList[Plus, 0, Table[(-1)^Random[Integer], {n}]]

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

Walk1D[10]

Note: A list of the step locations can also be generated, albeit a bit more slowly, without creating a list of the step increments, using the nesting operation

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

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 backwards step) with respect to the preceding step. In higher dimensions,  a step can take a range of orientations with respect to previous steps.

We'll consider a random walk on a lattice. This kind of walk is appropriately referred to as a lattice walk. Specifically, we'll 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

{{0,1},{1,0},{0,-1},{-1,0}}[[Table[Random[Integer, {1, 4}], {n}] ]]

By analogy to the one-dimensional walk computation, a program, called walk2D, to generate a list of the step locations of an n-step lattice walk which starts at the origin {0, 0} is given by

Walk2D[n_] := 
  FoldList[Plus, 
 {0, 0}, 
{{0,1},{1,0},{0,-1},{-1,0}}[[Table[Random[Integer, {1, 4}], {n}]]]]

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

Walk2D[10]

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, we are often 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. We'll look at two measures of the mean 'size' of a two-dimensional lattice walk: the mean-square, end-to-end distance and the mean-square radius of gyration.

Mean-Square, End-To-End Distance

The square end-to-end distance, r2,  of a two-dimensional lattice walk is given by 
(xf - xi)2 + (yf - yi)2 where {xi, yi} and {xf, yf}  are the initial and final locations of the walk, repectively. Choosing the origin {0, 0} as the starting point of the lattice walk, simplifies the formula to (xf2 + yf2).
The square end-to-end distance of a lattice walk  starting at {0, 0} and ending at {xf, yf}  is given by

Apply[Plus, {xf, yf}^2]

We can write a program, called SquareDistance, using the above formula  to compute r2 for the two-dimensional lattice walk

SquareDistance[walk_List] := Apply[Plus, Last[walk]^2]

A typical run of the squareDistance program is shown below for a ten-step walk.

SquareDistance[ walk2D[10] ]

A program, called MeanSquareDistance, for computing the mean-square, end-to-end distance for m n-step lattice walks can be written very easily, using the Sum function

MeanSquareDistance[n_Integer, m_Integer] := 
	Module[{walk2D},
	walk2D[s_] := FoldList[Plus, {0, 0}, 
{{0,1},{1,0},{0,-1},{-1,0}}[[Table[Random[Integer,{1,4}],{s}]]]]; 
	N[Sum[Apply[Plus, Last[walk2D[n]]^2], {m}]/m]
	]

A typical run of the MeanSquareDistance program is shown below for 25 10-step walks.

MeanSquareDistance[10, 25]

Mean-Square, Radius of Gyration

The mean square radius of gyration, <Rg2>, of a random walk is the sum of the squares of the distances of the step locations from the center of mass divided by the number of step locations, where the center of mass is the sum of the step locations divided by the number of step locations.  

The computations of the center of mass and the sum of the squares of step distances from the center of mass, are relatively straightforward. 

For the list of the (n + 1)  locations of an n-step walk, which we'll call locs, the center of mass, which we'll call cm, is given by

cm = N[Apply[Plus, locs]/(n + 1)]

The list,
{{(x0 - xcm)2, (x1 - xcm)2,..,  (xn - xcm)2}, {(y0 - ycm)2, (y1 - ycm)2,..,  (yn - ycm)2}} where xj, xcm, yj, and ycm  are the x- and y-components of the jth step location and the center of mass is given by

(Transpose[locs] - cm)^2

and so, the sum of the squares of distances of the step locations from the center of mass is given by

Apply[Plus,  Flatten[(Transpose[locs] - cm)^2]]

The overall program for the mean-square-radius of gyration, called MeanSquareRadiusGyration, is written using the above quantities and following the form used for the MeanSquareDistance program

MeanSquareRadiusGyration[m_Integer, n_Integer] := 
  Module[{squareRadiusGyration},
      squareRadiusGyration[s_Integer] := 
         Module[{locs, cm, choices = {{1,0},{-1,0},{0,1},{0,-1}}},
          locs = FoldList[Plus,{0,0}, 
             choices[[Table[ Random[Integer,{1,4}],{s}]]]];
          cm = N[Apply[Plus, locs]/(s+1)];
          Apply[Plus, Flatten[(Transpose[locs] - cm)^2]]/(s+1)
                    ];
      N[Sum[squareRadiusGyration[n], {m}]/m]
              ]

A typical run of the meanSquareRadiusGyration program is shown below for 25 10-step walks.

MeanSquareRadiusGyration[10, 25]

The Critical Exponent of a Random Walk

It has been found experimentally (in the laboratory) and theoretically (on paper) that both <r2> and <Rg2> have a power law dependence on the number of steps in the walk, n. The power, v, in the relationship <r2> = nv is known as the critical exponent of the walk. We can determine the value of the critical exponent computationally (with a computer).

The computation of the critical exponent can be illustrated with a specific example.

We'll first create a data set of the computed values of the ordered pairs {<r2>, n} for values of n from 10 to 90 in increments of 20,  with m equal to 75 being used to compute <r2>.

data =
 Map[({meanSquareDistance[#,75],#})&,Range[10,90,20]]

Taking the Log of the powerLaw list (which is equivalent to creating the list  of ordered pairs, {Log[<r2>], Log[n]}, and using it in the Fit function

calculatedExponent = Fit[N[Log[data]], {x}, x]

For a power law relationship of the form <r2> = nv , Log[<r2>] = v Log[n] and so, the coefficient  of x in calculatedExponent is the critical exponent, which has a value of approximately one. 

When we used {x} in the Fit function, we assumed, rather than proved, a power law dependence of  <r2> on n. To check  how good this assumption is, we can look at plots of the computed power law relationship and the data set together.

A plot of the computed power law relationship is created using

calculatedGraph = Plot[calculatedExponent, {x, 0, 90}]

A log-log plot of the data is created using the LogLogListPlot function defined in the Mathematica Graphics package. We first load the package using

Needs["Graphics`Graphics`"]

and then use

dataGraph = LogLogListPlot[data,
		PlotStyle -> PointSize[.03] ]

The plots of the computed power law relationship and the data set can now be shown together

Show[dataGraph, calculatedGraph]

Visualizing the Two-Dimensional Lattice 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.

ShowWalk2D[coords_, opts___]:=
	Show[Graphics[Line[coords],
		AspectRatio -> Automatic,
		opts]]

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 are a simple example of a two-dimensional lattice walk.

ShowWalk2D[ walk2D[10] ]

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.

showWalk2D[ walk2D[10^3],
	DefaultColor -> Hue[.75],
	Background -> GrayLevel[0] ]

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 an animation.

Animation

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

w8 = Walk2D[8]

Creating an 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

Map[(Show[Graphics[Line[Take[w8, #]]]])&, 
	Range[2, Length[w8] ]]

Show[Graphics[GraphicsArray[Partition[%,4]]]]

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, {{xmin, xmax}, {ymin, ymax}} can be determined by separating the x- and y-components of the walk using Transpose and then mapping an anonymous function containing Min and Max onto it.

Map[{Min[#],Max[#]}&, Transpose[ w8 ]]

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.

AnimateWalk2D[coords_, opts___]:=
	Map[Show[Graphics[{
		{RGBColor[1,0,0],PointSize[.05],
		 Point[ coords[[#]] ]},
		Line[Take[coords, #]]}],
	 AspectRatio -> Automatic,
	 PlotRange -> Map[{Min[#]-.2, Max[#]+.2}&,
		             Transpose[coords]],
	 opts]&, Range[2, Length[coords]]]

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.

Show[GraphicsArray[Partition[
          animateWalk2D[Walk2D[10],
               DisplayFunction -> Identity], 5]
	]];

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.

AnimateWalk2D[ Walk2D[100] ]

Computer Simulation Projects

1. Two related quantities of interest in the random walk model are the mean number of distinct sites visited during a lattice walk (the number of sites that are visited at least one time) and the mean occupany of a site (the mean number of times each site is visited). Determine the power law dependence of these quantities on the number of steps for the two-dimensional lattice walk.

2. Write a program for computing the step locations of a 3-dimensional walk on a cubic lattice. Create an animation of a ten-step cubic lattice walk.

3. The  off-lattice walk in two dimensions consists of n steps of equal lengths, each step being randomly oriented with respect to preceding steps. In this model, the x- and y-components of each step increment are not independent because each step must have length one. This constraint can be satisfied by first randomly selecting an orientation angle, between 0 and 360 degrees, for each step, called theta, with Random[Real, {0, N[2 Pi]}] and then calculating the ordered pair of  the x- and y-components of the step, with {Cos[theta], Sin[theta]}. A list of the step increments in the off-lattice, n-step walk is given by first generating a list of theta values and then mapping the anonymous function {Cos[#],Sin[#]}& onto the list. A program for doing this is given by

OffLatticeWalk[n_] := 
  FoldList[Plus, {0.0 , 0.0}, 
  	Map[{Cos[#],Sin[#]}&, 
  		Table[Random[Real,{0, N[2Pi]}],{n}]]]

Write a program for the step locations of an off-lattice walk in three dimensions.

General References

Weiss, George H. 1983. Random Walks and Their Applications, American Scientist, 71(1), pp. 65-71 .