Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $X_1,\dots,X_n$ denote i.i.d. standard Gaussian random variables. My question is: Do there exist absolute constants $C,c>0$ such that for every $\epsilon>0$ and positive real numbers $a_1,\dots,a_n>0$, we have the following bound

$\quad \Pr(\sum_{i=1}^n a_i X_i^2 \le \epsilon \sum_{i=1}^n a_i)\le C\epsilon^c\quad ?$

Background: Results of Carbery and Wright (2001) give powerful anti-concentration inequalities for polynomials of Gaussian variables. If we replace the term $\epsilon \sum_{i=1}^n a_i$ by $\epsilon\sqrt{\sum_{i=1}^n a_i^2}$ the bound follows directly from Carbery-Wright with $c=1/2$. Here, however, we need a stronger bound in terms of the $\ell_1$-norm rather than $\ell_2$-norm of the polynomial.

The reason why I believe the claim is still true is that all the variables $X_i$ appear squared so that there are no cancellations. Also, for $n=1$ the claim follows from simple Gaussian anti-concentration bounds with $c=1/2.$

Note: A simple application of Paley-Zygmund gives the bound $\Pr(\sum a_i X_i^2 \ge \epsilon\sum a_i )\ge (1-\epsilon)^2/3.$ This, unfortunately does not imply the statement above.

share|improve this question
    
Does the implicit constant in $O(\epsilon^c)$ allowed to depend on $n$ and $a_1,\ldots,a_n$? I assume not, but the way it's stated makes it sound like it does to me. –  George Lowther Apr 25 '12 at 0:32
    
No, it's supposed to be an absolute constant independent of $a_1,\dots,a_n$ and $n$. I will update the question. –  Mitch Apr 25 '12 at 0:56
    
Anyway, at first glance it looks like it should hold for $c=1/2$. Is that what you expect, or can you rule that case out? (certainly $c > 1/2$ is ruled out by looking at $n=1$). –  George Lowther Apr 25 '12 at 1:07
    
Yes, I would expect $c=1/2,$ but I don't want to discourage somebody with an answer that gives $c<1/2.$ –  Mitch Apr 25 '12 at 1:12

2 Answers 2

up vote 7 down vote accepted

We can show that $$ \mathbb{P}\left(\sum_ia_iX_i^2\le\epsilon\sum_ia_i\right)\le\sqrt{e\epsilon} $$ so that the inequality holds with $c=1/2$ and $C=\sqrt{e}$.

For $\epsilon\ge1$ the right hand side is greater than 1, so the inequality is trivial. I'll prove the case with $\epsilon < 1$ now. Without loss of generality, we can suppose that $\sum_ia_i=1$ (just to simplify the expressions a bit). Then, for any $\lambda\ge0$, $$ \begin{align} \mathbb{P}\left(\sum_ia_iX_i^2\le\epsilon\right)&\le\mathbb{E}\left[e^{\lambda\left(\epsilon-\sum_ia_iX_i^2\right)}\right]\cr &=e^{\lambda\epsilon}\prod_i\mathbb{E}\left[e^{-\lambda a_iX_i^2}\right]\cr &=e^{\lambda\epsilon}\prod_i\left(1+2\lambda a_i\right)^{-1/2}\cr &\le e^{\lambda\epsilon}\left(1+2\lambda\right)^{-1/2}. \end{align} $$ Take $\lambda=(\epsilon^{-1}-1)/2$ to obtain $$ \mathbb{P}\left(\sum_ia_iX_i^2\le\epsilon\right)\le e^{(1-\epsilon)/2}\sqrt{\epsilon}. $$

share|improve this answer
    
I don't think this (proof, if not the result) is correct. The first inequality in this proof looks like an incorrect application of Markov's inequality. –  Alex Gittens Nov 14 '13 at 19:44
1  
The first inequality is just taking expectations of $1_{\{\sum a_iX_i^2\le\epsilon\}}\le e^{\lambda(\epsilon-\sum a_iX_i^2)}$. –  George Lowther Nov 14 '13 at 21:38
    
Ah, yes, carry on, good sir :) –  Alex Gittens Nov 15 '13 at 22:46

I also would strongly suspect it holds with $c = 1/2$. Here's an argument which, if I haven't made a mistake, gives the upper bound $O(\epsilon^{1/2} \ln^{1/2}(1/\epsilon))$.

Assume without loss of generality that $a_1 \geq a_2 \geq \cdots \geq a_n$ and that $a_1 + \cdots + a_n = 1$. Divide into two cases:

Case 1: $a_1 \geq \frac{1}{100\log(1/\epsilon)}$. In this case it's sufficient to show that we already have $\Pr[a_1 X_1^2 \leq \epsilon] \leq O(\epsilon^{1/2} \ln^{1/2}(1/\epsilon))$. But this holds as you said because of the anticoncentration of a single Gaussian.

Case 2: $a_1 \leq \frac{1}{100\log(1/\epsilon)}$. In this case, note that $\sigma^2 := \sum_i a_i^2 \leq a_1 \sum_i a_i \leq \frac{1}{100\ln(1/\epsilon)}$. Now the random variables $X_i^2$ are nice enough that one should be able to apply a Chernoff Bound to them. (I think I could provide a source for this if necessary.) Since $Y := \sum a_i X_i^2$ has mean $1$ and standard deviation $\sqrt{2}\sigma$ (I think, maybe the constant $\sqrt{2}$ is wrong), we should have a statement like $\Pr[|Y - 1| \geq t \cdot \sqrt{2}\sigma] \leq \exp(-t^2/c)$, where $c$ is a quite modestly small universal constant. So $\Pr[Y \leq \epsilon] \leq \Pr[|Y-1| \geq 1/2] \leq \exp(-\frac{1}{8c\sigma^2}) \leq \exp(-\frac{12.5}{c} \ln(1/\epsilon)) = \epsilon^{12.5/c}$, which is smaller than $\epsilon^{1/2}$ if $c$ is not too large, and even if $c$ is too large, one can make $100$ larger.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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