0
$\begingroup$

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 ?

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

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .