# Is there a good explanation for this fact on pairwise independent variables?

(related question : most general way to generate pairwise independent random variables?)

Let $X_1,X_2,X_3,X_4$ be four random variables with standard Bernoulli distribution (i.e. $P(X_i=0)=P(X_i=1)=\frac{1}{2}$ for $1 \leq i \leq 4$) and such that any two of those four variables are independent.

Then the fourtuple $\overrightarrow{X}=(X_1,X_2,X_3,X_4)$ takes at least one of the three values $(0,0,0,0),(0,0,0,1)$ or $(0,0,1,0)$ with positive probability.

This surprising fact can be shown by brute force: what we have is essentially a system of linear equalities and inequalities in 16 variables corresponding to the distribution of $\overrightarrow{X}$. The proof is straightforward but not very illuminating. Are there better explanations?

UPDATE 22:15 Actually, the following stronger property holds : for any $(a,b,c,d)$ in $\lbrace 0,1 \rbrace ^4$, the event $(X_1,X_2)=(a,b) \Rightarrow (X_3,X_4)=(c,d)$ has probability $<1$ (in this sense, $(X_3,X_4)$ cannot be "dependent" on $(X_1,X_2)$).

-
What is the third value? – Stanley Yao Xiao Jun 2 '11 at 14:46
@Stanley Yao Xiao : The third value is (0,0,1,0), do you have trouble reading it on your screen? – Ewan Delanoy Jun 2 '11 at 16:08
I deleted my answer for now since it was wrong, and I didn't see how to salvage it. – Nate Eldredge Jun 2 '11 at 18:12
@Nate : why was it wrong? – Ewan Delanoy Jun 2 '11 at 18:15
@Michael Hardy: I think the desired conclusion could be written as $P(\vec{X} \in \{(0,0,0,0), (0,0,0,1), (0,0,1,0) \} ) > 0$. – Nate Eldredge Jun 2 '11 at 18:15

This solution is ugly, sorry.

Proceed by contradiction and assume that 0000, 0001 and 0010 all have probability zero. Every event where one specifies two coordinates and one leaves free the two remaining ones has probability exactly 1/4 because this event involves only the joint distribution of two independent Bernoulli random variables. Write N for an unspecified 0 or 1. Then, for example 00NN has probability 1/4, hence 0011 has probability 1/4 because 00NN is the disjoint union of 0000, 0001, 0010 and 0011.

Likewise : comparing 0011 and NN11, this shows that 0111, 1011 and 1111 have probability zero; comparing 0011 and 0N1N, this shows that 0110 has probability zero; comparing 0011 and N0N1, this shows that 1001 has probability zero; comparing 0011 and N01N, this shows that 1010 has probability zero; and comparing 0011 and 0NN1, this shows that 0101 has probability zero.

Hence we know that 0011 has probability 1/4 and that the rest of the mass is concentrated on 0100, 1000, 1100, 1101 and 1110. But the three first points are all in NN00 hence the sum of their probabilities is at most 1/4. Likewise the two last points are in 11NN hence the sum of their probabilities is at most 1/4. The total mass of the measure is at most 3/4, which is absurd.

In the end, the result is that none of the 16 points may have probability 1/4: otherwise every point in any same plane than this heavy point has probability zero; this leaves only two planes, each with probability at most 1/4, to spend a total mass of 3/4 on.

Edit The condition in the update is equivalent to the condition that none of the 16 points has mass 1/4.

-
In fact, with some linear programming, I managed to find a sharp bound: the most mass that any one point can have is 1/6. If there were a nice proof of this, it would be very interesting! – Nate Eldredge Jun 2 '11 at 21:25
It isn't hard but a bit boring. I'll assume that the point is 0000 and denote by q the set where Q=1. Take x of measure 1/2. xy,xz,xt are contained in x and have measure 1/4 each. PIE shows that one of their intersections, say xyz, is of measure at least 1/12, so WLOG x has the piece of measure 1/12 or more free of y and z. But y and z together give 3/4 and 3/4+1/12=5/6. – fedja Jun 3 '11 at 3:41


Your condition is equivalent to $\P(X=0011)=\frac14$. But for any point we cannot have $\P(X=a)=\frac14$. Let's pick $a=1111$ WLOG. Let $S=\sum_i X_i$. Then $\E(S)=2$ and $\var(S)=1$. But then $\P(S=4)=\frac14$ already contributes 1 to the variance and the other values must also have positive contribution giving a contradiction.

I didn't bother calculating the lower bound for $\P(X \in \{0000, 0001, 0010\})$.

-
Elaborating on this: If we have 0000 with probability $a$, then E[X1+X2+X3+X4]=2, EE[(X1+X2+X3+X4)^2]=5, so, by Cauchy 5(1-a)\ge 4 and a\le 1/5. Probably, that is not tight, but it is good enough. – fedja Jun 2 '11 at 22:27

I don't know if this explanation is better than any other, but here is how I thought about it.

To simplify my notation, let me denote the variables by X, Y, U, and V, and denote n-tuples by juxtaposition. (E.g., "XY = 01" means "(X,Y) = (0,1)".)

First, we have that the variables are pairwise independent 1/2-Bernoulli's. We begin by observing that under this assumption, $$P(U=1\mid XY=00) = P(U=0\mid XY=01).\qquad(*)$$ To see this, we write

\begin{align} \textstyle{\frac12}&=P(U=1\mid X=0)\\\\ &= P(UY=10\mid X=0) + P(UY=11\mid X=0)\\\\ &= P(Y=0\mid X=0)P(U=1\mid XY=00)\\\\ &\qquad + P(Y=1\mid X=0)P(U=1\mid XY=01)\\\\ &= \textstyle{\frac12}P(U=1\mid XY=00) + \textstyle{\frac12}P(U=1\mid XY=01)\\\\ &= \textstyle{\frac12}P(U=1\mid XY=00) + \textstyle{\frac12} - \textstyle{\frac12}P(U=0\mid XY=01), \end{align}

which gives us (*).

Now, to obtain a contradiction, let us assume that $P(UV=11\mid XY=00) = 1$. Then, by (*), we have $P(UV=00\mid XY=01)=1$. Thus, $P(U=V\mid X=0)=1$. Similarly, $P(U=V\mid Y=0)=1$. Hence, $P(U=V\mid X=0\text{ or }Y=0)=1$, which implies $$P(U=V)\ge P(X=0\text{ or }Y=0).$$ But X, Y, U, and V are pairwise independent 1/2-Bernoulli's, so $P(U=V)=1/2$ and $P(X=0\text{ or }Y=0)=3/4$, and so we have a contradiction.

-