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.

  • $\begingroup$ 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. $\endgroup$ Apr 25, 2012 at 0:32
  • $\begingroup$ No, it's supposed to be an absolute constant independent of $a_1,\dots,a_n$ and $n$. I will update the question. $\endgroup$
    – Mitch
    Apr 25, 2012 at 0:56
  • $\begingroup$ 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$). $\endgroup$ Apr 25, 2012 at 1:07
  • $\begingroup$ Yes, I would expect $c=1/2,$ but I don't want to discourage somebody with an answer that gives $c<1/2.$ $\endgroup$
    – Mitch
    Apr 25, 2012 at 1:12
  • $\begingroup$ Using Chernoff's inequality, you can get the result in one line. See my post below. $\endgroup$
    – dohmatob
    Aug 16, 2020 at 7:55

4 Answers 4


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

  • $\begingroup$ 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. $\endgroup$
    – AatG
    Nov 14, 2013 at 19:44
  • 1
    $\begingroup$ 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)}$. $\endgroup$ Nov 14, 2013 at 21:38
  • $\begingroup$ Ah, yes, carry on, good sir :) $\endgroup$
    – AatG
    Nov 15, 2013 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.


You can directly use Chernoff's inequality, to get $LHS \le e^{-\Lambda^*(\epsilon)}$, where $\Lambda^*(\epsilon) := (\epsilon-1-\log\epsilon)/2$ is the Fenchel-Legendre transform of the log-MGF $\Gamma$ of $X_1^2$ (this has been computed in this SE post). Simplifying then gives

$$ LHS \le e^{-\Lambda^*(\epsilon)} = e^{-(\epsilon-1-\log\epsilon)/2} = e^{(1-\epsilon)/2}\sqrt{\epsilon} \le \sqrt{e\epsilon}. $$


It looks like all the previous answers (including mine) are quite off by a huge margin, if the vector $a=(a_1,\ldots,a_n)$ is somewhat dense in the sense that $\|a\|_1/\|a\|_\infty$ is substantially larger than $1$. For example, if $a_i=1/n$ for all $i$, then we would expect to have the upper-bound to be of orde $\epsilon^{\Omega(n)}$, and not $\epsilon^{1/2}$. See Fact 2.1 of this blogpost.

In this post, I will provide an upper-bound which has somewhat optimal dependence on $a$.

Main tool: concentration function under affine transformation

Given a random vector $Y$ taking values in $\mathbb R^m$, its concentration function is defined by setting, for any $\epsilon \ge 0$,

$$ \mathcal L(Y,\epsilon) := \sup_{y \in \mathbb R^m} \mathcal L_y(Y,\epsilon),\text{ where }\mathcal L_y(Y, \epsilon) := \mathbb P(\|Y-y\|_2 \le \epsilon). $$

Now, let $A$ be a deterministic $m \times n$ matrix and let $X=(X_1,\ldots,X_n)$ be a random vector taking values in $\mathbb R^n$, with independent components verifying $$ \max_{1 \le i \le n}\mathcal L(X_i,\epsilon) \le \ell(\epsilon). $$ It is well-known (e.g see Theorem 1.5 of this paper by M. Rudelson) that for any $\delta \in (0,1)$, there exists a positive constant $C_\delta$ such that $$ \mathcal L(AX,\epsilon\|A\|_{HS}) \le (C_\delta \ell(\epsilon))^{(1-\delta)r(A)}, $$ where $r(A) := \|A\|_{HS}^2/\|A\|_{op}^2 \ge 1$. In particular, if the $X_i$'s have standard normal distribution, then we may take $\ell(\epsilon)=\epsilon$, and get for any $\epsilon \ge 0$ and $\delta \in (0,1)$, $$ \mathcal L(AX,\epsilon\|A\|_{HS}) \le (C_\delta \epsilon)^{(1-\delta)r(A)}. $$

Application to OP's question

In particular, taking $A$ to be the $n \times n$ diagonal matrix $\mbox{diag}(\sqrt a)$ with $a = (a_1,\ldots,a_n)$, we have

$$ \begin{split} \mathbb P(\sum_{i=1}^n a_i X_i^2 \le \epsilon \sum_{i=1}^n a_i) &= \mathbb P(\|AX\|_2 \le \sqrt\epsilon\|A\|_{HS})\\ & = \mathcal L_0(AX, \sqrt\epsilon\|A\|_{HS})\\ & \le \mathcal L(AX,\sqrt\epsilon\|A\|_{HS}) \\ &\le (C_\delta \sqrt \epsilon)^{(1-\delta)r(A)}\\ & = (C_\delta \sqrt{\epsilon})^{(1-\delta)s(a)}, \end{split} $$ where $s(a) := \|a\|_1 / \|a\|_\infty \in [1,n]$ measures the sparsity of $a$. As a sanity check, if $a_i=c > 0$ for all $i \in [n]$, then $s(a) = \|a\|_1 / \|a\|_\infty = n$, and our upper-bound above recovers the correct order in $\epsilon$, namely $\epsilon^{\Omega(n)}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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