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?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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.
answered Sep 3 '10 at 23:40
-
$\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
$\begingroup$
$\endgroup$
If you have pairwise independence, then you can bound the variance of the sum, and thus get a concentration bound using Chebyshev's inequality.
answered Oct 6 '10 at 14:35
-
4
-
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
$\begingroup$
$\endgroup$
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"
answered Sep 3 '10 at 23:30
