= Random walk
{title2=$S_n=S_0+\sum_{j=1}^n\xi_j$}
{wiki}
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 is
$$
S_n=S_0+\sum_{j=1}^n\xi_j.
$$
The 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 https://ocw.mit.edu/courses/18-s096-topics-in-mathematics-with-applications-in-finance-fall-2013/f5784e4facf3de690210d17c97358eba_MIT18_S096F13_lecnote5.pdf[MIT, Stochastic Processes I, section 2].
Back to article page
