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.)

Table of contents

1 Properties
2 Example
3 Significance in mathematics and physics
4 Suggested reading

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^1/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)

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