<< Click to Display Table of Contents >>
## Random walks |

In 1888 the Reverend John Venn (of Venn diagram fame) discussed the randomness of the sequential decimal digits of Pi. He used a graphical aid to illustrate the randomness of the digits, which involved selecting the digits 0,1...7 from Pi. He then used these to provide an 8-point compass selection which generated a random walk in the plane (essentially a random walk on a lattice). An 200-step example of this type of random walk, commencing at 0,0 is shown below:

Venn 8-direction random lattice walk

More commonly now, 4-point or square lattices are studied, and the diagram below illustrates a 4-point random walk on a lattice of 10,000 steps, starting at 0,0 and finishing at -7,-3 (MATLab code by John Burkardt, Virginia Tech). Note that this walk is not self-avoiding, i.e. it repeatedly crosses itself and reversal of steps is permitted.

Random walk on a rectangular lattice

A few years after Venn's publication Karl Pearson posed the following question in the 1905 issue of "Nature" [PEA1], which is the first known mention of the term random walk:

A man starts from a point O and walks L yards in a straight line; he then turns through any angle whatever and walks another L yards in a second straight line. He repeats this process n times. I require the probability that after these n stretches he is at a distance between r and r + dr from his starting point, O.

Note that in this case, the range of directions is not constrained to a lattice, but the step length is still assumed to be constant. In this instance the average or expected distance from the starting point, for large n, is E(r)=0, i.e. the walk will tend to end up at its starting point. The probability distribution for a finite number of n steps is not known. Curiously enough, this result holds, broadly, for random walks on complex networks, such as a highly connected street network in a city.

This question is an example of one of a large number of similar random walk problems. In this case there is no restriction on the angular variation at each stage, and each straight-line segment is the same length. This inevitably produces a self-crossing walk, as opposed to a self-avoiding walk (SAW). Other characteristics of this walk is that it is continuous, embedded in a two-dimensional plane (walks in one dimension and higher dimensions and walks restricted to lattices, graphs or trees form another set of problems of this type), and it is implied that the walk is at a constant rate with finite step lengths. Variations in all these elements provides a rich set of possibilities, with an equally diverse range of applications.

Brownian motion, which is the apparently random movement of very small particles suspended in a liquid, is a form of random walk. Typically it is modeled as a continuous random walk in 2D (1D and 3D variants are also studied), commencing at fixed location, e.g. 0,0 and developing as the path of independent samples from a common cumulative bivariate Normal distribution (this version is formally a Weiner process). In this way the direction and length of steps in the path are determined, variable and entirely independent. Strictly speaking the steps are not assumed to be constant in time, but are modeled as such for convenience. An example simulation of Brownian motion using this model is shown below. In the left-hand diagram a typical random walk is shown, whilst on the right a zoom-ed in section of a 1 million step Brownian motion walk is illustrated, highlighting the dense pattern of self crossing observed. With unlimited steps Brownian motion will theoretically fill the plane, which means that every point is reached, and by extension, every point is reached an arbitrary number of times, and the path is considered as a fractal (with dimension 2) — indeed, the was one of the defining examples in Mandelbrot's analysis of fractal dimension — see further, Mandlebrot (1970 [MAN1]).

Brownian motion — A. 1000 step model; B. sample section of 1,000,000 step model

Pure one-dimensional random walks are of particular interest in statistics, as they are closely related to Markov processes. Indeed, a simple stationary Markov Chain is a random walk that commences at 0, and makes a random transition of +1 or -1 after each interval of time. This kind of model is illustrated below for 5 paths, over 10,000 steps. As with the 2D walk, the expected position of the walk at time t, is 0, although as can be seen. the actual position of the walk at any time t may be very different from 0. The visual form of these walks also provides an indication of their application in fields such as gambling, econometrics and stock price modeling. 1D Brownian motion walks are also studied, and their application to stock and option market pricing was one of their first uses.

Random walk in 1D

Self-avoiding random walk (SAW)

Self avoiding walks are walks that do no cross themselves or retrace their paths. Whether random or non-random, such walks are usually considered for the case of the regular (square) lattice. In general the properties of such paths are not amenable to analytical results, but computational methods are available, both to generate a variety of different self-avoiding walks, and to examine the properties of such paths.

There has been a great deal of research into self-avoiding random walks (SAWs) in 2- and 3-space, much of it in chemistry, physics and mathematics. 2-D SAWs are often generated by a so-called ‘pivot’ algorithm (e.g. see Kennedy, 2002 [KEN1]), which has similarities to some fractal generation models. Pivot algorithms commence with a straight line of length n steps defined by n nodes (optionally being points on a square lattice). A series of n transformations are made to the line (rotations and reflections) by choosing a node at random and a transformation at random. The line is checked after each transformation to ensure it is not self-crossing. With large n the ‘memory’ of the original configuration is lost and a truly random line is generated. The diagram below illustrates a 4-point random walk on a lattice of 100 steps, starting at (0,0) and finishing at (6,-8) (MATLab code by John Burkardt, Virginia Tech). Note that unlike the previous subsection, this walk is self-avoiding. Random tree walks are a special form of SAW (see below).

Random walk on a rectangular lattice

Self-attracting random walks also have interesting applications in a range of practical applications. For example, because random walks will eventually pass through all possible points, a subset of paths commencing at any given point (an origin) will reach a second point (destination) in less steps/a shorter time than other paths. If the shortest such path is marked or recorded each time walks are simulated, subsequent random walks can be programmatically biased to use all or parts of this path with a self-reinforcing result. Such concepts have been used in a variety of traffic behavior modeling and, more recently, in modeling crowd behavior in built-up environments during special events (galleries, London streets). See Batty et al. (1998, [BAT1]) for a fuller discussion.

Random tree walks and Rapidly expanding random trees (RRTs)

An important class of random walks include those that generate tree-like structures. There are various forms of such structures, from random growth and branching processes that reflect models of biological growth and chemical diffusion, to structural trees that represent population dynamics from generation to generation, to exploratory methods applied to complex optimization problems. In this subsection we describe a number of such models and their application. Random walks on pre-existing trees and graphs are not covered here.

The first model is a population growth model, due to Watson and Galton (1875, [WAT1]). It involves a branching process in which each individual gives birth to a random number of offspring independently of the others and according to the same distribution. In the example illustrated below, a random tree has been produced for 6 generations, starting with a single parent (pair). The distribution used to determine the number of off-spring is a generalized discrete distribution, with the first class equating to the case off-spring=0. One result of this type of model is that some generated trees are empty, or near empty, whilst others are dense. This particular example is based on the MATLab code produced by Ingemar Kaj and Raimundas Gaigalas of Uppsala University, Mathematical Statistics group. Galton and Watson were actually investigating surnames, or family names, and the apparent tendency for particular surnames to disappear over time. Indeed, they concluded that under fairly general assumptions, any surname will disappear over time.

Random Tree — Galton and Watson model, 6 generations

The second and third examples are of random tree growth used to solve spatial optimization problems. In this case a starting point (source) and finishing point (target) are defined in 2D or 3D space. Obstacles lie in the path of a direct Euclidean space path, and the problem is to find the shortest path from source to target. This kind of operation has a range of applications, but in this instance was developed by Lavalle (1988, [LAV1]) for fast robot navigation (e.g. maneuvering around the space station, across the Mars landscape etc). Exhaustive search in such cases is not a practical proposition, although regular discretization of the space may reduce the scale of the problem significantly — this can then be followed by conventional shortest path or distance transform procedures (see, for example, de Smith, 2004, for a fuller discussion, [DES1]). In the first example (illustrated below) a path is sought from (0,0,0) to (0,1,0) with two vertical barriers (shown in grey) that have small square apertures in them. Random trees are grown (either from one end or both ends) within a bounding region (a 3D cube in this example) until one or more find the apertures and continue to grow and search. Eventually a proximity criterion enables an end-to-end connection to be made and an initial feasible solution (shown below in red/darker line) is found. Then, either using geometric analysis or variational methods, this solution is improved to obtained a reduced (feasible and more optimal) path (green/paler line) — code implemented in MATLab by Clifton et al (2008, [CLI1]).

3D RRT multi-tree model

The second example is a generalization of Steiner's problem (for more details of this procedure and sample software see the author's VORTAL web page). The objective is to connect the three corner points with the shortest path in the plane avoiding the obstacles (shown as green rectangles) by a specified minimum distance. A directionally correlated random tree (see further CRWs) was grown from each corner simultaneously until a feasible path connecting all three nodes was identified (black line). This was then optimized further by variational methods (effectively a form of string tightening process to remove the wiggles in the path as much as possible) resulting in the final optimized (local optimum) path.

VORTAL model using random trees to solve an optimization problem

Correlated Walk Analysis (CWA) is an analytical procedure based on examining a sequence of events (e.g. crimes, animal movements) in terms of location, bearing (direction from a given point) and time lapse. Its objective is to predict where subsequent events, e.g. burglaries, may occur. An essential part of such analyses is the examination of patterns in the distribution of data as the distance and direction of examination is varied. The central idea is that animals and humans do not walk from one point to the next completely at random, but there is often a directional correlation in their behavior which can be examined and even modeled (a correlated random walk, or CRW). This modeling and analysis is usually performed by some form of simulation process, most notably in crime analysis software (e.g. CrimeStat) or ecology software (e.g. GME). The results are typically graphical rather than statistical, although measures such as the location reached after a certain interval of time, the mean travel time and mean distance traveled, the mean distance from the start point, the mean direction etc., can be computed with ease. In principle, such tools can be used to generate a large number of random walks, and the statistical properties of these examined computational, rather than analytically, for example to produce probability surfaces identifying the end point at time t.

A Correlated Random Walk (CRW) simulation facility is provided with the GME software tool (see diagram below). This example, which uses the Normal distribution for angular selection and the Uniform distribution for step length, highlights the impact of model parameters on the resulting path form. Distributions used in the latest version of this software are chosen from a range of options based on the R library or from empirical data loaded by the user, and modeling is either in 2D free space, or may incorporate polygonal constraints (barriers).

Correlated Random Walk simulation

A. 500 step CRW, variable (random uniform) step length, directional model N(0,1) degrees |
B. 500 step CRW, variable (random uniform) step length, directional model N(30,15) degrees |

References

[BAT1] Batty M, Jiang B, Thurstain-Goodwin M (1998) Local movement: agent-based models of pedestrian movement, Working Paper 4, CASA, UCL London

[CLI1] Clifton M, Paul G, Kwok N, Liu D, Wang D-L (2008) Evaluating Performance of Multiple RRTs. IEEE conference on Mechatronic and Embedded Systems and Application

[DAV1] David H A, Edwards A W F eds. (2001) The random walk and its fractal limiting form — comments on Venn, 1888. in Annotated Readings in the History of Statistics. Springer

[DES1] de Smith M J (2004) Distance transforms as a new tool in spatial analysis, urban planning and GIS, Environment & Planning B, 31(1), 85-104

[KEN1] Kennedy T (2002) A faster implementation of the pivot algorithm for self-avoiding walks. J. Stat. Phys., 106, 407-429; see the code and set of images provided by Kennedy at: http://math.arizona.edu/~tgk/

[LAV1] Lavalle S M (1998) Rapidly-exploring random trees: A new tool for path planning. TR 98-11, Computer Science Dept., Iowa State University. See further Lavalle's RRT page: http://msl.cs.uiuc.edu/rrt/

[LEV1] Levine N (2009). CrimeStat: A Spatial Statistics Program for the Analysis of Crime Incident Locations (v 3.2a). Ned Levine & Associates, Houston, TX, and the National Institute of Justice, Washington, DC.

[MAD1] Madras N, Slade G (1998) The Self-avoiding Walk.

[MAN1] Mandlebrot B B (1970) Fractals: Form, chance and dimension. San Francisco, Freeman, p.10

[PEA1] Pearson K (1905) The problem of the Random Walk. Nature, 72, 294

[WAT1] Watson H W, Galton F (1875) On the Probability of the Extinction of Families. Journal of the Anthropological Institute of Great Britain, 4, 138–144