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.



Concentration bound on maximum subset sum of standard Gaussians
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$.


