Random walk

Example of eight random walks in one dimension starting at 0. The plot shows the current position on the line (vertical axis) versus the time steps (horizontal axis).

A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. The results of random walk analysis have been applied to computer science, physics, ecology, economics, psychology and a number of other fields as a fundamental model for random processes in time. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the financial status of a gambler can all be modeled as random walks. The term random walk was first introduced by Karl Pearson in 1905.

Various different types of random walks are of interest. Often, random walks are assumed to be Markov chains or Markov processes, but other, more complicated walks are also of interest. Some random walks are on graphs, others on the line, in the plane, or in higher dimensions, while some random walks are on groups. Random walks also vary with regard to the time parameter. Often, the walk is in discrete time, and indexed by the natural numbers, as in . However, some walks take their steps at random times, and in that case the position Xt is defined for the continuum of times . Specific cases or limits of random walks include the drunkard's walk and Lévy flight. Random walks are related to the diffusion models and are a fundamental topic in discussions of Markov processes. Several properties of random walks, including dispersal distributions, first-passage times and encounter rates, have been extensively studied.

Lattice random walk
A popular random walk model is that of a random walk on a regular lattice, where at each step the walk jumps to another site according to some probability distribution. In simple random walk, the walk can only jump to neighbouring sites of the lattice. In simple symmetric random walk on a locally finite lattice, the probabilities of walk jumping to any one of its neighbours are the same. The most well-studied example is of random walk on the d-dimensional integer lattice (sometimes called the hypercubic lattice) .

One-dimensional random walk
Imagine a one-dimensional length of something, a 'line'. Now imagine this line has numbers on it, spaced apart equally. A particularly elementary and concrete random walk is the random walk on the integer number line, Z , which starts at So=0 and at each step moves by ±1 with equal probability. To define this walk formally, take independent random variables Z1, Z2..., where each variable is either 1 or −1, with a 50% probability for either value, and set

The series is called the simple random walk on . This series (the sum of the sequence of -1's and 1's) gives you the length you have 'walked', if each part of the walk is of length one.

This walk can be illustrated as follows. Say you flip a fair coin. If it lands on heads, you move one to the right on the number line. If it lands on tails, you move one to the left. So after five flips, you have the possibility of landing on 1, −1, 3, −3, 5, or −5. You can land on 1 by flipping three heads and two tails in any order. There are 10 possible ways of landing on 1. Similarly, there are 10 ways of landing on −1 (by flipping three tails and two heads), 5 ways of landing on 3 (by flipping four heads and one tail), 5 ways of landing on −3 (by flipping four tails and one head), 1 way of landing on 5 (by flipping five heads), and 1 way of landing on −5 (by flipping five tails). See the figure below for an illustration of this example.