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

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

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.

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.

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