# Chernoff bound for weighted sums

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.

• 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. Jul 27, 2017 at 10:06