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 ?

| cite | improve this question | | | | |
  • 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 '19 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 '19 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 '19 at 1:28
  • $\begingroup$ Yes indeed, and the best known one is due to Massart et al. $\endgroup$ – dohmatob Jan 7 '19 at 1:30
  • $\begingroup$ Lemma 1 of projecteuclid.org/download/pdf_1/euclid.aos/1015957395. $\endgroup$ – dohmatob Jan 7 '19 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.

| cite | improve this answer | | | | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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