Skip to main content
6 of 6
added 118 characters in body
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

For a subcollection $\mathcal S$ of $k$-element subsets of $[n]$, consider the random variable $Z_{\mathcal S} := \sup_{A \in \mathcal S}|X_A|$, where $X_A:=\sum_{i \in A}X_i$, and the $X_i$'s are iid from $N(0,1)$. Note that $X_A \sim N(0,k)$. Note that $(X_A)_A$ is a Gaussian process on $\mathcal S$ seen as a topological space. Moreover, it is a standard computation that $$ \begin{split} \mathbb E Z_{\mathcal S} &= \mathbb E \sup_{A \in \mathcal S}|X_A| \le \sqrt{2k\log|\mathcal S|} < \infty,\\ \sigma_{\mathcal S}^2 &:= \sup_{A \in \mathcal S}\mathbb E|X_A|^2 = k < \infty, \end{split} $$ where the first line is thanks to Massart's Lemma. Therefore, noting that $Z_{\mathcal S} \ge \sup_{A \in \mathcal S}X_A$, the Borell-TIS ienquality gives

$$ \begin{split} \forall u \ge 0,\; \mathbb P\left(\sup_{A \in \mathcal S}X_A \ge \sqrt{2k\log|\mathcal S|} + u\right) &\le \mathbb P(Z_{\mathcal S} \ge \sqrt{2k\log|\mathcal S|} + u)\\ &\le \mathbb P(Z_{\mathcal S} \ge \mathbb EZ_{\mathcal S} + u)\\ &\le \exp(-u^2/(2\sigma_{\mathcal S}^2))\\ & = \exp(-u^2/(2k)). \end{split} $$

To make things more interpretable, we do the the change of variable $t:=u/\sqrt{2k}$ to get $$ \mathbb P\left(\sup_{A \in \mathcal S}X_A \le \sqrt{2k}(\sqrt{\log|\mathcal S|} + t)\right) \le e^{-t^2},\forall t \ge 0. $$

In particular, if $|\mathcal S| \to 0$ as $n \to \infty$, then taking $t = \sqrt{\log |\mathcal S|}$ gives $$ \mathbb P\left(\sup_{A \in \mathcal S}X_A \le \sqrt{8k\log|\mathcal S|}\right) \le 1/|\mathcal S| \to 0. $$

dohmatob
  • 6.9k
  • 1
  • 18
  • 76