Chaining
A single finite cover approximates a process at one resolution. A fine cover reduces approximation error but increases the number of points over which we must take a maximum. Chaining avoids paying the fine-cover cost for every increment: it approximates each index successively, using small increments between neighboring resolutions. Dudley’s entropy integral records the total cost across these scales.
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 replace the pathwise Lipschitz condition by a tail bound for each increment. Namely, we first want to relax the requirement that \(|X_t - X_s| \lesssim d(t,s)\) almost surely. Instead, we want to replace this by a condition that allows us to control these increments via “how far” \(s\) and \(t\) are in the metric space \(T\). Before giving such a relaxation, here is a general result that applies for subgaussian random variables.
Proposition 1. Suppose \(T\) is a nonempty finite set, and let \(\{X_t\}_{t \in T}\) be a stochastic process. For all \(t \in T\) and \(\eta \geq 0\), assume the following inequality holds:
where \(\sigma > 0\) is fixed. Then, there exists a universal positive constant \(C\) such that
Proof. Since \(\sup_{t \in T} \: |X_t|\) is positive, we have
by an elementary result. Then, it remains to bound the tail probability for every \(\eta \geq 0\). By assumption,
For some suitably chosen “intermediate cutoff point” \(\eta_0\), we have
Clearly, if \(T\) is large, the upper bound is crude. Therefore, pick \(\eta_0\) such that the (growing) constant \(2|T|\) vanishes, or
Therefore, we have
as desired. ◻
This motivates the following definition of a subgaussian process: a random process \(\{X_t\}_{t \in T}\), where \((T,d)\) is a metric space, is subgaussian if \(\mathbb{E} X_t = 0\) and
for all \(s,t \in T\) and \(\lambda \geq 0\). Note that this immediately implies (and is equivalent to, up to constants)
For the forward implication, exponential Markov optimized at \(\lambda=x/d(s,t)^2\) gives the upper tail; interchange \(s,t\) for the lower tail. Adding gives \(C=2\). For zero distance the increment vanishes almost surely by the moment bound.
For completeness, the converse also follows with a changed universal constant when the increments are centered. If \(Y=X_t-X_s\), \(r=d(s,t)>0\), and \(P(|Y|>u)\leq C e^{-u^2/(Cr^2)}\), enlarge \(C\) to at least one and let \(Y'\) be an independent copy. Then \(W=Y-Y'\) is symmetric, and \(P(|W|>u)\leq2C e^{-u^2/(4Cr^2)}\). Tail integration gives \(\mathbb EW^{2k}\leq2C(4Cr^2)^k k!\). Jensen, the nonnegative series for cosh, and \((2k)!\geq(k!)^2\) imply
The last inequality uses \(1+A(e^x-1)\leq e^{Ax}\) for \(A\geq1,x\geq0\). Thus a tail bound and a centered moment bound describe the same increment condition up to constants. Dudley's entropy bound combines these increment estimates across successive finite nets.
Theorem 2 (Dudley’s entropy bound; finite \(T\)). Let \((T,d)\) be a finite metric space. Let \(\{X_t\}_{t\in T}\) be a subgaussian process. Then, there exists a universal positive constant \(C\) such that the following inequality holds for every \(t_0 \in T\):
Clearly, since \(T\) is a finite set, the diameter of \(T\), denoted \(\operatorname{diam}(T)\), is finite, so
It then follows from the scaling property of the packing number that
Dudley’s entropy bound can then be stated equivalently as
To proceed proving Dudley’s entropy bound, the technique we will use is a principle of chaining. Here, \(T\) is finite, so it makes sense to construct a shrinking sequence of chains that, altogether, “link” the set \(T\) together. On each of these links, we apply Proposition 1 to show that these bounds contribute small amounts to \(\mathbb{E} \sup_{t \in T} \: |X_t - X_{t_0}|\). The conclusion then follows from arguing that we can choose arbitrarily small chains to send the approximation error to zero.
Proof. Put \(R=\operatorname{diam}(T)\). If \(R=0\), there is only one index and the claim is immediate. Otherwise set \(r_k=2^{-k}R\). For \(k\geq1\), choose a largest strictly \(r_k\)-separated subset \(T_k\), of size \(D(r_k,T,d)\). It is an \(r_k\)-net, since an uncovered point could be added. Let \(\pi_k(t)\) be a closest net point. Set \(T_0=\{t_0\}\), \(\pi_0(t)=t_0\). For sufficiently large \(K\), \(r_K\) is below every positive distance in the finite space, so \(T_K=T\) and \(\pi_K(t)=t\).
The telescoping chain and triangle inequality give
Each edge at level \(k\) has length at most \(r_k+r_{k-1}=3r_k\), including \(k=1\) because \(d(t,t_0)\leq R\). There are at most \(|T_k||T_{k-1}|\leq D(r_k,T,d)^2\) distinct edges. Exponential moments and Jensen, applied to both signs of each edge, give
For the last inequality, \(D(r_k,T,d)\geq2\): two points attaining the diameter are farther apart than \(r_k\leq R/2\). The same numerical constant works at every level. The finite maximum bound used here follows from \(\lambda\mathbb E\max|Y_j|\leq\log(2m)+\lambda^2(3r_k)^2/2\), optimized over \(\lambda>0\).
Since packing numbers decrease with radius,
Sum these disjoint dyadic intervals to obtain
The second inequality uses monotonicity to bound the integral over \([R/4,R/2]\) by the one over \([0,R/4]\). This proves the stronger truncated packing bound, and hence the stated full integral. Finally \(D(u,T,d)\leq N(u/2,T,d)\); substituting \(u=2v\) bounds the packing integral by twice the corresponding covering integral. This also proves the truncated covering version with an adjusted universal constant. ◻
For infinite index sets we approximate a countable determining set by increasing finite subsets and use monotone convergence. A dense set of indices alone does not determine the process values: a sample-path separability condition is needed to identify the full supremum with a countable one.
We need a mild restriction on the metric space \((T,d)\). A stochastic process \(\{X_t\}_{t \in T}\) is separable if there exists a countable subset \(\widetilde T\) of \(T\), and a measure zero set \(N\), such that for all \(\omega \notin N\) and \(t \in T\), there exists a sequence \(\{t_n\}\) in \(\widetilde T\) such that \(\lim\limits_{n \to \infty} d(t_n, t) = 0\) and \(\lim\limits_{n \to \infty} X_{t_n} (\omega) = X_t (\omega)\). A useful characterization of a separable stochastic process is the following: if \((T,d)\) is separable, and \(\{X_t\}_{t \in T}\) has continuous sample paths almost surely, then \(\{X_t\}_{t \in T}\) is separable. Furthermore, if \(\{X_t\}_{t \in T}\) is separable, then \(\sup_{t \in T} \: |X_t - X_{t_0}| = \sup_{t \in \widetilde T} |X_t - X_{t_0}|\) almost surely for all \(t_0 \in T\).
We are now ready to state and prove Dudley’s entropy bound in full generality, when \(T\) is not necessarily a finite set.
Theorem 3. Let \((T,d)\) be a separable metric space. Let \(\{X_t\}_{t\in T}\) be a separable subgaussian process. Then, there exists a universal positive constant \(C\) such that the following inequality holds for every \(t_0 \in T\):
where \(\overline D \triangleq \operatorname{diam}(T)\), and this need not be finite.
Proof. There exists a countable, dense subset \(\widetilde T\) of \(T\) such that \(\sup_{t \in T} \: |X_t - X_{t_0}| = \sup_{t \in \widetilde T} |X_t - X_{t_0}|\) almost surely for all \(t_0 \in T\). Add \(t_0\) to \(\widetilde T\) if necessary, so that for each \(k \geq 1\), set \(\widetilde T_k\) be a finite set obtained from taking the first \(k\) elements of \(\widetilde T\). The order of this construction doesn’t matter, and \(\widetilde T_k\) can be made such that it contain \(t_0\) for all \(k \in \mathbb N\). Applying Theorem 2 to \(\{X_t\}_{t \in \widetilde T_k}\), and writing \(\overline D_k = \operatorname{diam}(\widetilde T_k)\), we have
Passing both sides of the inequality to \(k\to\infty\), we must then have, by the monotone convergence theorem,
Applying the fact that \(\sup_{t \in T} \: |X_t - X_{t_0}| = \sup_{t \in \widetilde T} |X_t - X_{t_0}|\) almost surely concludes the proof. ◻
Remark 4 (Explicit constants). A version of the same argument gives
For finite \(T\) of positive diameter, choose the largest integer \(k_0\) with \(2^{-k_0}\geq\operatorname{diam}(T)\). Repeat the preceding proof at radii \(r_k=2^{-k}\), \(k>k_0\), using largest separated nets and the starting singleton. Each level costs at most \(3\sqrt6\,2^{-k}\sqrt{\log D(2^{-k},T,d)}\). Since \(D(2^{-k})\leq N(2^{-k-1})\), shifting the index gives the first bound with \(6\sqrt6\). The one-point case is zero. Finally,
which proves the integral bound. For an infinite separable process, apply the finite packing argument to increasing finite determining sets. Their packing numbers are bounded by those of \(T\); compare these with the covering numbers of \(T\), then pass to the limit. This avoids assuming that internal covering numbers are monotone under taking subsets. The constants here follow from the displayed estimates; the source's smaller constants were not justified by its absolute-maximum argument.
Chaining also gives probability bounds for the oscillation between nearby indices, rather than only an expectation bound for the global supremum. To do this, we define the uniform entropy integral (or covering integral, (à la Pollard 1984))
The chaining lemma below keeps track of the exceptional event at every scale. Covering-number bounds make it possible to sum the probabilities of those events.
In the chaining lemma, \((T,d)\) is a nonempty metric space (the same proof works after identifying zero-distance points in a pseudometric). Finiteness of \(J(\delta_0)\) at one positive radius implies finite covering numbers at every positive radius: an infinite number at any smaller radius would force an infinite integrand on a nontrivial interval. Monotonicity handles larger radii. It also implies finiteness and continuity of \(J\) throughout \([0,1]\), with \(J(0)=0\), because the integrand is bounded on intervals separated from zero.
Lemma 5 (Chaining). Let \(\{Z(t):t \in T\}\) be a stochastic process whose index set \(T\) has a finite covering integral \(J(\delta, T, d)\). Suppose further that there exists a constant \(D>0\) such that for all \(s,t\),
For \(\delta\in(0,1]\), define the covering number
and define
Assume \(J(\varepsilon,T,d)<\infty\) for the \(\varepsilon\) used below. Then, there exists a countable dense subset \(T^* \subset T\) such that for \(\varepsilon \in (0,1)\),
Furthermore, if \(Z\) has continuous sample paths, then \(T^*\) can be replaced by \(T\).
Proof. Fix \(\varepsilon\in(0,1)\). We prove (4) in explicit steps. Define radii
so that \(\sum_{i=1}^\infty \delta_i=\varepsilon\).
We construct finite sets \(T_i\subset T\) satisfying:
\(T_i\) is a \(2\delta_i\)-net: for every \(t\in T\), there exists \(\pi_i(t)\in T_i\) such that
\[\begin{aligned} d\left(t,\pi_i(t)\right)\le 2\delta_i. \end{aligned}\tag{6}\](Nesting) \(T_i\subset T_{i+1}\) for all \(i\).
(Cardinality bound) \(|T_i|\le N(\delta_i)\) for all \(i\).
Construction. Start from one point and enlarge it to a maximal set \(T_1\) with pairwise distances strictly greater than \(2\delta_1\). A \(\delta_1\)-cover contains at most one selected point in each ball, so this procedure stops after at most \(N(\delta_1)\) steps. Inductively \(T_i\) is already \(2\delta_{i+1}\)-separated, since \(\delta_{i+1}<\delta_i\); extend it by the same procedure to a maximal \(2\delta_{i+1}\)-separated set \(T_{i+1}\). Thus nesting, separation, and the cardinality bound hold at every scale.
Verification of (S1.1). If \(T_{i+1}\) is maximal \(2\delta_{i+1}\)-separated, then it is a \(2\delta_{i+1}\)-net: otherwise there exists \(t\in T\) with \(d(t,u)>2\delta_{i+1}\) for all \(u\in T_{i+1}\), so we could add \(t\), contradicting maximality. Thus (6) holds with \(i+1\).
Verification of (S1.3). Let \(A\subset T\) be any \(2\delta\)-separated subset. Take a \(\delta\)-cover of \(T\) with \(N(\delta)\) balls \(\{B(t_j,\delta)\}_{j=1}^{N(\delta)}\) centered at points in \(T\). Since \(A\) is \(2\delta\)-separated, each ball contains at most one point of \(A\) (otherwise two points in the same ball would have distance \(\le 2\delta\)). Hence \(|A|\le N(\delta)\). Apply this with \(A=T_i\) and \(\delta=\delta_i\) to get \(|T_i|\le N(\delta_i)\).
Finally define
\[\begin{aligned} T^\ast \equiv \bigcup_{i=1}^\infty T_i. \end{aligned}\tag{7}\]Then \(T^\ast\) is countable (countable union of finite sets). It is dense because for any \(t\in T\), (6) gives \(d(t,T_i)\le 2\delta_i\to 0\), hence \(d(t,T^\ast)=0\).
Define “bad” events at each scale. For each \(i\ge 1\), define the event
\[\begin{aligned} A_i \equiv \left\{\exists\,u,v\in T_i:\ |Z(u)-Z(v)|> D\, d(u,v) H(\delta_i)\right\}, \end{aligned}\tag{8}\]where \(H(\cdot)\) is defined in (3).
Bound \(\mathbf P\,\,\!\!(A_i)\). Fix \(i\). For any fixed pair \((u,v)\in T_i\times T_i\), apply (2) with
\[\eta \equiv D H(\delta_i)\]to obtain
\[\begin{aligned} \mathbf P\,\,\!\!\left(|Z(u)-Z(v)|> D H(\delta_i) d(u,v)\right) &\le 2\exp\left(-\frac{(D H(\delta_i))^2}{2D^2}\right) =2\exp\left(-\frac{H(\delta_i)^2}{2}\right) \nonumber\\ &= 2\exp\left(-\log \left(\frac{N(\delta_i)^2}{\delta_i}\right)\right) =\frac{2\delta_i}{N(\delta_i)^2}. \end{aligned}\tag{9}\]Now take a union bound over all pairs in \(T_i\times T_i\):
\[\begin{aligned} \mathbf P\,\,\!\!(A_i) &\le \sum_{(u,v)\in T_i\times T_i}\mathbf P\,\,\!\!\left(|Z(u)-Z(v)|> D\, d(u,v) H(\delta_i)\right) \nonumber\\ &\le |T_i|^2\cdot 2\frac{\delta_i}{N(\delta_i)^2} \le N(\delta_i)^2\cdot 2\frac{\delta_i}{N(\delta_i)^2} =2\delta_i. \end{aligned}\tag{10}\]Bound the union of bad events. By another union bound and (10),
\[\begin{aligned} \mathbf P\,\,\!\!\left(\bigcup_{i=1}^\infty A_i\right) \le \sum_{i=1}^\infty \mathbf P\,\,\!\!(A_i) \le \sum_{i=1}^\infty 2\delta_i =2\sum_{i=1}^\infty \delta_i =2\varepsilon. \end{aligned}\tag{11}\]Define the “good” event
\[G \equiv \left(\bigcup_{i=1}^\infty A_i\right)^c.\]On \(G\), for every \(i\) and all \(u,v\in T_i\),
\[\begin{aligned} |Z(u)-Z(v)|\le D d(u,v) H(\delta_i). \end{aligned}\tag{12}\]Construct chains between nearby points in \(T^\ast\). Let \(s,t\in T^\ast\) satisfy \(d(s,t)\le\varepsilon\). For positive distance, choose \(m\) large enough so that \(s,t\in T_m\) (possible since \(T^\ast=\cup_i T_i\) and the \(T_i\) are nested). Choose \(n\ge 1\) such that
\[\begin{aligned} \delta_n\le d(s,t)\le 2\delta_n \qquad\text{(equivalently, $\delta_{n-1}=2\delta_n\ge d(s,t)$).} \end{aligned}\tag{13}\]Increase \(m\) to be at least \(n\) if necessary. Define a chain \(\{s_k\}_{k=n}^m\) by setting \(s_m \equiv s\) and recursively
\[\begin{aligned} s_k \equiv \pi_k(s_{k+1})\in T_k,\qquad k=m-1,m-2,\dots,n, \end{aligned}\tag{14}\]and similarly define \(\{t_k\}_{k=n}^m\) with \(t_m \equiv t\) and \(t_k \equiv \pi_k(t_{k+1})\). By (6) applied to \(s_{k+1}\in T_{k+1}\subset T\), we have
\[\begin{aligned} d(s_{k+1},s_k)\le 2\delta_k,\qquad d(t_{k+1},t_k)\le 2\delta_k, \qquad k=n,\dots,m-1. \end{aligned}\tag{15}\]By repeated application of triangle inequality,
\[\begin{aligned} |Z(s)-Z(t)| &=|Z(s_m)-Z(t_m)| \nonumber\\ &\le |Z(s_n)-Z(t_n)|+\sum_{k=n}^{m-1}\left(|Z(s_{k+1})-Z(s_k)|+|Z(t_{k+1})-Z(t_k)|\right). \end{aligned}\tag{16}\]Control \(d(s_n,t_n)\). Again by triangle inequality and (15),
\[\begin{aligned} d(s_n,t_n) &\le d(s,t)+\sum_{k=n}^{m-1}\left(d(s_{k+1},s_k)+d(t_{k+1},t_k)\right) \nonumber\\ &\le d(s,t)+\sum_{k=n}^{m-1} (2\delta_k+2\delta_k) = d(s,t)+4\sum_{k=n}^{m-1}\delta_k \nonumber\\ &\le 2\delta_n + 4\sum_{k=n}^{\infty}\delta_k \qquad\text{(by (13))} \nonumber\\ &=2\delta_n + 4\cdot \left(\delta_n+\delta_{n+1}+\cdots\right) =2\delta_n+4\cdot (2\delta_n) =10\delta_n, \end{aligned}\tag{17}\]where we used \(\sum_{k=n}^\infty \delta_k = \delta_n/(1-1/2)=2\delta_n\).
Bound the RHS of (16) on \(G\). Work on the event \(G\); we have:
(a) The middle-scale term. Since \(s_n,t_n\in T_n\), apply (12) with \(i=n\):
\[\begin{aligned} |Z(s_n)-Z(t_n)| \le D d(s_n,t_n) H(\delta_n) \le 10D \delta_n H(\delta_n), \end{aligned}\tag{18}\]using (17).
(b) The chaining increments. For each \(k\in\{n,\dots,m-1\}\), note that \(s_k,s_{k+1}\in T_{k+1}\) because \(T_k\subset T_{k+1}\). Hence (12) with \(i=k+1\) gives
\[\begin{aligned} |Z(s_{k+1})-Z(s_k)| \le D d(s_{k+1},s_k) H(\delta_{k+1}) \le 2D \delta_k H(\delta_{k+1}), \end{aligned}\tag{19}\]where we used \(d(s_{k+1},s_k)\le 2\delta_k\) from (15). Similarly,
\[\begin{aligned} |Z(t_{k+1})-Z(t_k)| \le 2D \delta_k H(\delta_{k+1}). \end{aligned}\tag{20}\]Plugging (18)–(20) into (16) yields on \(G\):
\[\begin{aligned} |Z(s)-Z(t)| &\le 10D \delta_n H(\delta_n) + \sum_{k=n}^{m-1}\left(2D \delta_k H(\delta_{k+1})+2D \delta_k H(\delta_{k+1})\right) \nonumber\\ &=10D \delta_n H(\delta_n)+4D\sum_{k=n}^{m-1}\delta_k H(\delta_{k+1}) \nonumber\\ &\le 10D \delta_n H(\delta_n)+4D\sum_{k=n}^{\infty}\delta_k H(\delta_{k+1}). \end{aligned}\tag{21}\]Convert the sums into the entropy integral. Both \(N(u)\) and \(1/u\) are nonincreasing in \(u\in(0,1]\), and they are positive. Consequently \(H(u)=\sqrt{2\log(N(u)^2/u)}\) itself is nonincreasing. No replacement by a different entropy function is needed.
(a) Bound \(\delta_n H(\delta_n)\) by \(J(\delta_n)\). Since \(H\) is nonincreasing,
\[\begin{aligned} J(\delta_n)=\int_0^{\delta_n}H(u)\,du \ge \int_0^{\delta_n}H(\delta_n)\,du =\delta_n H(\delta_n), \end{aligned}\tag{22}\]hence
\[\begin{aligned} 10D \delta_n H(\delta_n)\le 10D J(\delta_n). \end{aligned}\tag{23}\](b) Bound the sum at the next smaller scale. For \(u\in[\delta_{k+2},\delta_{k+1}]\), monotonicity gives \(H(u)\ge H(\delta_{k+1})\). The interval has length \(\delta_k/4\), so
\[\delta_k H(\delta_{k+1})\le4\int_{\delta_{k+2}}^{\delta_{k+1}}H(u)du.\tag{24}\]\[\sum_{k=n}^\infty\delta_kH(\delta_{k+1})\le4J(\delta_{n+1})\le4J(\delta_n).\tag{25}\]\[4D\sum_{k=n}^\infty\delta_kH(\delta_{k+1})\le16D J(\delta_n).\tag{26}\]Combining (21), (23), and (26) gives
\[|Z(s)-Z(t)|\le(10D+16D)J(\delta_n)=26D J(\delta_n).\tag{27}\]and since \(d(s,t)\ge \delta_n\) by (13) and \(J(\cdot)\) is nondecreasing,
\[\begin{aligned} J(\delta_n)\le J(d(s,t)). \end{aligned}\tag{28}\]Hence on \(G\),
\[\begin{aligned} |Z(s)-Z(t)|\le 26D J(d(s,t)). \end{aligned}\tag{29}\]Define the event
\[E \equiv \left\{\exists\,s,t\in T^\ast\text{ with }d(s,t)\le \varepsilon\text{ and }|Z(s)-Z(t)|>26D J(d(s,t))\right\}.\]By (29), \(E\subseteq G^c=\cup_{i=1}^\infty A_i\), hence by (11),
\[\mathbf P\,\,\!\!(E)\le \mathbf P\,\,\!\!\left(\bigcup_{i=1}^\infty A_i\right)\le 2\varepsilon,\]which is exactly (4).
The auxiliary dense set just constructed can depend on \(\varepsilon\). To obtain one countable set for the statement, fix any countable dense \(T_0\) in advance. For each \(t\in T_0\), approximate it by points of the auxiliary set. The increment tail bound makes their process values converge to \(Z(t)\) in probability. A diagonal subsequence gives simultaneous almost-sure convergence for all \(t\in T_0\). On the good event the inequality therefore passes to every pair in \(T_0\) at distance strictly less than \(\varepsilon\); continuity of the finite integral \(J\) justifies this passage. Apply the argument with \(\varepsilon'>\varepsilon\) and let \(\varepsilon'\downarrow\varepsilon\) to include pairs at distance exactly \(\varepsilon\), retaining probability bound \(2\varepsilon\). Zero-distance pairs have equal process values almost surely by the increment assumption; countability permits this simultaneously. Thus take \(T^*=T_0\).
If the sample paths are \(d\)-continuous, the same limit argument passes from \(T_0\) to all of \(T\), again first using a radius \(\varepsilon'>\varepsilon\) to avoid a boundary issue. For measurability, the set of pairs \(\{(s,t):d(s,t)\leq\varepsilon\}\) is a separable subspace of \(T\times T\). Choose a countable dense set in this pair space. Continuity of the paths and of \(J\) makes the supremum of \(|Z(s)-Z(t)|-26DJ(d(s,t))\) equal to its supremum over those countably many pairs, outside the common continuity null set. This proves the final assertion.
This concludes the proof. ◻