Donsker Convergence for the Simple Symmetric Walk

From a Symmetric Walk to a Brownian Path

A simple symmetric random walk moves one unit to the right or left at each step, with equal probabilities. At a fixed number of steps, its typical displacement is of the order of the square root of that number. Donsker’s theorem turns this scaling observation into a statement about entire paths: after rescaling time and space together, the walk approaches Brownian motion on any fixed time interval.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((\xi_k)_{k\ge1}\) be independent random variables with \(\mathbb{P}(\xi_k=1)=\mathbb{P}(\xi_k=-1)=\tfrac12\), and define \(S_0=0\) and \(S_m=\sum_{k=1}^m \xi_k\) for \(m\ge1\). The walk \((S_m)_{m\ge0}\) has state space \(\mathbb{Z}\) and discrete time \(m\). For each positive integer \(n\), define a continuous-time, continuous-path process on a fixed interval \([0,T]\) by linearly interpolating the walk between its step times and scaling space by \(1/\sqrt n\):

Here \(\lfloor nt\rfloor\) is the integer part of \(nt\). At a grid time \(t=m/n\), this gives \(W_n(t)=S_m/\sqrt n\). Between grid times, it joins adjacent scaled walk values by a straight line. The time scaling means that \(n\) walk steps correspond to one unit of rescaled time.

The Donsker Result and Its Hypotheses

To apply the theorem, check its hypotheses for the particular increments, not just the shape of the plotted paths. The simple symmetric increments are identically distributed and independent by construction. Their mean and second moment are

Thus the increments are centered and have variance \(1\). They also have finite second moment, as required. Consequently, for every fixed finite \(T\), the scaled, linearly interpolated simple symmetric walk converges in distribution in \(C[0,T]\) to standard Brownian motion. The conclusion is about the random path, not merely the value at one time.

The unit variance is what fixes the Brownian scale. If increments instead had variance \(\sigma^2>0\), the unadjusted space scaling \(1/\sqrt n\) would give limiting covariance \(\sigma^2\min(s,t)\), rather than the standard Brownian covariance \(\min(s,t)\). That broader setting belongs to the later treatment of finite-variance increments; here the increments have variance exactly \(1\).

Checks on the Scaling

Two elementary calculations help interpret the theorem. First, interpolation changes the stepwise walk by at most one step’s scaled size. Second, the covariance of the interpolated process approaches the Brownian covariance. These facts do not replace Donsker’s theorem: convergence of covariances alone would not establish convergence of path distributions. They do provide direct checks that the interpolation and scaling have the expected size and dependence.

Proof. Write \(r=nt-\lfloor nt\rfloor\), so \(0\le r<1\). The difference between the interpolated and stepwise values is \(r\xi_{\lfloor nt\rfloor+1}/\sqrt n\). Since \(|\xi_k|=1\), its absolute value is \(r/\sqrt n\le1/\sqrt n\).

For the covariance, it is enough to take \(s\le t\), since covariance is symmetric. Write \(ns=a+\alpha\) and \(nt=b+\beta\), where \(a,b\) are nonnegative integers and \(0\le\alpha,\beta<1\). The process value at time \(s\) has coefficient \(1/\sqrt n\) on each of \(\xi_1,\ldots,\xi_a\) and coefficient \(\alpha/\sqrt n\) on \(\xi_{a+1}\). The corresponding coefficients at \(t\) are \(1/\sqrt n\) through \(\xi_b\) and \(\beta/\sqrt n\) on \(\xi_{b+1}\). Distinct increments have covariance zero, and each increment has variance \(1\). If \(a<b\), the shared coefficients give covariance \((a+\alpha)/n=s\). If \(a=b\), the covariance is \((a+\alpha\beta)/n\), so its difference from \(s=(a+\alpha)/n\) is \(\alpha(1-\beta)/n\). In this case \(\alpha\le\beta\), and \(0\le\alpha(1-\beta)\le1\), so the difference is at most \(1/n\). In both cases the covariance differs from \(\min(s,t)=s\) by at most \(1/n\), which tends to zero. \(\square\)

The bound on interpolation is uniform over the whole time interval: \(\sup_{0\le t\le T}|W_n(t)-U_n(t)|\le1/\sqrt n\). It explains why joining the grid values does not create a large extra fluctuation. The covariance calculation checks the variance scale and the dependence between times; the theorem supplies the stronger path-distribution conclusion.

Why Path Convergence Is Stronger Than an Endpoint Limit

The endpoint calculation concerns only \(W_n(1)\). Even convergence of the joint distributions at every finite collection of times would not, by itself, rule out irregular behavior between those times. Donsker’s theorem establishes convergence as random elements of \(C[0,T]\); its proof requires both control of finite-dimensional distributions and tightness of the path laws. The tightness argument is a substantive part of the earlier proof structure, not a consequence of the variance calculation alone.

Path convergence is useful when the quantity of interest depends on a whole trajectory, such as the maximum over an interval or the time spent above a level. For example, the map \(f\mapsto\sup_{0\le t\le T}f(t)\) is continuous in the uniform norm: for any \(f,g\in C[0,T]\),

Thus, by the continuous mapping theorem, Donsker convergence also gives convergence in distribution of the path maxima to \(\sup_{0\le t\le T}B_t\). This conclusion concerns the maximum of the interpolated path; interpolation makes that maximum a well-defined continuous-path functional.

Common scaling error. Dividing the walk by \(n\), rather than \(\sqrt n\), makes the fluctuations vanish. For instance, at time \(1\) with \(n=16\), the wrongly scaled endpoint \(S_{16}/16\) has variance \(16/16^2=1/16\), whereas the correctly scaled endpoint \(S_{16}/\sqrt{16}=S_{16}/4\) has variance \(16/16=1\). In general, the incorrect variance is \(n/n^2=1/n\to0\); it cannot yield a nondegenerate standard Brownian endpoint. The square-root scaling is dictated by the accumulated variance of \(n\) independent unit-variance increments.