Pairwise Independence vs. Independence
March 13, 2013 Leave a comment
For collections of independent random variables, the Chernoff bound and related bounds give us very sharp concentration inequalities — if are independent, then their sum has a distribution that decays like . For random variables that are only pairwise independent, the strongest bound we have is Chebyshev’s inequality, which says that their sum decays like .
The point of this post is to construct an equality case for Chebyshev: a collection of pairwise independent random variables whose sum does not satisfy the concentration bound of Chernoff, and instead decays like .
The construction is as follows: let be independent binary random variables, and for any , let , where the sum is taken mod 2. Then we can easily check that the are pairwise independent. Now consider the random variable . If any of the is equal to 1, then we can pair up the by either adding or removing from to get the other element of the pair. If we do this, we see that in this case. On the other hand, if all of the are equal to 0, then as well. Thus, with probability , deviates from its mean by , whereas the variance of is . The bound on this probability form Chebyshev is , which is very close to , so this constitutes something very close to the Chebyshev equality case.
Anyways, I just thought this was a cool example that demonstrates the difference between pairwise and full independence.