Donsker Class
For any fixed finite collection of square-integrable functions, the multivariate central limit theorem describes their empirical errors. A Donsker theorem asks for convergence of the entire empirical process in the supremum norm. The extra requirement is tightness: nearby functions must have small empirical-process increments uniformly in the sample size. Entropy conditions give practical ways to verify this requirement.
Let \(X_1,\ldots,X_n\) be i.i.d. with law \(P\). For a function \(f\), write \(Pf=\mathbb{E} f(X_1)\), \(P_nf=n^{-1}\sum_{i=1}^n f(X_i)\), and \(\mathbb G_nf=\sqrt n(P_n-P)f\). Rademacher variables are independent random signs, independent of the observations. See the empirical-process setup for measurability conventions.
We now pass from uniform laws of large numbers to a uniform central limit theorem. Suppose \(X_1, \dots, X_n\) is an i.i.d. sample drawn from an unknown distribution \(\mathbf P\,\,\!\!\). As before, define the empirical process
for any \(f \in \mathcal F\), where \(\mathcal F\) is a class of measurable functions. By definition, \(\mathbb G_n f\) is a stochastic process. To discuss convergence of this process, we regard each bounded sample path as a point in a function space.
A sample-bounded process has paths in \(\ell^\infty(T)\), the space of bounded functions with supremum norm. It suffices that boundedness hold outside a common null set, on which the process can be redefined. A map into a metric space \(S\) is Borel measurable when inverse images of Borel subsets of \(S\) are measurable. Its law is tight if for every \(\eta>0\) some compact \(K\subset S\) has probability at least \(1-\eta\).
An empirical process need not be Borel measurable as an \(\ell^\infty(T)\)-valued map, even when every coordinate is measurable. Accordingly, weak convergence below means \(\mathbb E^*H(X_n)\to\mathbb EH(X)\) for every bounded continuous \(H\), where the limit is a tight Borel random element. Finite-dimensional convergence is ordinary convergence of the measurable coordinate vectors.
Theorem 1. Let \(\Omega_n = (\Omega_n, \mathfrak F_n, \widehat P_n)\) denote a sequence of probability spaces. Let \((T,d)\) be a metric space. A sequence of arbitrary maps \(X_n : \Omega_n \to \ell^\infty (T)\) converges weakly to a tight random element if and only if both of the following conditions are satisfied:
(Convergence in distribution on \(\mathbb R^m\)) For all \((t_1, \dots, t_m) \in T^m\), the random vector \((X_n(t_1), \dots, X_n(t_m))\) converges in distribution in \(\mathbb R^m\).
(Asymptotic stochastic equicontinuity) There exists a semi-metric \(d\) such that \((T,d)\) is totally bounded and that, for all \(\varepsilon > 0\),
\[\begin{aligned} \lim\limits_{\delta \to 0} \limsup_{n\to\infty} \mathbf P\,\,\!\!^* \left( \sup_{s,t \in T : d(s,t) < \delta} |X_n (s) - X_n (t)| > \varepsilon \right) = 0 ~. \end{aligned}\]
Theorem 1 is the weak-convergence criterion in Wellner’s Delft lectures, Chapter 1, Theorem 2.1, pp. 6–8 (2005 version). The following finite-grid argument explains how its hypotheses are used. Choose a finite \(\delta\)-net and a map \(\pi_\delta:T\to T\) taking values in that net with \(d(t,\pi_\delta t)<\delta\). Then
The grid processes converge by finite-dimensional convergence. The theorem constructs a tight limit \(X\) with uniformly \(d\)-continuous paths. Thus its grid approximations converge uniformly almost surely. For a test function \(H\) bounded by one and with Lipschitz constant one, the first approximation error is at most
The corresponding limit error has the same bound. First pass \(n\to\infty\), then \(\delta\downarrow0\), and finally \(\varepsilon\downarrow0\). This proves convergence for these test functions; the tight-limit characterization extends it to bounded continuous tests. The existence and tightness construction, and the converse implication, are supplied by the cited theorem.
These definitions let us state the desired form of empirical-process convergence. In the setup as above, we say \(\mathcal F\) is \(\mathbf P\,\,\!\!\)-Donsker if \(\{\mathbb G_n f : f \in \mathcal F\} \xrightarrow{d} T\), where \(T\) is a tight random element in \(\ell^\infty (\mathcal F)\). In other words, an empirical process maps from an underlying probability space to \(\ell^\infty (\mathcal F)\), i.e. its sample paths are bounded. And, if some functions \(f_1, \dots, f_m \in \mathcal F\) are such that \(P f_i^2 < \infty\) for all \(i \in \{1, \dots, m\}\), we have
where the limiting random vector follows a normal distribution with mean zero and variance given by \(\operatorname{Cov}(\mathbb G_P f_i,\mathbb G_P f_j)=P(f_if_j)-(Pf_i)(Pf_j)\). We say a stochastic process \(\mathbb G_P\) is Gaussian if, for all \(f_1, \dots, f_m \in \mathcal F\), \((\mathbb G_P f_1, \dots, \mathbb G_P f_m)\) is multivariate normal.
From Theorem 1, we can easily deduce the following.
Theorem 2. Let \(\mathcal F\) denote the class of real-valued, measurable functions \(f: \mathscr X \to \mathbb R\), such that \(\mathbf P\,\,\!\!f^2 < \infty\) for all \(f \in \mathcal F\). Suppose \(\sup_{f \in \mathcal F} |f - \mathbf P\,\,\!\!f| < \infty\) for all \(x \in \mathscr X\). Then, \(\{\mathbb G_n f : f \in \mathcal F\}\) converges weakly to a tight random element if and only if there exists a semi-metric \(d\) on \(\mathcal F\) such that \((\mathcal F, d)\) is totally bounded, and if, for all \(\varepsilon > 0\), the following asymptotic stochastic equicontinuity condition is satisfied:
To verify Theorem 2 directly from this criterion, take any \(f_1,\ldots,f_m\) and coefficients \(a_1,\ldots,a_m\). The variable \(\sum_j a_j(f_j(X)-Pf_j)\) has finite variance, so the ordinary central limit theorem applies to its empirical average. Cramér–Wold therefore gives the displayed Gaussian vector and its covariance. The pointwise bound \(H(x)=\sup_f|f(x)-Pf|<\infty\) ensures \(\|\mathbb G_n\|_{\mathcal F}\le n^{-1/2}\sum_i H(X_i)<\infty\); measurability of this envelope is not needed for that pathwise assertion. The two remaining conditions are exactly total boundedness and the displayed equicontinuity condition. In particular, being continuous as an individual function does not by itself make a class Donsker: the size of the entire class matters.
A \(\mathbf P\,\,\!\!\)-Donsker class deserves a close study because not all random elements are tight, and it is unclear that this condition is satisfied for classes of measurable functions we might be interested in (for example, for the class of continuous functions). The next two entropy criteria give sufficient conditions for a \(\mathbf P\,\,\!\!\)-Donsker class, using the tools we have discussed so far.
Theorem 3 (Donsker). Let \(\mathcal F\) be the class of measurable functions with square-integrable envelope function \(F\). Suppose \(J_{[\:]} (1, \mathcal F, \lVert \cdot \rVert_{\mathbf P\,\,\!\!, 2}) < \infty\). Then, \(\mathcal F\) is \(\mathbf P\,\,\!\!\)-Donsker.
Proof. Use the \(L^2(P)\) distance \(d(f,g)=\|f-g\|_{P,2}\). Finiteness of the bracketing integral implies that every positive-radius bracketing number is finite: an infinite value at a positive radius would force the integral below that radius to diverge. Choosing one function from each nonempty bracket gives a finite cover, so \((\mathcal F,d)\) is totally bounded. We use outer expectations for suprema when needed, as permitted in the maximal inequality.
We need control of differences between nearby functions. Write \(\mathcal G=\mathcal F-\mathcal F\). If \([l_i,u_i]\), \(1\le i\le N\), are brackets of \(L^2(P)\) width at most \(\varepsilon/2\), then the \(N^2\) brackets
cover \(\mathcal G\). Their widths are \((u_i-l_i)+(u_j-l_j)\), with norm at most \(\varepsilon\). Thus
The envelope of \(\mathcal G\) is \(G=2F\), which is square-integrable. With the convention \(\operatorname{Log}x=\max(1,\log x)\) used in the bracketing integral, the preceding bound gives
Now put \(\mathcal G_\delta=\{f-g:f,g\in\mathcal F,\ \|f-g\|_{P,2}<\delta\}\). Every member has second moment below \(\delta^2\). Its bracketing numbers are finite, so
Apply Theorem 6 with radius \(\delta\) and envelope \(G\):
For each fixed positive \(\delta\), the tail term tends to zero, since
The limit follows from \(PG^2<\infty\). First let \(n\) tend to infinity and then let \(\delta\) decrease to zero. The entropy bound above yields
Markov's inequality now gives asymptotic stochastic equicontinuity in \(d\). The envelope supplies finite second moments and sample boundedness, and the multivariate central limit theorem gives convergence of each finite collection of coordinates. Theorem 2 therefore proves that \(\mathcal F\) is \(P\)-Donsker. ◻
We can also characterize a \(\mathbf P\,\,\!\!\)-Donsker class via uniform covering numbers.
Theorem 4 (Donsker). Let \(\mathcal F\) be a class of pointwise measurable functions with a measurable envelope function \(F\). Suppose \(\mathbf P\,\,\!\!F^2 < \infty\) and \(J(1, \mathcal F, F) < \infty\). Then, \(\mathcal F\) is \(\mathbf P\,\,\!\!\)-Donsker.
Proof of Theorem 4. Set \(A=\|F\|_{P,2}\). If \(A=0\), the envelope makes the empirical process zero almost surely, so assume \(A>0\). We again use the semimetric \(d(f,g)=\|f-g\|_{P,2}\). There are two requirements: finite covers in this population metric, and control of the empirical process on small \(d\)-balls.
First fix \(0<\varepsilon<1\), and take any finite family \(f_1,\ldots,f_m\) whose pairwise \(d\)-distances exceed \(\varepsilon A\). The law of large numbers applies simultaneously to the finitely many squared differences and to \(F^2\). Thus there is a finitely supported empirical probability measure \(Q\) for which
These functions are therefore separated by more than \((\varepsilon/2)\|F\|_{Q,2}\) in \(L^2(Q)\). By the covering–packing comparison in Lemma 8,
The last bound is independent of the selected family and follows from \(J(1,\mathcal F,F)<\infty\). A greedy \(\varepsilon A\)-packing must consequently terminate; a maximal one is a cover. This proves total boundedness without assuming in advance that a largest finite packing exists. Only second moments were used.
For equicontinuity, let \(\mathcal G_\delta=\{f-g:f,g\in\mathcal F,\ \|f-g\|_{P,2}<\delta\}\), with envelope \(2F\). The strict population-norm restriction is useful for measurability: pointwise approximations from a countable subclass converge also in \(L^2(P)\), by domination with \(F\), so they eventually remain in \(\mathcal G_\delta\). Hence this difference class is pointwise measurable; outer expectations give the same bounds.
A cover of \(\mathcal F\cup\{0\}\) gives a cover of its differences by taking every pair of centers. If centers are required to lie in \(\mathcal G_\delta\), select one member from each nonempty covering cell; this at most doubles the radius. The following bound is valid with either convention:
Write \(J_F(s)=J(s,\mathcal F,F)\) and \(J_\delta(s)=J(s,\mathcal G_\delta,2F)\). Taking square roots in (2) and integrating gives
The conditional bound in Theorem 1 involves a random empirical radius. We use its local variance refinement, Theorem 4, to express the bound in terms of the population radius. For \(0<\delta\le2A\), put \(\eta=\delta/(2A)\) and \(M_n=(\mathbb E\max_{i\le n}(2F(X_i))^2)^{1/2}\). Every \(g\in\mathcal G_\delta\) satisfies \(Pg^2<\delta^2\), while \(\|2F\|_{P,2}=2A\). The theorem gives
It remains to check that the second term disappears for fixed \(\delta\). For each \(K>0\), the elementary maximum bound gives
Let \(n\) tend to infinity and then \(K\) tend to infinity. Since \(PF^2<\infty\), this proves \(M_n/\sqrt n\to0\). Consequently (3) and the entropy comparison imply
Markov's inequality proves asymptotic stochastic equicontinuity. Together with total boundedness and the finite-dimensional central limit theorem, Theorem 2 gives the conclusion. The order of limits is \(n\to\infty\) at each fixed positive \(\delta\), followed by \(\delta\downarrow0\). ◻