# Chernoff-type Inequality for pair-wise independent random variables

Chernoff-type inequalities are used to show that the probability that a sum of independent random variables deviates significantly from its expected value is exponentially small in the expected value and the deviation. Is there a Chernoff-type inequality for any sum of pairwise independent random variables? In other words, is there a result that shows the following: the probability that a sum of pairwise independent random variables deviates from its expected value is exponentially small in the expected value and the deviation?

Pairwise independence is not enough for a Chernoff-type bound on the expectation.

This follows from the fact that there are $poly(n)$-size sample spaces on $n$ 0-1 random variables, where all the variables are pairwise independent, and each is variable is uniform (it is $1$ with probability $1/2$). So the expected value of their sum is $n/2$. But because there are only $poly(n)$ possible events in the sample space, even the probability that a sum is exactly a particular value $v$ is at least $1/poly(n)$ (hence, it can't be at most $1/exp(n)$).

For a reference to this sample space construction, see pages 11-12 in this survey.

• I guess it depends on what you mean by a 'chernoff-type' bound ;) – Suresh Venkat Sep 3 '10 at 23:52
• I mean exactly what the question asks... – Ryan Williams Sep 3 '10 at 23:54

If you have pairwise independence, then you can bound the variance of the sum, and thus get a concentration bound using Chebyshev's inequality.

• But this isn't "Chernoff-type", no? – arnab Oct 7 '10 at 0:56
• I thought the person who asked the question might be interested in whatever concentration bounds they can get. – Dana Moshkovitz Oct 7 '10 at 14:52

There are all kinds of results of this kind in the Dubhashi-Panconesi book. One standard reference of this kind is the 1993 work by Schmidt, Siegel and Srinivasan titled (appropriately enough) "Chernoff-Hoeffding bounds for applications with limited independence"