Concentration bound on maximum subset sum of standard Gaussians

Question

Let $X_1, \dots, X_n$ be standard Gaussians. Let $\mathcal{S} \subseteq \{A \in 2^{\{1, \dots, n\}} : |A| = k\} $ be a family of subsets of $\{1,\dots, n\}$ with fixed size $k$. [Note that $\mathcal{S}$ may be smaller than $\{A \in 2^{\{1, \dots, n\}} : |A| = k\}$, the set of all subsets with fixed size $k$.]

Let $Y = \max_{A \in \mathcal{S}} \sum_{i \in A} X_i$. Are there any known concentration bounds on $Y$? I have the bound $E[Y] \leq \sqrt{2k\log{|\mathcal{S}|}}$, and I want to say something like "We have $Y < 10 \sqrt{k \log{|\mathcal{S}|}}$ with high probability".

I tried using Chebyshev with the bound $\text{Var}(\max Z_i) \leq \sum \text{Var}(Z_i)$, but that yields $\text{Var}(Y) \leq O(k |\mathcal{S}|)$ which is too weak.

Answer 1

Claim: If $|\mathcal{S}| \to \infty$ as $n\to \infty$, then $Y \leq \sqrt{2k\log{|\mathcal{S}|}}$ with high probability.

Proof: Let $t = \sqrt{2k\log{|\mathcal{S}|}}$. By union bound, we have

$P(Y > t) \leq \sum_{A \in \mathcal{S}} P(\sum_{i \in A} X_i > t) = |\mathcal{S}| \cdot P(N(0,k) > t)$.

Plugging in $t$ and simplifying yields $P(Y > t) \leq |\mathcal{S}| \cdot P(N(0,1) > \sqrt{2\log{|\mathcal{S}|}})$.

Using the bound here (https://www.johndcook.com/blog/norm-dist-bounds/) yields $P(Y > t) \leq \frac{1}{\sqrt{2\pi}}\cdot \frac{1}{\sqrt{2\log{|\mathcal{S}|}}}$, which goes to $0$ as $n \to\infty$.

Answer 2

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. $$