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?

$\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
  • $\begingroup$ The current link in the post is to a postscript file that won't render for me. Here's a current link to a PDF: math.ias.edu/csdm/files/05-06/…. For the record their Claim 2.4 is the following. "Fix integer $\ell>0$. The distribution on sample points is $a\in_R\{0,1\}^\ell$. For all $i\in\{0,1\}^\ell\setminus\{0^\ell\}$, define $X_i(a)=\big(\sum_{j=1}^\ell a_j i_j\big) \bmod 2$. Then random variables $X_1, X_2, \ldots, X_{2^{\ell}-1}$ are uniformly distributed and pairwise independent." $\endgroup$ – Neal Young Jun 29 at 12:06
  • $\begingroup$ (continued) Now taking $n=2^\ell-1$, this is a size-$(n+1)$ sample space on $n$ 0-1 random variables. Consider the sum $\sum_{i=1}^{n} X_i$. It has expectation $n/2$. Does it obey a Chernoff-type bound? This sum is the number of subsets $S\subseteq\{1,2,\ldots,\ell\}$ such that the sum of the corresponding terms in $a$ (that is, $\sum_{j\in S} a_j$) is odd. As long as $a \ne 0^\ell$, the sum is $2^{\ell-1} = n/2+1/2$. But in the case that $a = 0^\ell$, the sum is zero. The latter case happens with probability $1/2^\ell = 1/n$, not exponentially small in $n$. No Chernoff bound holds. $\endgroup$ – Neal Young Jun 29 at 12:56
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.