From random walk to Brownian motion

How fast must the steps of a random walk shrink as its time step shrinks?

If the steps shrink too fast, the spread at a fixed time shrinks to 0 and the paths bunch up near 0; if they shrink too slowly, the spread blows up. Exactly one power of the time step lies in between. With it the walk converges to Brownian motion, and later lessons use Brownian motion to model stock prices.

Before you start · 3 quick checks on random walks, the central limit theorem and normal probabilities, about 3 min

Setup: a random walk on a time grid

Fix a horizon \(T \gt 0\) and a number of steps \(n\). The partition \(0 = t_0 \lt t_1 \lt \dots \lt t_n = T\) has equal spacing \(\Delta t = T/n\), so \(t_k = k\,\Delta t\).

Coin flips. \(\xi_1, \dots, \xi_n\) are independent, and each is \(+1\) or \(-1\) with probability \(\tfrac12\). So \(E[\xi_k] = 0\) and \(\xi_k^2 = 1\).
Steps. Every step has the same size \(\Delta x \gt 0\): the increment over \([t_{k-1}, t_k]\) is \(\Delta W_k = W^{(n)}_{t_k} - W^{(n)}_{t_{k-1}} = \Delta x\,\xi_k\).
The walk. \(W^{(n)}_{t_0} = 0\) and \(W^{(n)}_{t_k} = \Delta W_1 + \dots + \Delta W_k\). Between grid times the path is a straight line, so \(t \mapsto W^{(n)}_t\) is continuous on \([0, T]\).

The question of this page: if the step size is a power of the time step, \(\Delta x = (\Delta t)^a\) with an exponent \(a \gt 0\), what happens to the walk as \(n \to \infty\), that is, as \(\Delta t \to 0\)?

Notation shared with the next steps

The next steps of the option pricing path (quadratic variation, martingales, the Itô integral) use the same names: \(W_t\) is a standard Brownian motion, \(T\) the horizon, \(0 = t_0 \lt t_1 \lt \dots \lt t_n = T\) a partition with \(\Delta t = T/n\), and \(\Delta W_k = W_{t_k} - W_{t_{k-1}}\) the increments. On this page the superscript in \(W^{(n)}\) marks the walk with \(n\) steps, before any limit is taken.

A larger exponent \(a\) gives smaller steps once \(\Delta t \lt 1\): for example \((0.01)^{1} = 0.01\) but \((0.01)^{0.25} \approx 0.316\).

1 See

Choose how fast the steps shrink

The goals, the definition of the limit and the key point of this part appear after your first pick.

Definition: standard Brownian motion

A process \((W_t)_{t \ge 0}\) is a standard Brownian motion if

\(W_0 = 0\);
for any times \(0 \le t_0 \lt t_1 \lt \dots \lt t_m\), the increments \(W_{t_1} - W_{t_0}, \dots, W_{t_m} - W_{t_{m-1}}\) over these non-overlapping intervals are independent;
for \(0 \le s \lt t\), the increment \(W_t - W_s\) is normal with mean 0 and variance \(t - s\), written \(W_t - W_s \sim N(0, t - s)\);
with probability 1, the path \(t \mapsto W_t\) is continuous.

By (iii) the distribution of an increment depends only on the length of its interval, not on where the interval starts: the increments are stationary. Such a process exists; N. Wiener constructed it in 1923. The walk with steps \(\pm\sqrt{\Delta t}\) has property (i), independent increments over grid intervals, increments with mean 0 and variance exactly \(t - s\) between grid times \(s \lt t\), and continuous paths. Only its increments are not normal; the central limit theorem fixes that in the limit.

From the central limit theorem to Donsker's theorem

At one time. Take \(\Delta x = \sqrt{\Delta t}\) and fix a time \(0 \lt t \le T\); at \(t = 0\) the walk is 0, which is \(N(0, 0)\), so there is nothing to prove. First let \(t = m\,\Delta t\) be a grid time, so \(m \ge 1\). Then \(W^{(n)}_t = \sqrt{\Delta t}\,(\xi_1 + \dots + \xi_m) = \sqrt{t}\,(\xi_1 + \dots + \xi_m)/\sqrt{m}\). As \(n \to \infty\) with \(t\) fixed, \(m \to \infty\), and by the central limit theorem \((\xi_1 + \dots + \xi_m)/\sqrt{m}\) converges in distribution to a standard normal. So \(W^{(n)}_t\) converges in distribution to \(N(0, t)\). For a time \(t\) between grid points the straight-line piece moves the value by at most one step \(\sqrt{\Delta t} \to 0\), so the same limit holds at every fixed \(t\).

What shrinking to 0 means. For \(a \gt 1\) every path flattens: a path moves at most \(n\,\Delta x = T^a n^{1-a}\) away from 0, and that tends to 0. For \(\tfrac12 \lt a \le 1\) some paths do not flatten: the path that goes up at every step ends at \(T^a n^{1-a}\), which equals \(T\) when \(a = 1\) and grows with \(n\) when \(\tfrac12 \lt a \lt 1\) (with \(T = 1\) and \(a = 0.75\) it ends at \(n^{0.25}\)). That path has probability \(2^{-n}\). What tends to 0 for every \(a \gt \tfrac12\) is the chance of a large value anywhere on \([0, T]\). The path is straight between grid times, so its largest size is \(\max_k \lvert W^{(n)}_{t_k}\rvert\), and by Kolmogorov's inequality \(P(\sup_{t \le T} \lvert W^{(n)}_t\rvert \ge \varepsilon) \le \operatorname{Var}(W^{(n)}_T)/\varepsilon^2 = T^{2a}n^{1-2a}/\varepsilon^2\), which tends to 0 for every \(\varepsilon \gt 0\). So for every \(a \gt \tfrac12\) the walk converges to 0 in probability, uniformly on \([0, T]\).

Whole paths (stated, not proved). Donsker's theorem: with steps \(\pm\sqrt{\Delta t}\) and straight lines between grid times, the random continuous functions \(t \mapsto W^{(n)}_t\) on \([0, T]\) converge in distribution to a Brownian motion on \([0, T]\) as \(n \to \infty\). The same holds for any independent, identically distributed steps with mean 0 and variance 1 in place of the coin flips. The proof needs more than the central limit theorem at finitely many times: it also needs control of the whole path between them.

Key point With steps \((\Delta t)^a\) the variance at time 1 is \(n^{1-2a}\). Only \(a = \tfrac12\), steps of \(\pm\sqrt{\Delta t}\), keeps it fixed; larger exponents squeeze the spread to 0 and smaller ones make it blow up. The limit of that walk is Brownian motion.

2 Try

Covariance, scaling and increments

The questions are about a standard Brownian motion \(W\), as defined at the end of stage 1: \(W_0 = 0\), independent increments over non-overlapping intervals, and \(W_t - W_s \sim N(0, t - s)\). The figures use 2000 seeded paths of the walk with steps \(\pm\sqrt{\Delta t}\), \(T = 1\) and \(n = 256\) as a stand-in. At grid times its increments have the same means, variances and independence as those of \(W\).

Increment goals

Choose a window \([s, t]\) with the sliders, in steps of \(\tfrac1{16}\). The figure shows the increment \(W_t - W_s\) of the 2000 walk paths and the normal density with variance \(t - s\).

Key point Everything about Brownian motion at finitely many times follows from one rule: split the times into non-overlapping windows, and the increments over them are independent and normal, each with variance equal to its window length.

3 Prove

Why the exponent must be one half, and the covariance

Theorem 1 (variance of the walk)

Assumptions. \(T \gt 0\), an integer \(n \ge 2\), \(\Delta t = T/n\) and \(t_k = k\,\Delta t\). The coin flips \(\xi_1, \dots, \xi_n\) are independent, each \(\pm1\) with probability \(\tfrac12\). An exponent \(a \gt 0\) is fixed (line 4 of the proof compares all exponents \(a \gt 0\)), \(\Delta x = (\Delta t)^a\), \(\Delta W_k = \Delta x\,\xi_k\), \(W^{(n)}_0 = 0\) and \(W^{(n)}_{t_k} = \Delta W_1 + \dots + \Delta W_k\).

Conclusion. For every \(k = 0, 1, \dots, n\), \(E[W^{(n)}_{t_k}] = 0\) and \(\operatorname{Var}(W^{(n)}_{t_k}) = t_k(\Delta t)^{2a-1}\). In particular \(\operatorname{Var}(W^{(n)}_T) = T^{2a}n^{1-2a}\). Comparing every exponent \(a \gt 0\): as \(n \to \infty\) it tends to 0 if \(a \gt \tfrac12\) and to \(\infty\) if \(a \lt \tfrac12\), and it equals \(T\) for every \(n\) exactly when \(a = \tfrac12\). Then \(\operatorname{Var}(W^{(n)}_{t_k}) = t_k\) at every grid time.

Scratch work, not part of the proof.

Theorem 2 (covariance of Brownian motion)

Assumptions. \(W\) is a standard Brownian motion: properties (i), (ii) and (iii) of the definition in stage 1. The proof does not use (iv).

Conclusion. For all \(s, t \ge 0\), \(\operatorname{Cov}(W_s, W_t) = \min(s, t)\).

The proof below takes \(0 \lt s \lt t\). If \(s = t \gt 0\), \(\operatorname{Cov}(W_t, W_t) = \operatorname{Var}(W_t - W_0) = t\) by (i) and (iii); if \(s = 0\) the covariance is 0 because \(W_0 = 0\); and \(s \gt t\) follows by swapping the names.

Theorem 3 (scaling)

If \(W\) is a standard Brownian motion and \(c \gt 0\), then \(X_t = W_{ct}/\sqrt{c}\), \(t \ge 0\), is again a standard Brownian motion.

Theorem 3 is the continuous form of stage 1: speeding time up by \(c\) multiplies variances by \(c\), so the amplitude has to be divided by \(\sqrt{c}\), just as steps of length \(\Delta t\) need size \(\sqrt{\Delta t}\).

Key point Variances of independent steps add, so \(n\) steps of size \((\Delta t)^a\) have variance \(T^{2a}n^{1-2a}\), and only \(a = \tfrac12\) gives a limit that neither vanishes nor explodes. In the limit, splitting \(W_t\) into \(W_s\) and an independent increment gives \(\operatorname{Cov}(W_s, W_t) = \min(s, t)\).

4 Apply

Problems

\(W\) is a standard Brownian motion and \(\Phi\) is the standard normal distribution function. Answers that use \(\Phi\) are graded with a tolerance that accepts values from a printed normal table.

More problems, including daily steps of a stock-like walk

Key point For a probability, write the quantity as an increment or a sum of independent increments, find its variance from the window lengths, and standardize with the square root of that variance.

Level Advanced undergrad Prerequisites simple random walk, the central limit theorem Time ~40 min