Random walk

Lore & Background

An elementary example of a random walk is on the integer number line, starting at 0, where at each step the walk moves +1 or −1 with equal probability. This can be illustrated by flipping a fair coin: heads moves right, tails moves left. After five flips, the marker can land on positions -5, -3, -1, 1, 3, or 5, with varying numbers of ways to reach each position. The series {S_n} defined as the sum of independent random variables each being 1 or −1 with 50% probability is called the simple random walk on Z.

The expectation of S_n is zero, and the expected squared distance after n steps is n, implying the expected translation distance is of order √n. A simple random walk on Z will cross every point an infinite number of times, a phenomenon known as recurrence or gambler's ruin. If a and b are positive integers, the expected number of steps until the walk first hits b or −a is ab, and the probability of hitting b before −a is a/(a+b).

Reader's Guide

Random walks are fundamental in probability theory and have broad applications. The simple symmetric random walk on the integer lattice is the best-studied example, serving as a model for phenomena from stock prices to animal foraging. The concept of recurrence, where the walk returns to any point infinitely often, is a key property distinguishing one-dimensional walks from higher dimensions. The gambler's ruin problem illustrates that a gambler with finite money playing a fair game against an infinite bank will eventually lose. These ideas extend to lattice random walks on regular lattices, including the d-dimensional integer lattice, and to Monte Carlo simulation for generating realizations.

Did You Know?

• A simple random walk on the integer number line will cross every point an infinite number of times.
• The expected translation distance after n steps is of the order √n.
• The probability that a one-dimensional simple random walk starting at 0 will hit b before −a is a/(a+b).