 Random walk

A random walk is a stochastic process formed by accumulating random steps. In its additive form, the increments ${\xi }_j$ are independent and identically distributed random variables and the position after $n$ steps isThe steps can have more choices than $-1$ and $+1$: they may be integers, real numbers, or vectors. A random walk on a graph instead describes steps between vertices along edges; its available moves can depend on the current vertex.

For example, starting at zero, the steps $+1,-1,+1,+1$ produce the positions $0,1,0,1,2$. This is one sample path; other step sequences can have the same endpoint. A simple random walk on the integer line makes this distinction particularly tangible: repeated Bernoulli trials determine both a whole sample path and an endpoint with a binomial distribution. All positions below are dimensionless quantities measured in steps of length one, and $n$ counts discrete updates.

The model is useful because it separates an average tendency from accumulated fluctuations. A fair simple symmetric random walk has zero expected value at every time, yet its standard deviation grows: cancellation across many possible sample paths does not keep each walker near zero. The two figures below compare sample paths with exact endpoint probabilities. For the basic additive construction and its independent increments, see MIT, Stochastic Processes I, section 2.