<p>Pairwise independence is not enough for a Chernoff-type bound on the expectation.</p>

<p>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)$).</p>

<p>For a reference to this sample space construction, see pages 11-12 in <a href="http://www.math.ias.edu/~avi/BOOKS/TCS003-1.ps">this survey</a>.</p>

CC BY-SA 4.0
2020-06-29T12:06:14.983Z
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: https://www.math.ias.edu/csdm/files/05-06/mluby_pairwise_independence_and_derandomization.pdf.  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."_
Neal Young
CC BY-SA 4.0
2020-06-29T12:56:43.780Z
(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.
Neal Young
CC BY-SA 2.5
2010-09-03T23:52:12.997Z
I guess it depends on what you mean by a 'chernoff-type' bound ;)
Suresh Venkat
CC BY-SA 2.5
2010-09-03T23:54:16.673Z
I mean exactly what the question asks...
Ryan Williams
CC BY-SA 2.5
2010-09-03T23:40:33.103Z
2010-09-04T00:08:36.047Z
2010-09-04T00:08:36.047Z
Ryan Williams
<p>If you have pairwise independence, then you can bound the variance of the sum, and thus get a concentration bound using Chebyshev's inequality.</p>

CC BY-SA 2.5
2010-10-07T00:56:40.560Z
But this isn't "Chernoff-type", no?
arnab
CC BY-SA 2.5
2010-10-07T14:52:41.497Z
I thought the person who asked the question might be interested in whatever concentration bounds they can get.
Dana Moshkovitz
CC BY-SA 2.5
2010-10-06T14:35:20.713Z
2010-10-06T14:35:20.713Z
Dana Moshkovitz
<p>There are all kinds of results of this kind in the <a href="http://rads.stackoverflow.com/amzn/click/0521884276">Dubhashi-Panconesi book</a>. One standard reference of this kind is the 1993 work by Schmidt, Siegel and Srinivasan titled (appropriately enough) "<a href="http://portal.acm.org/citation.cfm?id=313797">Chernoff-Hoeffding bounds for applications with limited independence</a>"</p>

CC BY-SA 2.5
2010-09-03T23:30:25.530Z
2010-09-03T23:30:25.530Z
Suresh Venkat
<p>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 <strong>pairwise independent</strong> random variables? In other words, is there a result that shows the following: the probability that a sum of <strong>pairwise independent</strong> random variables deviates from its expected value is exponentially small in the expected value and the deviation? </p>

<derandomization><pr.probability><chernoff-bound>
Chernoff-type Inequality for pair-wise independent random variables
Rahul Tripathi
# Chernoff-type Inequality for pair-wise independent random variables

(Asked by: username_0 on 2010-09-03)

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?

**Tags:** derandomization, pr.probability, chernoff-bound


---

## 3 answers

### Answer by username_1 on 2010-09-03. Score: 19

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](http://www.math.ias.edu/~avi/BOOKS/TCS003-1.ps).

> **Comments:**
> **username_3**: I guess it depends on what you mean by a 'chernoff-type' bound ;)  
> **username_1**: I mean exactly what the question asks...  
> **username_2**: 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: https://www.math.ias.edu/csdm/files/05-06/mluby_pairwise_independence_and_derandomization.pdf.  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."_  
> **username_2**: (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.  

---

### Answer by username_4 on 2010-10-06. Score: 14

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

> **Comments:**
> **username_5**: But this isn't "Chernoff-type", no?  
> **username_4**: I thought the person who asked the question might be interested in whatever concentration bounds they can get.  

---

### Answer by username_3 on 2010-09-03. Score: 12

There are all kinds of results of this kind in the [Dubhashi-Panconesi book](http://rads.stackoverflow.com/amzn/click/0521884276). 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](http://portal.acm.org/citation.cfm?id=313797)"


---

