the simple random walk

Imagine standing on a number line. A coin is flipped: heads, you step right; tails, you step left. Flip again, step again, and keep going. The wandering position you trace out is the simple random walk — the most basic, most studied process that builds up by accumulating independent random steps. It is the toy model from which a huge amount of the theory of processes is born.

Formally, take steps Z_1, Z_2, Z_3, ... that are independent and identically distributed, each equal to +1 or -1 (the symmetric case uses probability 1/2 each). Start at S_0 = 0 and set S_n = Z_1 + Z_2 + ... + Z_n, the position after n steps. This is a discrete-time, integer-state process with independent and stationary increments. Two quick facts pin down its scale: the expected position is E[S_n] = 0 (in the symmetric case the walk has no drift, it does not tend left or right), while the spread grows as Var(S_n) = n, so the typical distance from the origin grows like the square root of n — slowly, but without bound. After 100 steps you are typically about 10 away from where you started, not 100.

Despite its plainness the simple random walk is astonishingly rich. It is recurrent in one and two dimensions (it returns to its start infinitely often, with probability 1) yet transient in three or more (it eventually wanders off and may never come back) — Polya's celebrated theorem. It is the discrete ancestor of Brownian motion: rescale space by 1/sqrt(n) and time by 1/n and the walk converges to Brownian motion (Donsker's theorem). It is the natural setting for the gambler's ruin, the reflection principle, and the surprising arcsine law. Almost every idea in the theory of processes can be first met, cheaply and concretely, in the simple random walk.