2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ In order statistics, you would ask this as: What are concentration bounds for $\sum_{i>n-k}X_{(i)}$, where $X$ is a standard normal? $\endgroup$
    – user44143
    Jan 3, 2020 at 18:01
  • $\begingroup$ It's a bit different since $\mathcal{S}$ is not all subsets of size k. I'll reword it since it's unclear. $\endgroup$ Jan 3, 2020 at 18:49
  • $\begingroup$ That makes sense. How is the family specified? The family $\{\{1,2,3,4\},\{5,6,7,8\}\}$ vs the family $\{\{4,5,6,7\},\{5,6,7,8\}\}$ would give quite different results. $\endgroup$
    – user44143
    Jan 3, 2020 at 19:09
  • $\begingroup$ Is there a lower bound on the size of S? Obviously concentration fails if S and k are small. $\endgroup$ Jan 3, 2020 at 21:13
  • $\begingroup$ Yeah, I assume |S| grows with n. I think I have a proof in this case actually, which I'll write out. $\endgroup$ Jan 3, 2020 at 23:54

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ There are much better bounds. Google "Borell-TIS inequality" $\endgroup$ Jan 4, 2020 at 0:36
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.