# Anti-concentration: upper bound for $P(\sup_{a \in \mathbb S_{n-1}}\sum_{i=1}^na_i^2Z_i^2 \ge \epsilon)$

Let $$\mathbb S_{n-1}$$ be the unit sphere in $$\mathbb R^n$$ and $$z_1,\ldots,z_n$$ be a i.i.d sample from $$\mathcal N(0, 1)$$.

# Question

Given $$\epsilon > 0$$ (may be assumed to be very small), what is a reasonable upper bound for the tail probability $$P(\sup_{a \in \mathbb S_{n-1}}\sum_{i=1}^na_i^2z_i^2 \ge \epsilon)$$ ?

# Observations

• Using ideas from this other answer (MO link), one can establish the non-uniform anti-concentration bound: $$P(\sum_{i=1}^na_i^2z_i^2 \le \epsilon) \le \sqrt{e\epsilon}$$ for all $$a \in \mathbb S_{n-1}$$.

• The uniform analogue is another story. May be one can use covering numbers ?

• Doesn't $\sup_{a \in \mathbb S_{n-1}}\sum_{i=1}^na_i^2Z_i^2 = \max_{1 \le i \le n} Z_i^2$? So this question is really just about the largest order statistic of a $\chi^2$ sample. – Nate Eldredge Jan 7 '19 at 1:22
• Thanks @NateEldredge. 1 or 2 minutes ago, I came up a similar understanding of the problem (after liking it to best response strategy, or max of linear form over probability simplex) :) – dohmatob Jan 7 '19 at 1:24
• It also tells you that the probability is $1 - F(\epsilon)^n$ where $F$ is the cdf of $\chi^2$ with 1 degree of freedom. And there should be plenty of good bounds for $F$. – Nate Eldredge Jan 7 '19 at 1:28
• Yes indeed, and the best known one is due to Massart et al. – dohmatob Jan 7 '19 at 1:30
• – dohmatob Jan 7 '19 at 1:32

$$P\left(\sup_{a \in \mathbb S_{n-1}}\sum_{i=1}^n a_i^2Z_i^2 \ge \epsilon\right) = P\left(\max_{1 \le i \le n}Z_i^2 \ge \epsilon\right) = 1-P(Z_1^2 \le \epsilon)^n = 1-P(\chi^2 \le \epsilon)^n.$$ One can then invoke standard tail bounds for chi-squared variables (e.g exponential-type tail bound established in Lemma 1 of this paper), to finish the problem.