13
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
17
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I guess it depends on what you mean by a 'chernoff-type' bound ;) $\endgroup$ – Suresh Venkat Sep 3 '10 at 23:52
  • 1
    $\begingroup$ I mean exactly what the question asks... $\endgroup$ – Ryan Williams Sep 3 '10 at 23:54
13
$\begingroup$

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

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

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"

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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