Random walk

Category:Stochastic processes In mathematics and physics,\na random walk is a formalization of the intuitive idea of taking successive steps, each in a random direction. \nA random walk is a simple stochastic process. A random walk is sometimes called a "drunkard's walk". \nDrunkard's Walk is also the name of a 1960 science fiction novel by Frederik Pohl.

Table of contents

1 Properties 2 Example 3 Higher dimensions 4 Random walk on graphs 5 Relation to Brownian motion 6 Self interacting random walks 7 Applications 8 See also 9 References

Properties

The simplest random walk is a path constructed according to the following rules:

• There is a starting point.\n*The distance from one point in the path to the next is a constant.\n*The direction from one point in the path to the next is chosen at random, and no direction is more probable than another.

The average straight-line distance between start and finish points of a random walk of n steps is on the order of √n. In fact, if "average" is understood in the sense of root-mean-square, then the average distance after n steps is exactly times the step length. There is a problem in the study of random walks called the level-crossing problem.\nSuppose we draw a line some distance from the origin of the walk.\nHow many times will the random walk cross the line?\nThe following, perhaps surprising, theorem is the answer:\nfor any random walk, every point in the domain will be crossed an infinite number of times almost surely.

Example

Graphs (i,j(i)) of eight random walks starting at 0.

The graph of eight random walks, each starting at zero, are shown here for 100 timesteps. At each time step, they go either one step up or down. As one can see, \nwhile they remain clustered around their common origin (the horizontal axis), \ntheir average distance to the origin does indeed increase, but more slowly than linearly.

Higher dimensions

Imagine now a drunkard walking around in the city. The city is infinite and completely ordered, and at every corner he chooses one of the four possible routes (including the one he came from) with equal probability. Formally, this is a random walk on the set of all points in the plane with integer coordinates. Will the drunkard ever get back to his home from the bar? It turns out that \nhe will, almost surely. This is the high dimensional equivalent of the level crossing problem discussed above. However, the similarity stops here. In dimensions 3 and above, this no longer holds. In other words, a drunk bird might forever wander around, never finding its nest. The formal terms to describe this phenomenon is that random walk in dimensions 1 and 2 is recurrent while in dimension 3 and above it is transient.\n The trajectory of a random walk is the collection of sites it visited, considered as a set with disregard to when the walk arrived at the point. In 1 dimension, the trajectory is simply all points between the minimum height the walk achieved and the maximum (both are, on average, on the order of √n). In higher dimensions the set has interesting geometric properties. In fact, one gets a discrete fractal, that is a set which exhibits stochastic self-similarity on large scales, but on small scales one can observe "jugginess" resulting from the grid on which the walk is performed. The two books of Lawler referenced below are a good source on this topic.

Random walk on graphs

Assume now that our city is no longer orderly. When our drunkard reaches a certain junction he picks between the various available roads with equal probability. Thus, if the junction has seven exits the drunkard will go to each one with probability one seventh. This is a random walk on a graph. It must not be confused with a Markov chain. Unlike a general Markov chain, random walk on a graph enjoys a property called time symmetry. Roughly it means that the probabilities to traverse a given path in one direction or in the other have a very simple connection between them (if the graph is regular, they are just equal). It turns out that this property has important consequences. Starting from the 80s, much research has gone into connecting properties of the graph, such as isoperimetric inequalities, properties of the graph as an electrical network, and properties of solutions of Laplace's equation, to random walks. A significant portion of this research was focused on Cayley graphs of finitely generated groups. In many cases the results carry over to Manifolds. A good reference for random walk on graphs is the online book by Aldous and Fill. For groups see the book of Woess. \nIf the graph itself is random, this topic is called "random walk in random environment" — see the book of Hughes. All are referenced below.

Relation to Brownian motion

Brownian motion is the scaling limit of random walk in dimension 1. This means that if you take a random walk with very small steps you get an approximation to Brownian motion. To be more precise, if the step size is ε, one needs to take a walk of length L/ε² to approximate a Brownian motion of length L. As the size step tend to 0 (and the number of steps increased comparatively) random walk converges to Brownian motion in an appropriate sense. Formally, if B is the space of all paths of length L with the maximum topology, and if M is the space of measure over B with the norm topology, then the convergence is in the space M. Similarly, Brownian motion in several dimensions is the scaling limit of random walk in the same number of dimensions. A random walk is a discrete fractal, but Brownian motion is a true fractal, and there is a connection between the two. For example, take a random walk until it hits a circle of radius r. The average number of steps it performs is r². This fact is the discrete version of the fact that Brownian motion is a fractal of Hausdorff dimension 2. In two dimensions, the average number of points the same random walk has on the boundary of its trajectory is . This corresponds to the fact that the boundary of the trajectory of Brownian motion is a fractal of dimension 4/3, a fact predicted by Mandelbrot using simulations but proved only in 2001. Brownian motion enjoys many symmetries random walk does not. For example, Brownian motion is invariant to rotations, but random walk is not, since the underlying grid is not (random walk is invariant to rotations by 90 degrees, but Brownian motion is invariant to rotations by 17 degrees too). This means that in many cases, problems on random walk are easier to solve by translating them to Brownian motion, solving the problem there, and then translating back. On the other hand, some problems are easier to solve with random walks due to its discrete nature. Random walk and Brownian motion can be coupled, namely manifested on the same probability space in a dependent way that forces them to be quite close. The simplest such coupling is the Skorokhod embedding, but other, more precise couplings exist as well.

Self interacting random walks

There is a number of interesting models of random paths in which each step depends on the past in a complicated manner. All are more difficult to analyze than the usual random walk — some notoriously so. For example\n* The self avoiding walk. See the Madras and Slade book.\n* The loop-erased random walk. See the two books of Lawler.\n* The reinforced random walk.\n* The exploration process.\n

Applications

• In physics, Random walks are used as simplified models of physical Brownian motion and the random movement of molecules in liquids and gases. See for example diffusion-limited aggregation.\n*Also in physics, random walks and some of the self interacting walks play a role in quantum field theory.\n*In economics, random walks are used to model behavior of shares and other economical factors.\n*In other fields of mathematics, random walk is used to calculate solutions to Laplace's equation, to estimate the harmonic measure, and for various constructions in analysis and combinatorics.\nIn all these cases, random walk is often subsituted for Brownian motion.\n*In Brain Research, random walks and reinforced random walks are used to model cascades of neuron firing in the brain.\n*Random walk can be used to sample from a state space which is unknown or very large, for example to pick a random page off the internet or, for research of working conditions, a random illegal worker in a given country.\n*When this last approach is used in computer science it is known as Markov Chain Monte Carlo or MCMC for short. Often, sampling from some complicated state space also allows one to get a probabilistic estimate of the space's size. The estimate of the permanent of a large matrix of zeros and ones was the first major problem tackled using this approach.\n*And lest we forget that random walk started its life in modeling of gambling.

See also

\n* Law of the iterated logarithm\n* Martingale\n* coin-tossing problems.

References

• David Aldous and Jim Fill, Reversible Markov Chains and Random Walks on Graphs, http://stat-www.berkeley.edu/users/aldous/RWG/book.html\n*[[William Feller (1968), An Introduction to Probability Theory and its Applications (Volume 1). ISBN 047125708-7\n:Chapter 3 of this book contains a thorough discussion of random walks, including advanced results, using only elementary tools.\n*Barry D. Hughes (1996), Random walks and random environments, Oxford University Press. ISBN 0198537891\n*Gregory Lawler (1996), Intersection of random walks, Birkhäuser Boston. ISBN 0-8176-3892-X\n*Gregory Lawler, Conformally Invariant Processes in the Plane, http://www.math.cornell.edu/~lawler/book.ps\n*Neal Madrad and Gordon Slade (1996), The Self-Avoiding Walk, Birkhäuser Boston. ISBN 0817638911 \n*Pal Révész (1990), Random walk in random and non-random environments, World Scientific Pub Co. ISBN 981-02-0237-7\n*Wolfgang Woess (2000), Random walks on infinite graphs and groups, Cambridge tracts in mathematics 138, Cambridge University Press. ISBN 0521552923
• The XScreenSaver has a hack wander that shows random walk on the plane with the color changing with time.