Donsker's theorem

Let ${\displaystyle X_1,X_2,X_3,\dots }$ be a sequence of independent and identically distributed (i.i.d.) random variables with mean 0 and variance 1. Let ${\displaystyle S_n:=\sum _{i=1}^n{X}_i}$. The stochastic process ${\displaystyle S:=(S_n{)}_{n\in \mathbb{N}}}$ is known as a random walk. Define the diffusively rescaled random walk (partial-sum process) by

${\displaystyle W^{(n)}(t):=\frac{S_{\lfloor nt\rfloor }}{\sqrt{n}},t\in [0,1].}$

The central limit theorem asserts that ${\displaystyle W^{(n)}(1)}$ converges in distribution to a standard Gaussian random variable ${\displaystyle W(1)}$ as ${\displaystyle n\to \mathrm{\infty }}$. Donsker's invariance principle extends this convergence to the whole function ${\displaystyle W^{(n)}:=(W^{(n)}(t){)}_{t\in [0,1]}}$. More precisely, in its modern form, Donsker's invariance principle states that: As random variables taking values in the Skorokhod space ${\displaystyle \mathcal{D}[0,1]}$, the random function ${\displaystyle W^{(n)}}$ converges in distribution to a standard Brownian motion ${\displaystyle W:=(W(t){)}_{t\in [0,1]}}$ as ${\displaystyle n\to \mathrm{\infty }.}$

Formal statement

Let F_n be the empirical distribution function of the sequence of i.i.d. random variables ${\displaystyle X_1,X_2,X_3,\dots }$ with distribution function F. Define the centered and scaled version of F_n by

${\displaystyle G_n(x)=\sqrt{n}(F_n(x)-F(x))}$

indexed by x ∈ R. By the classical central limit theorem, for fixed x, the random variable G_n(x) converges in distribution to a Gaussian (normal) random variable G(x) with zero mean and variance F(x)(1 − F(x)) as the sample size n grows.

Theorem (Donsker, Skorokhod, Kolmogorov) The sequence of G_n(x), as random elements of the Skorokhod space ${\displaystyle \mathcal{D}(-\mathrm{\infty },\mathrm{\infty })}$, converges in distribution to a Gaussian process G with zero mean and covariance given by

${\displaystyle \mathrm{cov}[G(s),G(t)]=E[G(s)G(t)]=min\{F(s),F(t)\}-F(s)}$${\displaystyle F(t).}$

The process G(x) can be written as B(F(x)) where B is a standard Brownian bridge on the unit interval.

Proof sketch

For continuous probability distributions, it reduces to the case where the distribution is uniform on ${\displaystyle [0,1]}$ by the inverse transform.

Given any finite sequence of times ${\displaystyle 0<t_1<t_2<\cdots <t_n<1}$, we have that ${\displaystyle N{F}_N(t_1)}$ is distributed as a binomial distribution with mean ${\displaystyle N{t}_1}$ and variance ${\displaystyle N{t}_1(1-t_1)}$.

Similarly, the joint distribution of ${\displaystyle F_N(t_1),F_N(t_2),\dots ,F_N(t_n)}$ is a multinomial distribution. Now, the central limit approximation for multinomial distributions shows that ${\displaystyle \underset{N}{lim}\sqrt{N}(F_N(t_i)-t_i)}$ converges in distribution to a gaussian process with covariance matrix with entries ${\displaystyle min(t_i,t_j)-t_i{t}_j}$, which is precisely the covariance matrix for the Brownian bridge.