<p><a href="http://rads.stackoverflow.com/amzn/click/0521884276" rel="noreferrer">The book by Dubhashi and Panconesi</a> collects together many such bounds, more numerous than can be listed here. If you find that hard to access immediately, there's an <a href="http://www.internetmathematics.org/volumes/3/1/ChungLu.pdf" rel="noreferrer">online  survey of Chernoff-like bounds</a> by Chung and Lu</p>

CC BY-SA 3.0
2017-03-11T09:54:22.420Z
The Chung and Lu link is dead. However, Internet Archive has it: http://web.archive.org/web/20070714095538/http://www.internetmathematics.org/volumes/3/1/ChungLu.pdf. The title is "Concentration Inequalities and Martingale Inequalities: A Survey" and the authors are Fan Chung and Linyuan Lu.
jbapple
CC BY-SA 4.0
2020-06-29T11:46:52.920Z
Current link for Chung and Liu: https://doi.org/10.1080/15427951.2006.10129115
Neal Young
CC BY-SA 2.5
2010-08-18T03:56:52.070Z
Thanks, this looks very good. In particular, Theorem 3.5 of the Chung and Lu survey seems to be identical to the Arora-Kannan lemma I was stating. Having the sum of the lambda_i^2 appear is natural since it is simply the variance of X.
Thomas
CC BY-SA 2.5
2010-08-18T03:44:48.050Z
2010-08-18T03:44:48.050Z
Suresh Venkat
<p>Consider <span class="math-container">$X = \sum_i \lambda_i Y_i^2$</span>, where <span class="math-container">$\lambda_i$</span> &gt; 0 and <span class="math-container">$Y_i$</span> is distributed as a standard normal. What kind of concentration bounds can one prove on <span class="math-container">$X$</span>, as a function of the (fixed) coefficients <span class="math-container">$\lambda_i$</span>?</p>
<p>If all the <span class="math-container">$\lambda_i$</span> are equal then this is a Chernoff bound. The only other result I am aware of is a lemma from a paper of Arora and Kannan (&quot;Learning mixtures of arbitrary Gaussians&quot;, STOC'01, Lemma 13), which proves concentration of the form <span class="math-container">$\Pr[X &lt; E[X] - t] &lt; \exp(-t^2/(4 \sum_i \lambda_i^2)$</span>, i.e., the bound depends on the sum of the squares of the coefficients.</p>
<p>The proof of their lemma is analogous to the usual proof of the Chernoff bound. Are there other &quot;canonical&quot; such bounds, or a general theory of which functions of the <span class="math-container">$\lambda_i$</span>'s are such that their largeness ensures good exponential concentration (here, the function was simply the sum of the squares)? Maybe some general measure of entropy?</p>
<p>A more standard reference for the Arora-Kannan lemma would also be great, if it exists.</p>

CC BY-SA 3.0
2017-07-27T10:06:40.540Z
How far did you get in reproducing their bound? This particular instance of the exponential mgf method seems to require some clever bounds and case analysis.
Thomas Ahle
<chernoff-bound>
Chernoff bound for weighted sums
Thomas
# Chernoff bound for weighted sums

(Asked by: username_0 on 2010-08-18)

Consider $X = \sum\_i \lambda\_i Y\_i^2$, where $\lambda\_i$ > 0 and $Y\_i$ is distributed as a standard normal. What kind of concentration bounds can one prove on $X$, as a function of the (fixed) coefficients $\lambda\_i$?

If all the $\lambda\_i$ are equal then this is a Chernoff bound. The only other result I am aware of is a lemma from a paper of Arora and Kannan ("Learning mixtures of arbitrary Gaussians", STOC'01, Lemma 13), which proves concentration of the form $\Pr[X < E[X] - t] < \exp(-t^2/(4 \sum\_i \lambda\_i^2)$, i.e., the bound depends on the sum of the squares of the coefficients.

The proof of their lemma is analogous to the usual proof of the Chernoff bound. Are there other "canonical" such bounds, or a general theory of which functions of the $\lambda\_i$'s are such that their largeness ensures good exponential concentration (here, the function was simply the sum of the squares)? Maybe some general measure of entropy?

A more standard reference for the Arora-Kannan lemma would also be great, if it exists.

**Tags:** chernoff-bound

> **Comments:**
> **username_1**: How far did you get in reproducing their bound? This particular instance of the exponential mgf method seems to require some clever bounds and case analysis.  

---

## 1 answers

### Answer by username_2 on 2010-08-18. Score: 14 | Accepted answer

[The book by Dubhashi and Panconesi](http://rads.stackoverflow.com/amzn/click/0521884276) collects together many such bounds, more numerous than can be listed here. If you find that hard to access immediately, there's an [online survey of Chernoff-like bounds](http://www.internetmathematics.org/volumes/3/1/ChungLu.pdf) by Chung and Lu

> **Comments:**
> **username_0**: Thanks, this looks very good. In particular, Theorem 3.5 of the Chung and Lu survey seems to be identical to the Arora-Kannan lemma I was stating. Having the sum of the lambda_i^2 appear is natural since it is simply the variance of X.  
> **username_3**: The Chung and Lu link is dead. However, Internet Archive has it: http://web.archive.org/web/20070714095538/http://www.internetmathematics.org/volumes/3/1/ChungLu.pdf. The title is "Concentration Inequalities and Martingale Inequalities: A Survey" and the authors are Fan Chung and Linyuan Lu.  
> **username_4**: Current link for Chung and Liu: https://doi.org/10.1080/15427951.2006.10129115  

---

