Donsker's Invariance Principle and Its Proof Structure

From Scaled Sums to Brownian Paths

The central limit theorem describes the distribution of a sum at one large time. Brownian motion appears when the whole sequence of partial sums is viewed as a path: time is scaled by \(n\), space by \(\sqrt n\), and the resulting random paths converge in distribution. This functional limit is Donsker’s invariance principle. Its proof has two distinct tasks: show convergence at every finite collection of times, then show that the paths cannot oscillate too much between those times.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space and let \(X_1,X_2,\ldots\) be independent and identically distributed real random variables with \(\mathbb{E}X_1=0\) and \(\operatorname{Var}(X_1)=\sigma^2<\infty\). Write \(S_0=0\) and \(S_k=\sum_{j=1}^k X_j\) for \(k\ge1\). For \(0\le t\le1\), define the polygonally interpolated process \((W_n(t))_{0\le t\le1}\) by

where the second term is zero when \(nt\) is an integer. Thus \(W_n\) is a random element of \(C[0,1]\), the space of continuous real-valued functions on \([0,1]\), equipped with the uniform norm. Convergence in distribution in this space means convergence of the probability laws tested against bounded continuous functions on \(C[0,1]\).

The theorem does not say that the random paths \(W_n\) are close to a particular Brownian path on the same probability space. It says their distributions, as random continuous functions, converge. The two proof tasks below explain why both the finite-dimensional distributions and control of path oscillations are necessary.

Finite-Dimensional Convergence

Fix times \(0\le t_1<\cdots<t_r\le1\). The vector \((W_n(t_1),\ldots,W_n(t_r))\) can be expressed using sums over disjoint blocks of increments. The block lengths, divided by \(n\), tend to \(t_1,t_2-t_1,\ldots,t_r-t_{r-1}\). The ordinary central limit theorem applied to each block gives independent Gaussian limits with respective variances \(\sigma^2t_1,\sigma^2(t_2-t_1),\ldots,\sigma^2(t_r-t_{r-1})\). These are exactly the successive increments of \((\sigma B_t)\).

Proof. First use the step values \(S_{\lfloor nt_j\rfloor}/\sqrt n\). Put \(m_j=\lfloor nt_j\rfloor\), \(m_0=0\), and \(L_j=m_j-m_{j-1}\). The increments \(S_{m_j}-S_{m_{j-1}}\), for \(1\le j\le r\), are independent sums of \(L_j\) iid variables. Since \(L_j/n\to t_j-t_{j-1}\), where \(t_0=0\), the central limit theorem implies that \[ \frac{S_{m_j}-S_{m_{j-1}}}{\sqrt n} \] converges to a centered normal variable of variance \(\sigma^2(t_j-t_{j-1})\). If \(t_j=t_{j-1}\), then \(L_j=0\) or \(L_j/n\to0\), and the corresponding scaled block converges to zero in probability, since its variance is \(L_j\sigma^2/n\to0\). The blocks are independent for every \(n\); their joint characteristic function is the product of their characteristic functions, so the vector of blocks converges to independent Gaussian variables with the stated variances. Taking cumulative sums gives the claimed Brownian vector for the step values. Finally, for each fixed \(t_j\), interpolation changes the step value by at most \(|X_{m_j+1}|/\sqrt n\). For every \(\varepsilon>0\), \[ \mathbb{P}(|X_{m_j+1}|>\varepsilon\sqrt n) \le \frac{\mathbb{E}X_1^2}{\varepsilon^2 n} =\frac{\sigma^2}{\varepsilon^2 n}\longrightarrow0. \] There are only finitely many \(t_j\), so all interpolation errors tend to zero in probability together. This proves the proposition. \(\square\)

This argument identifies the candidate limit but does not yet establish convergence in \(C[0,1]\). Finite-dimensional convergence alone cannot rule out increasingly rapid oscillations between the selected times. Tightness supplies that missing control.

Tightness Under Only a Second-Moment Assumption

For a continuous function \(f\), define its modulus of continuity by \(\omega(f,\delta)=\sup\{|f(t)-f(s)|:s,t\in[0,1],\,|t-s|\le\delta\}\). A standard tightness criterion for \(C[0,1]\) says that tightness follows when the paths start at zero and their moduli of continuity become small in probability as \(\delta\downarrow0\), uniformly in the asymptotic sense. The estimates below establish \(\lim_{\delta\downarrow0}\limsup_{n\to\infty}\mathbb{P}(\omega(W_n,\delta)>a)=0\) for every \(a>0\). The tightness criterion and the general theorem that tightness plus finite-dimensional convergence to a continuous process implies convergence in \(C[0,1]\) are standard weak-convergence results; their general proofs are beyond this tutorial.

Here is the main estimate behind tightness. We give the details because a finite fourth moment is not assumed. A useful elementary bound is Kolmogorov’s maximal inequality: for independent, mean-zero variables \(Y_1,\ldots,Y_n\), with partial sums \(R_k=\sum_{j=1}^kY_j\), \(\mathbb{P}(\max_{k\le n}|R_k|\ge x)\le x^{-2}\sum_{j=1}^n\mathbb{E}Y_j^2\). To verify it, partition the event by the first index \(k\) at which \(|R_k|\ge x\). On that event, future increments are independent of the first \(k\) variables and have mean zero, so \(\mathbb{E}[R_n^2\mathbf{1}_{\{\text{first crossing at }k\}}]\ge x^2\mathbb{P}(\text{first crossing at }k)\). Summing over the disjoint first-crossing events and using \(\mathbb{E}R_n^2=\sum_j\mathbb{E}Y_j^2\) proves the bound.

Proof of the tightness estimate. Fix \(\varepsilon>0\). For each \(n\), decompose \[ X_k=\xi_{n,k}+\eta_{n,k},\qquad \xi_{n,k}=X_k\mathbf{1}_{\{|X_k|\le\varepsilon\sqrt n\}}- \mathbb{E}[X_k\mathbf{1}_{\{|X_k|\le\varepsilon\sqrt n\}}], \] where \(\eta_{n,k}=X_k\mathbf{1}_{\{|X_k|>\varepsilon\sqrt n\}}- \mathbb{E}[X_k\mathbf{1}_{\{|X_k|>\varepsilon\sqrt n\}}]\). The two terms sum to \(X_k\), since \(\mathbb{E}X_k=0\). For the tail sums, Kolmogorov’s inequality gives, for \(b>0\), \[ \mathbb{P}\left(\max_{k\le n}\left|\sum_{j=1}^k\eta_{n,j}\right|>b\sqrt n\right) \le \frac{\operatorname{Var}(\eta_{n,1})}{b^2} \le \frac{\mathbb{E}[X_1^2\mathbf{1}_{\{|X_1|>\varepsilon\sqrt n\}}]}{b^2} \longrightarrow0. \] The last limit follows from \(\mathbb{E}X_1^2<\infty\): the integrand is bounded by \(X_1^2\) and its indicator tends pointwise to zero.

For the truncated terms, \(|\xi_{n,k}|\le2\varepsilon\sqrt n\), \(\mathbb{E}\xi_{n,k}^2\le\sigma^2\), and hence \(\mathbb{E}\xi_{n,k}^4\le4\varepsilon^2n\sigma^2\). For a sum \(R_m\) of \(m\) such independent centered terms, expansion of the fourth power gives \[ \mathbb{E}R_m^4 =m\mathbb{E}\xi_{n,1}^4+3m(m-1)(\mathbb{E}\xi_{n,1}^2)^2 \le4\varepsilon^2n\sigma^2m+3\sigma^4m^2. \] The fourth-moment maximal inequality for partial sums, \(\mathbb{E}\max_{k\le m}|R_k|^4\le(4/3)^4\mathbb{E}|R_m|^4\), is Doob’s \(L^4\) maximal inequality applied to the partial-sum martingale; it is a standard result whose proof is beyond this tutorial.

Partition the \(n\) increments into consecutive blocks of length at most \(r=\lfloor\delta n\rfloor\). For fixed \(\delta>0\) and sufficiently large \(n\), \(r\ge\delta n/2\), and the number of blocks is at most \(2/\delta+1\). An interval of time length at most \(\delta\) intersects at most three such blocks. Within any block, the largest deviation from its starting partial sum is bounded by the maximum of the absolute partial sums in that block; linear interpolation cannot increase this maximum. Applying the fourth-moment maximal inequality in each block and the union bound, with threshold proportional to \(a\sqrt n\), gives a numerical constant \(C\), independent of \(n,\delta,\varepsilon,a\), such that the truncated path satisfies \[ \mathbb{P}(\omega(W_n^{\mathrm{trunc}},\delta)>a) \le \frac{C}{a^4}\left(\varepsilon^2\sigma^2+\delta\sigma^4+ \frac{\varepsilon^2\sigma^2}{n}+\frac{\sigma^4}{n}\right). \] Indeed, for each block the fourth-moment bound divided by \(n^2\) is at most \(4\varepsilon^2\sigma^2(r/n)+3\sigma^4(r/n)^2\); multiplying by at most \(2/\delta+1\) blocks yields the displayed terms, after enlarging \(C\).

The tail path has uniform norm at most \(n^{-1/2}\max_{k\le n}|\sum_{j=1}^k\eta_{n,j}|\), since linear interpolation lies between its endpoint values. Thus its contribution to the modulus is at most twice that norm. For fixed \(\varepsilon\), its probability of exceeding any fixed positive threshold tends to zero by the previous maximal bound. Consequently, first taking \(\limsup_{n\to\infty}\), then letting \(\delta\downarrow0\), bounds the modulus probability by a constant times \(\varepsilon^2\sigma^2/a^4\). Letting \(\varepsilon\downarrow0\) proves the asserted tightness estimate. If \(\sigma=0\), then \(X_k=0\) almost surely for every \(k\), and tightness is immediate. \(\square\)

Combining the finite-dimensional proposition, tightness, and the standard weak-convergence result stated above proves Donsker’s theorem. Brownian motion is the identified limit because its finite-dimensional distributions are centered Gaussian with covariance \(\sigma^2\min(s,t)\), and it has continuous paths.

What the Theorem Does—and Does Not—Say

Finite-dimensional convergence answers questions about a fixed finite set of times. Tightness prevents path behavior between those times from escaping control. Neither task replaces the other: convergence at a finite grid alone cannot establish convergence of the whole path, while tightness alone does not identify the limit. This division of labor is the reusable structure of many functional limit theorems.

Common pitfall. A frequent scaling error is to assign variance \(\sigma^2\) to the limit at every time. At time \(t\), the sum contains about \(nt\) increments, so its variance is about \(nt\sigma^2\); after division by \(\sqrt n\), the variance is about \(t\sigma^2\), not \(\sigma^2\). For \(t=\tfrac14\) and the first example’s \(\sigma^2=2\), the limiting variance is \(2(\tfrac14)=\tfrac12\). This agrees with the Brownian covariance formula at equal times.