Random walk

A random walk is a path built from a sequence of random steps within a given mathematical space, making it a type of stochastic process. The term was introduced in 1905 by Karl Pearson. In some texts, it is also called a drunkard’s walk. One basic example occurs on the integer number line, starting at zero, where each step moves either +1 or –1 with equal probability. This can be modeled by flipping a fair coin: heads moves the marker right, tails moves it left. After five flips, the marker can land on –5, –3, –1, 1, 3, or 5. For instance, three heads and two tails (in any order) land on 1, and there are ten ways to achieve that outcome. The number of distinct walks of n steps, each step being +1 or –1, is 2ⁿ, and all are equally likely. The net distance after n steps is the sum of the step values, and its expected value is zero. The expected absolute distance grows roughly as the square root of n. A simple random walk on the integers will cross every point infinitely often if allowed to continue forever—a property known as recurrence, level-crossing, or gambler’s ruin. This last name comes from the fact that a gambler with finite money playing a fair game against an infinitely wealthy bank will eventually go broke. For positive integers a and b, the expected number of steps to first hit b or –a from zero is ab, and the probability of hitting b before –a is a/(a+b). These results can be derived from the martingale property of the walk or from Pascal’s triangle. The number of walks that end at a particular value k after n steps equals the binomial coefficient C(n, (n+k)/2), provided n and k have the same parity. Using Stirling’s formula, one can estimate this probability. Realizations of random walks can be generated through Monte Carlo simulation. Other examples include the path of a molecule in a liquid or gas (Brownian motion), a foraging animal’s search path, a fluctuating stock price, or a gambler’s financial status. Random walks have applications in ecology, psychology, computer science, physics, chemistry, biology, economics, and sociology. A popular model is the lattice random walk, where the location jumps to neighboring sites on a regular lattice according to a probability distribution. In a simple symmetric random walk on a locally finite lattice, each immediate neighbor is equally likely. The best-studied case is the d-dimensional integer lattice (hypercubic lattice). If the state space is finite, the model is called a simple bordered symmetric random walk, where transition probabilities depend on position because movement is limited at margins and corners.