Random walk
A random walk is a simple stochastic process. It is a formalization of the intuitive idea of taking successive steps, each in a random direction. For this reason it is sometimes called a "Drunkard's walk". ("Drunkard's walk" is a 1960 science fiction novel by Frederik Pohl.)
Properties
The simplest random walk is a path constructed according to the following rules:
- There is a starting point.
- The distance from any point in the path to the next point in the path is a constant.
- The direction from any point in the path to the next point in the path is chosen uniformly at random.
The average straight-line distance between start and finish points of a random walk of length n is O(n½).
The following, perhaps surprising, theorem is very useful in the study of random walks:
Theorem 1.1 For any random walk, every point in the domain will almost surely be crossed an infinite number of times. That is,  (crossing  times)
Example
 Eight random walks starting at (0,0).
Eight random walks, each starting at zero, are shown here for 100 timesteps. At each instant, they go either one step forwards or backwards. As one can see, while their average position remains zero, their average distance to the origin does indeed increase, but more slowly than linearly.
Significance in mathematics and physics
Random walks are sometimes used as simplified models of Brownian motion and the random movement of molecules in liquids and gases. A random walk also serves as an idealized mathematical model for coin-tossing.
Suggested reading
- William Feller, An Introduction to Probability Theory and its Applications (Volume 1) (1968) ISBN 047125708-7
- Chapter 3 of this book contains a thorough discussion of random walks, including advanced results, using only elementary tools.
Referenced By
Levy flights | List of mathematical topics (P-R) | List of probability topics | Lévy flight
|
