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


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)$ ?


  • 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 ?

  • 1
    $\begingroup$ 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. $\endgroup$ – Nate Eldredge Jan 7 at 1:22
  • $\begingroup$ 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) :) $\endgroup$ – dohmatob Jan 7 at 1:24
  • 1
    $\begingroup$ 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$. $\endgroup$ – Nate Eldredge Jan 7 at 1:28
  • $\begingroup$ Yes indeed, and the best known one is due to Massart et al. $\endgroup$ – dohmatob Jan 7 at 1:30
  • $\begingroup$ Lemma 1 of projecteuclid.org/download/pdf_1/euclid.aos/1015957395. $\endgroup$ – dohmatob Jan 7 at 1:32

As pointed out by a user (Nate Eldgredge) in the comments under the question,

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


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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