Skip to content

Donsker's Theorem

Donsker's theorem (also known as Donsker's invariance principle, or the functional central limit theorem) is a functional extension of the central limit theorem.
Let {Xn:n≥0}\{X_n : n \geq 0\} be a sequence of independent and identically distributed random variables with E[Xn]=0\mathbb{E}[X_n] = 0 and Var⁡(Xn)=1\operatorname{Var}(X_n) = 1. We look at the random walk generated by the sequence
Sn=∑k=1nXk,\begin{equation*}S_n = \sum_{k=1}^{n} X_k ,\end{equation*}
and interpolate linearly between the integer points, i.e.
S(t)=S⌊t⌋+(t−⌊t⌋)(S⌊t⌋+1−S⌊t⌋).\begin{equation*}S(t) = S_{\lfloor t \rfloor} + \left( t - \lfloor t \rfloor \right)(S_{\lfloor t \rfloor + 1} - S_{\lfloor t \rfloor}).\end{equation*}
DONSKER'S INVARIANCE PRINCIPLE
On the space C[0,1]C[0, 1] of continuous functions on the unit interval with the metric induced by the sup-norm, the sequence {Sn∗:n≥1}\{S_n^* : n \geq 1\} converges in distribution to a standard Brownian motion {B(t):t∈[0,1]}\{B(t) : t \in [0, 1]\}.

Proof of Donsker's invariance principle

The following proof is taken from Mörters and Peres [MortersPeres2010], Theorem 5.22, pp. 131–133.
The idea of the proof is to construct the random variables X1,X2,X3,…X_1, X_2, X_3, \dots on the same probability space as the Brownian motion in such a way that {Sn∗:n≥1}\{S^*_n : n \geq 1\} is with high probability close to a scaling of this Brownian motion.

Construction of stopping times

The first image illustrates Brownian Motion B(t)B(t), while the second shows how we can select specific random times that correspond to a Random Walk with Sn=B(Tn)S_n = B(T_n).
Using Skorokhod embedding, we define T1T_1 to be a stopping time with E[T1]=1\mathbb{E}[T_1] = 1 such that B(T1)=dXB(T_1) \stackrel{d}{=} X in distribution. By the strong Markov property,
{B2(t):t≥0}={B(T1+t)−B(T1):t≥0}\begin{equation*}\{B_2(t) : t \geq 0\} = \{B(T_1 + t) - B(T_1) : t \geq 0\}\end{equation*}
is a Brownian motion and independent of F+(T1)\mathcal{F}^+ (T_1) and, in particular, of (T1,B(T1))(T_1, B(T_1)). Hence we can define a stopping time T2′T'_2 for the Brownian motion {B2(t):t≥0}\{B_2(t) : t \geq 0\} such that E[T2′]=1\mathbb{E}[T'_2] = 1 and B2(T2′)=XB_2(T'_2) = X in distribution. Then T2=T1+T2′T_2 = T_1 + T'_2 is a stopping time for the original Brownian motion with E[T2]=2\mathbb{E}[T_2] = 2, such that B(T2)B(T_2) is the second value in a random walk with increments given by the law of XX. We can proceed inductively to get a sequence 0=T0≤T1≤T2≤T3<…0 = T_0 \leq T_1 \leq T_2 \leq T_3 < \dots such that Sn=B(Tn)S_n = B(T_n) is the embedded random walk, and E[Tn]=n\mathbb{E}[T_n] = n.

How close Sn∗(t)S^*_n(t) and B(nt)n\frac{B(nt)}{\sqrt{n}}

To prove convergence in C[0,1]C[0,1], we must control the sup-norm distance between the rescaled random walk Sn∗S_n^* and the Brownian scaling Wn(t)=B(nt)/nW_n(t)=B(nt)/\sqrt{n}. Let AnA_n be the event that there exists t∈[0,1)t \in [0, 1) such that ∣Sn∗(t)−Wn(t)∣>ε\left| S^*_n(t) - W_n(t) \right| > \varepsilon. We have to show that
P{∃t∈[0,1):  ∣Sn∗(t)−Wn(t)∣>ε}=P(An)→n→∞0.\begin{equation*}\mathbb{P}\{ \exists t \in [0, 1) : \; \left| S^*_n(t) - W_n(t) \right| > \varepsilon \} = \mathbb{P}(A_n) \xrightarrow[n \to \infty]{} 0.\end{equation*}
Fix t∈[k−1n,kn)t\in\left[\frac{k-1}{n},\frac{k}{n}\right). By construction, Sn∗S_n^* is the straight line joining Sk−1/nS_{k-1}/\sqrt n and Sk/nS_k/\sqrt n on this interval. Hence if Sn∗(t)S_n^*(t) is more than ε\varepsilon away from Wn(t)W_n(t), then at least one of the two endpoints Sk−1/nS_{k-1}/\sqrt n or Sk/nS_k/\sqrt n must also be more than ε\varepsilon away from Wn(t)W_n(t).
An⊂{there exists t∈[0,1) such that ∣Sk/n−Wn(t)∣>ε}∪{there exists t∈[0,1) such that ∣Sk−1/n−Wn(t)∣>ε}.\begin{equation*}A_n \subset \left\{ \text{there exists } t \in [0, 1) \text{ such that } | S_k/\sqrt{n} - W_n(t) | > \varepsilon \right\} \cup \left\{ \text{there exists } t \in [0, 1) \text{ such that } | S_{k-1}/\sqrt{n} - W_n(t) | > \varepsilon \right\}.\end{equation*}
As Sk=dB(Tk)=dnWn(Tk/n)S_k \stackrel{d}{=} B(T_k) \stackrel{d}{=}\sqrt{n} W_n(T_k / n) we obtain
An⊂An∗:={there exists t∈[0,1) such that ∣Wn(Tk/n)−Wn(t)∣>ε}∪{there exists t∈[0,1) such that ∣Wn(Tk−1/n)−Wn(t)∣>ε}.\begin{equation*}A_n \subset A^*_n := \left\{ \text{there exists } t \in [0, 1) \text{ such that } \left| W_n(T_k/n) - W_n(t) \right| > \varepsilon \right\} \cup \left\{ \text{there exists } t \in [0, 1) \text{ such that } \left| W_n(T_{k-1}/n) - W_n(t) \right| > \varepsilon \right\}.\end{equation*}
Now we deal with the probabilities of events where differences are between the same processes. For given 0<δ<10 < \delta < 1 the event An∗A^*_n is contained in
An∗⊂{there exist s,t∈[0,2] such that ∣s−t∣<δ,∣Wn(s)−Wn(t)∣>ε}∪∪{there exists t∈[0,1) such that ∣Tk/n−t∣≥δ,∣Tk−1/n−t∣≥δ}.\begin{align}A^*_n \subset & \left\{ \text{there exist } s, t \in [0, 2] \text{ such that } \left| s - t \right| < \delta, \left| W_n(s) - W_n(t) \right| > \varepsilon \right\} \cup \\\cup & \left\{ \text{there exists } t \in [0, 1) \text{ such that } \left| T_k/n - t \right| \geq \delta, \left| T_{k-1}/n - t \right| \geq \delta \right\} .\end{align}
Note that the probability of (1) does not depend on nn, because by the scaling property of Brownian motion the process WnW_n is itself a standard Brownian motion on [0,2][0,2]. Choosing δ>0\delta > 0 small, we can make this probability as small as we wish, since Brownian motion is uniformly continuous on [0,2][0, 2].

The convergence Tk/nT_k/n to tt

It remains to show that for arbitrary, fixed δ>0\delta > 0, the probability of (2) converges to zero as n→∞n \to \infty. To prove this we use that
lim⁡n→∞Tnn=lim⁡n→∞1n∑k=1n(Tk−Tk−1)=1 almost surely.\begin{equation*}\lim_{n \to \infty} \frac{T_n}{n} = \lim_{n \to \infty} \frac{1}{n} \sum_{k=1}^{n} (T_k - T_{k-1}) = 1 \text{ almost surely}.\end{equation*}
This is Kolmogorov's law of large numbers for the sequence {Tk−Tk−1}\{T_k - T_{k-1}\} of independent identically distributed random variables with mean 1. Observe that for every sequence {an}\{a_n\} of reals one has
lim⁡n→∞ann=1  ⟹  lim⁡n→∞sup⁡0≤k≤n∣ak−kn∣=0.\begin{equation*}\lim_{n \to \infty} \frac{a_n}{n} = 1 \implies \lim_{n \to \infty} \sup_{0 \leq k \leq n} \left|\frac{a_k - k}{n} \right| = 0.\end{equation*}
This is a matter of plain (deterministic) arithmetic and easily checked. Hence we have,
lim⁡n→∞Tnn=1⟹lim⁡n→∞P{sup⁡0≤k≤n∣Tk−kn∣>δ}=0.\begin{equation*}\lim_{n \to \infty} \frac{T_n}{n} = 1 \quad \Longrightarrow \quad \lim_{n \to \infty} \mathbb{P} \left\{ \sup_{0 \leq k \leq n} \left|\frac{T_k - k}{n} \right| > \delta \right\} = 0.\end{equation*}
Now recall that t∈[(k−1)/n,k/n)t \in [(k-1)/n, k/n) and let n>2/δn > 2/\delta. Then
P{there exists t∈[0,1] such that ∣Tk/n−t∣∨∣Tk−1/n−t∣≥δ}≤P{sup⁡1≤k≤n(Tk−(k−1)n∨k−Tk−1n)>δ}≤P{sup⁡1≤k≤nTk−kn≥δ/2}+P{sup⁡1≤k≤nk−Tk−1n≥δ/2},\begin{align*}\mathbb{P} \left\{ \text{there exists } t \in [0, 1] \text{ such that } |T_k/n - t| \vee |T_{k-1}/n - t| \geq \delta \right\} &\leq \mathbb{P} \left\{ \sup_{1 \leq k \leq n} \left(\frac{T_k - (k-1)}{n} \vee \frac{k - T_{k-1}}{n}\right) > \delta \right\} \\&\leq \mathbb{P} \left\{ \sup_{1 \leq k \leq n} \frac{T_k - k}{n} \geq \delta/2 \right\} + \mathbb{P} \left\{ \sup_{1 \leq k \leq n} \frac{k - T_{k-1}}{n} \geq \delta/2 \right\},\end{align*}
and by (3) both summands converge to 0.
We have proved that probability of both events (1) and (2) converges to 00 as n→0n \rightarrow 0 which imply
lim⁡n→∞P{sup⁡0≤t≤1∣B(nt)n−Sn∗(t)∣≥ϵ}=0.\begin{equation*}\lim_{n \to \infty} \mathbb{P}\left\{\sup_{0 \leq t \leq 1} \left|\frac{B(nt)}{\sqrt{n}} - S_n^*(t)\right| \geq \epsilon \right\} = 0.\end{equation*}

Approximation random walk with Brownian Motion

Choose the sequence of stopping times as in previous subsection and recall from the scaling property of Brownian motion that the random functions {Wn(t):0≤t≤1}\{W_n(t) : 0 \leq t \leq 1\} given by Wn(t)=B(nt)nW_n(t) = \frac{B(nt)}{\sqrt{n}} are standard Brownian motions. Suppose that KK is closed subset of functions in C[0,1]C[0, 1] and define new set
K[ϵ]={f∈C[0,1]:∥f−g∥sup⁡≤ϵ for some g∈K}.\begin{equation*}K[\epsilon] = \{f \in C[0, 1] : \|f - g\|_{\sup} \leq \epsilon \text{ for some } g \in K\}.\end{equation*}
Then from triangle inequality
{Sn∗∈K}∩{∥Sn∗−Wn∥sup⁡≤ϵ}⊂{Wn∈K[ϵ]}.\begin{equation*}\{S_n^* \in K\} \cap \{\|S_n^* - W_n\|_{\sup} \leq \epsilon\} \subset \{W_n \in K[\epsilon]\}.\end{equation*}
we obtain the inequality for probabilities
P{Sn∗∈K}≤P{Wn∈K[ϵ]}+P{∥Sn∗−Wn∥sup⁡>ϵ}⏟→0.\begin{equation*}\mathbb{P}\{S^*_n \in K\} \leq \mathbb{P}\{W_n \in K[\epsilon]\} + \underbrace{\mathbb{P}\{\|S^*_n - W_n\|_{\sup} > \epsilon\}}_{\to 0}.\end{equation*}
The first term does not depend on nn and is equal to P{B∈K[ϵ]}\mathbb{P}\{B \in K[\epsilon]\} for a Brownian motion BB. As KK is closed we have
lim⁡ϵ→0P{B∈K[ϵ]}=P{B∈⋂ϵ>0K[ϵ]}=P{B∈K}.\begin{equation*}\lim_{\epsilon \to 0} \mathbb{P}\{B \in K[\epsilon]\} = \mathbb{P}\left\{B \in \bigcap_{\epsilon > 0} K[\epsilon]\right\} = \mathbb{P}\{B \in K\}.\end{equation*}
Putting these facts together, we obtain lim⁡sup⁡n→∞P{Sn∗∈K}≤P{B∈K}\lim \sup_{n \to \infty} \mathbb{P}\{S^*_n \in K\} \leq \mathbb{P}\{B \in K\}, which is condition (ii) in the Portmanteau theorem. Hence Donsker's invariance principle is proved. □\Box

References

  • [Donsker1951]Donsker, Monroe D. ``An invariance principle for certain probability limit theorems.'' Memoirs of the American Mathematical Society, no. 6, 1951.
  • [MortersPeres2010]Mörters, Peter, and Yuval Peres. Brownian Motion. First edition. Cambridge University Press, 2010. PDF.