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.)
| Table of contents |
|
2 Example 3 Significance in mathematics and physics 4 Suggested reading |
The simplest random walk is a path constructed according to the following rules:
Properties
The average straight-line distance between start and finish points of a random walk of length n is O(n1/2).
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)
Eight random walks, each starting at zero, are shown here for 100 timesteps. At each instant, they go either one step 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.
Example
Eight random walks starting at (0,0).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
Chapter 3 of this book contains a thorough discussion of random walks, including advanced results, using only elementary tools.
