Pairwise Independence vs. Independence

For collections of independent random variables, the Chernoff bound and related bounds give us very sharp concentration inequalities — if X_1,\ldots,X_n are independent, then their sum has a distribution that decays like e^{-x^2}. For random variables that are only pairwise independent, the strongest bound we have is Chebyshev’s inequality, which says that their sum decays like \frac{1}{x^2}.

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 \frac{1}{x^2}.

The construction is as follows: let X_1,\ldots,X_d be independent binary random variables, and for any S \subset \{1,\ldots,d\}, let Y_S = \sum_{i \in S} X_i, where the sum is taken mod 2. Then we can easily check that the Y_S are pairwise independent. Now consider  the random variable Z = \sum_{S} Y_S. If any of the X_i is equal to 1, then we can pair up the Y_S by either adding or removing i from S to get the other element of the pair. If we do this, we see that Z = 2^{d-1} in this case. On the other hand, if all of the X_i are equal to 0, then Z = 0 as well. Thus, with probability \frac{1}{2^d}, Z deviates from its mean by 2^{d-1}-\frac{1}{2}, whereas the variance of Z is 2^{d-2}-\frac{1}{4}. The bound on this probability form Chebyshev is \frac{2^{d-2}-1/4}{(2^{d-1}-1/2)^2}, which is very close to \frac{1}{2^d}, 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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: