Donsker's Theorem: beautiful proof

Contents

The 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. The theorem states that a scaled random walk converges to Brownian Motion.

Let

\{X_n : n \geq 0\}

be a sequence of independent and identically distributed random variables and assume that they are normalised, so that

\mathbb{E}[X_n] = 0

and

\text{Var}(X_n) = 1

. This assumption is no loss of generality for

X_n

with finite variance, since we can always consider the normalisation

\begin{equation*}\frac{X_n - \mathbb{E}[X_n]}{\sqrt{\text{Var}(X_n)}}.\end{equation*}

We look at the random walk generated by the sequence

\begin{equation*}S_n = \sum_{k=1}^{n} X_k ,\end{equation*}

and interpolate linearly between the integer points, i.e.

\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*}

This defines a random function

S \in C[0, \infty)

. We now define a sequence

\{S^*_n : n \geq 1\}

of random functions in

C[0, 1]

\begin{equation*}S^*_n(t) = \frac{S(nt)}{\sqrt{n}} \quad \text{for all } t \in [0, 1].\end{equation*}

Theorem (Donsker's Invariance Principle)
On the space

C[0, 1]

of continuous functions on the unit interval with the metric induced by the sup-norm, the sequence

\{S_n^* : n \geq 1\}

converges in distribution to a standard Brownian motion

\{B(t) : t \in [0, 1]\}

Proof of Donsker's invariance principle

The foolowing proof is taken from Theorem 5.22, p. 131-133 of [MörtersPeres]

Proof of Donsker's invariance principle

The foolowing proof is taken from Theorem 5.22, p. 131-133 of [MörtersPeres]

The idea of the proof is to construct the random variables

X_1, X_2, X_3, \dots

on the same probability space as the Brownian motion in such a way that

\{S^*_n : n \geq 1\}

is with high probability close to a scaling of this Brownian motion.

Construction of stopping times

Using Skorokhod embedding, we define

T_1

to be a stopping time with

\mathbb{E}[T_1] = 1

such that

B(T_1) \stackrel{d}{=} X

in distribution. By the strong Markov property,

\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

\mathcal{F}^+ (T_1)

and, in particular, of

(T_1, B(T_1))

. Hence we can define a stopping time

T'_2

for the Brownian motion

\{B_2(t) : t \geq 0\}

such that

\mathbb{E}[T'_2] = 1

and

B_2(T'_2) = X

in distribution. Then

T_2 = T_1 + T'_2

is a stopping time for the original Brownian motion with

\mathbb{E}[T_2] = 2

, such that

B(T_2)

is the second value in a random walk with increments given by the law of

X

. We can proceed inductively to get a sequence

0 = T_0 \leq T_1 \leq T_2 \leq T_3 < \dots

such that

S_n = B(T_n)

is the embedded random walk, and

\mathbb{E}[T_n] = n

donskerTheorem SkorokhodEmbedding.png — The first image illustrates Brownian Motion $B(t)$ , while the second shows how we can select specific random times that correspond to a Random Walk with $S_n = B(T_n)$ .

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

Abbreviate

W_n(t) = \frac{B(nt)}{\sqrt{n}}

and let

A_n

be the event that there exists

t \in [0, 1)

such that

\left| S^*_n(t) - W_n(t) \right| > \varepsilon

. We have to show that

\begin{equation*}P\{ \exists t \in [0, 1) : \; \left| S^*_n(t) - W_n(t) \right| > \varepsilon \} = P(A_n) \rightarrow 0 \quad \text{n} \rightarrow \infty.\end{equation*}

Let

k = k(t)

be the unique integer with

(k-1)/n \leq t < k/n

. Since

S^*_n

is linear on such an interval we have

\begin{align*}A_n \subset & \left\{ \text{there exists } t \in [0, 1) \text{ such that } | S_k/\sqrt{n} - W_n(t) | > \varepsilon \right\} \cup \\\cup & \left\{ \text{there exists } t \in [0, 1) \text{ such that } | S_{k-1}/\sqrt{n} - W_n(t) | > \varepsilon \right\}.\end{align*}

S_k \stackrel{d}{=} B(T_k) \stackrel{d}{=}\sqrt{n} W_n(T_k / n)

we obtain

\begin{align*}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 \\\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{align*}

Now we deal with the probabilities of events where differences are between the same processes.For given

0 < \delta < 1

the event

A^*_n

is contained in

\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

n

. Choosing

\delta > 0

small, we can make this probability as small as we wish, since Brownian motion is uniformly continuous on

[0, 2]

The convergence $T_k/n$ to $t$

It remains to show that for arbitrary, fixed

\delta > 0

, the probability of (2) converges to zero as

n \to \infty

. To prove this we use that

\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

\{T_k - T_{k-1}\}

of independent identically distributed random variables with mean 1. Observe that for every sequence

\{a_n\}

of reals one has

\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,

\begin{equation}\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 \in [(k-1)/n, k/n)

and let

n > 2/\delta

. Then

\begin{equation*}\mathbb{P} \left\{ \text{there exists } t \in [0, 1] \text{ such that } \left| \frac{T_k/n - t}{T_{k-1}/n - t} \right| \geq \delta \right\}\end{equation*}

\begin{equation*}\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\}\end{equation*}

\begin{equation*}\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{equation*}

and by (3) both summands converge to 0.

We have proved that probability of both events (1) and (2) converges to

0

n \rightarrow 0

which imply

\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

\{W_n(t) : 0 \leq t \leq 1\}

given by

W_n(t) = \frac{B(nt)}{\sqrt{n}}

are standard Brownian motions. Suppose that

K

is closed subset of functions in

C[0, 1]

and define new set

\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

\begin{equation*}\| S^*_n \|_{\sup} \leq \| W_n \|_{\sup} + \| S^*_n - W_n \|_{\sup}\end{equation*}

we obtain the inequality for probabilities

\begin{equation*}\mathbb{P}\{S^*_n \in K\} \leq \mathbb{P}\{W_n \in K[\epsilon]\} + \mathbb{P}\{\|S^*_n - W_n\|_{\sup} > \epsilon\}.\end{equation*}

n \to \infty

, the second term goes to

0

because of (4), whereas the first term does not depend on

n

and is equal to

\mathbb{P}\{B \in K[\epsilon]\}

for a Brownian motion

B

. As

K

is closed we have

\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 \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

[MörtersPeres]
Peter Mörters and Yuval Peres. Brownian Motion. Cambridge University Press, 2010.

Donsker's Theorem: beautiful proof

Proof of Donsker's invariance principle

Proof of Donsker's invariance principle

Proof of Donsker's invariance principle

Construction of stopping times

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

The convergence Tk/nT_k/nTk​/n to ttt

Approximation random walk with Brownian Motion

References

References

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

The convergence $T_k/n$ to $t$