Obtaining a lower bound on the expectation using the Sudakov-Fernique inequality

Question

In my work I wish to obtain a lower bound for the term below. Here the expectation is taken over $h$, a standard random Gaussian vector of length $n$. The minimum is taken over all $\{i_1,\dots,i_L\} \in \{1,\dots,n\}$, where $L$ is a fixed integer less than $n$. Can this be done using the Sudakov-Fernique inequality? $$ \mathbb{E}_{h} \min _{i_{1}, \ldots, i_{L}}\left[\sum_{j\neq i_1,\dots,i_L}h_j\right]. $$

Answer 1

Your question is equivalent to asking about the expectation of the max, and asking for an upper bound on the expectation of the max. You have a bunch of Gaussians $\{Y_\alpha\}_{\alpha\in I}$ indexed by a set $I$ of cardinality $M$ which equals $n$-choose-$L$. The variance of each is $n-L$, and the correlation is at least $n-2L$ (better bounds can be given if $L$ is not small compared to $n$, and in particular if $L\geq n/2$, but I'll leave that to you). Hence, $E(Y_\alpha-Y_\beta)^2\leq 2(n-L)-2(n-2L)=2L$ if $\alpha\neq \beta$. Hence, by Sudakov-Fernique, the expected maximum is bounded above by the expected maximum of a bunch of Gaussians $\{Z_\alpha\}_{\alpha\in I}$ with variance $n-L$ and pairwise covariance $n-2L$. But you can realize the $Z_\alpha$'s as $$Z_\alpha=\sqrt{n-2L} G+ \sqrt{L} W_\alpha$$ where $G$ is a standard normal and the $W_\alpha$ are iid. So the expected max of the $Z_\alpha$ is the expected max of the $\sqrt{L}W_\alpha$, ie roughly $\sqrt{2L\log M}$ (for $M$ large and $L<n/2$).