Gaussian Comparison and Sudakov’s Inequality

A Gaussian maximum depends on the covariance between its coordinates. Gaussian interpolation varies that covariance continuously, and integration by parts expresses the derivative of an expectation using second derivatives. For suitable smooth approximations to a maximum, the sign of this derivative is determined by increment variances. This gives comparison inequalities and, by comparison with independent variables, Sudakov’s lower bound.

Here we use Gaussian integration by parts to compare expectations under different covariance structures. Recall the definition and basic bounds for centred Gaussian processes.

Throughout, Gaussian vectors and processes are centered. Without centering, even a singleton index set with different means contradicts the expected-supremum comparison. For infinite index sets we interpret expected suprema as suprema of finite-dimensional expected maxima. For a separable process this agrees with the ordinary expected supremum, in the extended sense: fix one index, subtract its integrable coordinate, and apply monotone convergence to nonnegative finite maxima.

Interpolation uses independent copies \(X,Y\) and \(Z(u)=\sqrt uX+\sqrt{1-u}Y\). Independence can always be imposed because the comparisons concern the two marginal laws.

Lemma 1 (Gaussian integration by parts). If \(G\sim \mathcal{N}(0,1)\), \(f\) is continuously differentiable, and \(f,f'\) have at most polynomial growth, then \(\mathbb Ef'(G)=\mathbb E[Gf(G)]\).

Proof. Since \(\phi'(x)=-x\phi(x)\), integration by parts gives

\[\int f'(x)\phi(x)\,dx=[f(x)\phi(x)]_{-\infty}^{\infty}-\int f(x)\phi'(x)\,dx=\int xf(x)\phi(x)\,dx.\]

Polynomial growth kills the boundary term and makes both integrals absolutely convergent. More generally the same identity holds for locally absolutely continuous \(f\) whenever the relevant integrals and vanishing boundary term are justified; arbitrary differentiability alone does not ensure this. ◻

Lemma 2 (Multivariate integration by parts). Let \(X\sim \mathcal{N}(0,\Sigma)\), allowing singular \(\Sigma\), and let \(f:\mathbb R^n\to\mathbb R\) be continuously differentiable with \(f\) and its first derivatives of polynomial growth. Then

\[\mathbb E[X_if(X)]=\sum_j\Sigma_{ij}\mathbb E[\partial_jf(X)].\]

Proof. Write \(X=AG\) with \(G\) standard normal and \(AA^\top=\Sigma\). Conditional univariate integration by parts and the chain rule give

\[\mathbb E[G_kf(AG)]=\sum_j A_{jk}\mathbb E[\partial_jf(AG)].\]

Multiply by \(A_{ik}\) and sum over \(k\). The coefficient becomes \(\sum_kA_{ik}A_{jk}=\Sigma_{ij}\). Gaussian moments justify conditioning and integration; no inverse covariance is used. ◻

Lemma 3 (Gaussian interpolation). Let \(X,Y\) be independent centered Gaussian vectors with covariances \(\Sigma^X,\Sigma^Y\). If \(f:\mathbb R^n\to\mathbb R\) is \(C^2\), with itself and its first two derivatives of polynomial growth, then for \(0<u<1\),

\[\frac d{du}\mathbb Ef(Z(u))=\frac12\sum_{i,j}(\Sigma^X_{ij}-\Sigma^Y_{ij})\mathbb E[\partial_{ij}f(Z(u))].\]

Proof. On each closed subinterval of \((0,1)\), polynomial domination permits differentiation under expectation:

\[\frac d{du}\mathbb Ef(Z(u))=\frac12\sum_i\mathbb E\left[\partial_if(Z(u))\left(\frac{X_i}{\sqrt u}-\frac{Y_i}{\sqrt{1-u}}\right)\right].\]

Condition on \(Y\) and apply Lemma 2 to the function \(x\mapsto\partial_if(\sqrt ux+\sqrt{1-u}Y)\). Its \(j\)th derivative is \(\sqrt u\partial_{ij}f\), so

\[\mathbb E[X_i\partial_if(Z(u))]=\sqrt u\sum_j\Sigma^X_{ij}\mathbb E[\partial_{ij}f(Z(u))].\]

Conditioning instead on \(X\) gives the corresponding factor \(\sqrt{1-u}\) for the \(Y_i\) term. Substitution cancels both denominators. The Hessian expression is uniformly integrable up to \(u=0,1\), by polynomial growth and Gaussian moments, and the endpoint expectations are continuous. Integrating on \([a,b]\subset(0,1)\) and then letting \(a\downarrow0,b\uparrow1\) therefore compares the endpoints. ◻

1. Slepian’s inequality

The distributional comparison needs equal coordinate variances. The comparison of expected maxima below only needs ordered increment variances.

Lemma 4. Suppose \(\Sigma^X_{ii}=\Sigma^Y_{ii}\) and \(\mathbb E(X_i-X_j)^2\le\mathbb E(Y_i-Y_j)^2\). For a function satisfying Lemma 3 and \(\partial_{ij}f\ge0\) when \(i\ne j\), we have \(\mathbb Ef(X)\ge\mathbb Ef(Y)\).

Proof. The increment inequality and equal diagonal entries imply \(\Sigma^X_{ij}\ge\Sigma^Y_{ij}\). The diagonal terms in the interpolation derivative vanish, and every off-diagonal term is nonnegative. Integrate the derivative from the \(Y\) endpoint to the \(X\) endpoint. ◻

Theorem 5 (Slepian). Under Lemma 4's covariance assumptions, for every real \(t\),

\[P(\max_iX_i\ge t)\le P(\max_iY_i\ge t).\]

Proof. Choose a smooth nonincreasing \(H:\mathbb R\to[0,1]\) equal to one on \(( -\infty,-1]\) and zero on \([0,\infty)\). Put \(h_m(x)=H(m(x-t))\) and \(f_m(x)=\prod_i h_m(x_i)\). For \(i\ne j\),

\[\partial_{ij}f_m(x)=h_m'(x_i)h_m'(x_j)\prod_{k\ne i,j}h_m(x_k)\ge0.\]

Lemma 4 applies to each \(m\). Since \(h_m(x)\to\mathbf1\{x<t\}\) at every \(x\), including \(x=t\), bounded convergence gives \(P(\max_iX_i<t)\ge P(\max_iY_i<t)\). Taking complements proves the claim. This one-sided smoothing handles degenerate coordinates and possible atoms without an unstated continuity assumption. ◻

Theorem 6 (Sudakov–Fernique, also called Slepian–Fernique). For centered Gaussian processes, suppose

\[\mathbb E(X_t-X_s)^2\ge\mathbb E(Y_t-Y_s)^2\qquad(s,t\in T).\]

Then \(\mathbb E\sup_tX_t\ge\mathbb E\sup_tY_t\), with the finite-dimensional supremum convention above.

Proof. First restrict to \(n\) indices. For \(\alpha>0\), the smooth maximum

\[f_\alpha(x)=\alpha^{-1}\log\sum_i e^{\alpha x_i}\]

satisfies \(0\le f_\alpha(x)-\max_ix_i\le(\log n)/\alpha\). Let \(p_i=e^{\alpha x_i}/\sum_j e^{\alpha x_j}\). Then \(\partial_if_\alpha=p_i\) and \(\partial_{ij}f_\alpha=\alpha(\delta_{ij}p_i-p_ip_j)\). These derivatives are bounded for fixed \(\alpha\), and \(f_\alpha\) has linear growth, so Lemma 3 applies. For every symmetric matrix \(\Sigma\),

\[\begin{aligned}\sum_{i,j}\Sigma_{ij}(\delta_{ij}p_i-p_ip_j)&=\sum_i\Sigma_{ii}p_i-\sum_{i,j}\Sigma_{ij}p_ip_j\\&=\frac12\sum_{i,j}(\Sigma_{ii}+\Sigma_{jj}-2\Sigma_{ij})p_ip_j,\end{aligned}\]

where the second equality uses \(\sum_jp_j=1\) in each diagonal term. Consequently,

\[\frac d{du}\mathbb Ef_\alpha(Z(u))=\frac\alpha4\sum_{i,j}\left[\mathbb E(X_i-X_j)^2-\mathbb E(Y_i-Y_j)^2\right]\mathbb E[p_i(Z(u))p_j(Z(u))]\ge0.\]

Integration compares the two smooth maxima. Their deterministic approximation error is at most \((\log n)/\alpha\), so expectation also converges as \(\alpha\to\infty\). This proves the finite-set result. Taking suprema over all finite subsets proves the general statement. For separable versions, take a common countable determining set and apply monotone convergence after subtracting one coordinate, as described above. ◻

2. Sudakov’s minorization inequality

The comparison with independent Gaussian variables now converts metric separation into a lower bound.

Theorem 7 (Sudakov minorization). For a nonempty centered Gaussian process, put \(d(s,t)^2=\mathbb E(X_s-X_t)^2\). For every \(\varepsilon>0\),

\[c\varepsilon\sqrt{\log N(\varepsilon,T,d)}\le\mathbb E\sup_{t\in T}X_t.\]

Proof. For any finite \(\varepsilon\)-separated family \(t_1,\ldots,t_m\), compare \(X_{t_i}\) with \(Y_i=(\varepsilon/\sqrt2)g_i\), where the \(g_i\) are independent standard normals. Their increment variances are \(\varepsilon^2\), so Theorem 6 and the independent-maximum lower bound give

\[\mathbb E\sup_tX_t\ge(\varepsilon/\sqrt2)\mathbb E\max_{i\le m}g_i\ge c\varepsilon\sqrt{\log m}.\]

A greedy selection either stops at a maximal separated family, which covers \(T\) at radius \(\varepsilon\), or yields arbitrarily large finite separated families. In the first case \(m\ge N(\varepsilon,T,d)\). In the second the expected supremum is infinite. This proves the result without assuming existence of a finite maximal packing. Covering conventions using strict balls can be handled by first changing the radius by an arbitrarily small factor. ◻

Remark 8 (The \(\ell^1\) ball). For \(T=B_1^d\), the process \(X_t=\langle g,t\rangle\) has Euclidean canonical metric and

\[\mathbb E\sup_{t\in B_1^d}\langle g,t\rangle=\mathbb E\max_{i\le d}|g_i|\le\sqrt{2\log(2d)}.\]

Indeed, exponential Markov and the Gaussian mgf bound the mean maximum by \(\log(2d)/\lambda+\lambda/2\), minimized at \(\lambda=\sqrt{2\log(2d)}\). Sudakov therefore gives

\[\log N(\varepsilon,B_1^d,\|\cdot\|_2)\le\frac{C\log(2d)}{\varepsilon^2}.\]

There is no extra factor \(\varepsilon\) on the upper bound for the width. The \(2d\) also covers \(d=1\). Compare this estimate with the volumetric bound and use whichever is smaller at the desired scale.

Theorem 9. Let \(T\subset\mathbb R^d\) be nonempty and bounded, \(d\ge1\). Define \(s(T)=\sup_{\varepsilon>0}\varepsilon\sqrt{\log N(\varepsilon,T,\|\cdot\|_2)}\) and \(w(T)=\mathbb E\sup_{t\in T}\langle g,t\rangle\). Then

\[cs(T)\le w(T)\le C\log(2d)\,s(T).\]

Proof. The lower bound is Theorem 7. If the diameter \(D\) is zero, both sides vanish. Otherwise two points at distance approaching \(D\) show \(N(D/3,T)\ge2\), hence \(s(T)\ge(D/3)\sqrt{\log2}\). Fix \(t_0\in T\), set \(r_k=D2^{-k}\), and take finite \(r_k\)-nets with maps \(\pi_k\); let \(\pi_0t=t_0\). A net may be chosen with at most \(N(r_k,T)\) centers (or with an arbitrarily small radius enlargement). The increments at level \(k\) have standard deviations at most \(r_k+r_{k-1}=3r_k\), and at most \(N(r_k,T)N(r_{k-1},T)\) possible pairs. The finite Gaussian maximum bound, applied to both signs, yields

\[\mathbb E\sup_t|\langle g,\pi_kt-\pi_{k-1}t\rangle|\le Cr_k\sqrt{\log(2N(r_k,T)N(r_{k-1},T))}\le C's(T).\]

For the last inequality use monotonicity of covering numbers, \(r_k\sqrt{\log N(r_k,T)}\le s(T)\), and \(r_k\le D\lesssim s(T)\). The telescoping identity and Cauchy–Schwarz then give, for every integer \(K\ge1\),

\[w(T)\le C K s(T)+r_K\mathbb E\|g\|_2\le C K s(T)+D2^{-K}\sqrt d.\]

Here the initial term has mean \(\mathbb E\langle g,t_0\rangle=0\); the supremum of a sum is bounded by the sum of suprema, not equal to it. Choose \(K=\max\{1,\lceil\log_2\sqrt d\rceil\}\). The residual is at most \(D\lesssim s(T)\), and \(K\lesssim\log(2d)\). This proves the upper bound with all scale factors retained. If \(T\) is unbounded, arbitrarily distant pairs already force the extended width and \(s(T)\) to be infinite; the bounded formulation avoids undefined products at zero radius. ◻