= Sudakov-Fernique inequality
{c}
{title2=$\mathbb E\max_iU_i\leq\mathbb E\max_iV_i$}
For centered <multivariate normal distributions>, if $\mathbb E(U_i-U_j)^2\leq\mathbb E(V_i-V_j)^2$ for every pair, then the displayed comparison holds. For a quick proof, make $U,V$ <independent> and set $Z_r=\sqrt{1-r}U+\sqrt rV$. Apply <Gaussian integration by parts> to $F_\tau(z)=\tau^{-1}\log\sum_i e^{\tau z_i}$. With <softmax function> weights $p_i$ and $D=\operatorname{Cov}(V)-\operatorname{Cov}(U)$, the derivative of $\mathbb EF_\tau(Z_r)$ is $\tfrac\tau4\mathbb E\sum_{i,j}p_ip_j(D_{ii}+D_{jj}-2D_{ij})\geq0$. Since $\max z_i\leq F_\tau(z)\leq\max z_i+\tau^{-1}\log n$, let $\tau\to\infty$. Singular <covariance matrices> follow by adding identical small <independent> <normal> noise to both vectors and taking a limit.
Back to article page
