Random Walk

Summary

A random walk is the simplest possible stochastic process: a sequence formed by summing independent, identically-distributed steps, one per discrete time period. It predates the Wiener process both historically and conceptually — the Wiener process is what a random walk becomes in the limit of infinitely many, infinitesimally small steps — and it already has the Markov property every process in the Stochastic Processes cluster relies on, in its plainest possible form.

Layperson's mental model

Imagine flipping a coin once per second, stepping one pace right for heads and one pace left for tails, and tracking where you end up. That's a random walk: the running total of a string of independent, identical random steps. There is no rule pulling you back toward where you started — after enough flips you could, in principle, be anywhere.

double position = 0.0;
for (int i = 0; i < n_steps; ++i) {
    position += (coin_flip() ? +1.0 : -1.0);   // one independent step
}

Shrink each step and speed up the flips — smaller paces, more of them per second — and, in the limit, this discrete jittery path becomes the smooth-looking (but still nowhere-differentiable) continuous path of a Wiener process.

Detail

The definition

A random walk \(S_n\) is defined by:

\begin{equation} S_n = S_0 + \sum_{i=1}^{n} X_i \end{equation}

where \(X_1, X_2, \ldots\) are independent, identically-distributed random steps. The simple random walk takes each \(X_i = \pm 1\) with equal probability — the textbook coin-flip walk — but the step distribution need not be so restricted: any independent, identically-distributed sequence of steps produces a random walk in this general sense.

Already Markov, already no-memory

Because each step \(X_i\) is drawn independently of every earlier step, \(S_{n+1} = S_n + X_{n+1}\) depends only on the current position \(S_n\) (and the fresh draw \(X_{n+1}\)), never on how \(S_n\) was reached — the Markov property holds trivially for a random walk, and is easiest to see directly here, before any continuous-time subtlety is introduced.

The continuous-time limit

Rescale a simple random walk so that each step has size \(1/\sqrt{n}\) and steps occur every \(1/n\) of a unit of time, then let \(n \to \infty\): the rescaled walk converges to the Wiener process (Donsker's theorem, also called the functional central limit theorem). This is the precise sense in which the Wiener process is a continuous-time random walk: not merely an analogy, but a rigorously defined limit of the discrete object. Practically, it also runs the other way: simulating a Wiener process on a computer, which necessarily advances in discrete ticks, is already an approximating random walk that targets the continuous idealisation, not the continuous process itself.