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

Question

(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)$).

Answer 1

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.

Answer 2

$\newcommand{\E}{\mathbb{E}} \renewcommand{\P}{\mathbf{P}} \DeclareMathOperator{\var}{Var}$ There is a simple explanation in this specific case.

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\})$.

Answer 3

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).\tag{$*$}$$ 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.

Answer 4

Claim: if $X_1=X_2=1 \Rightarrow X_3=X_4=1$ holds then $X_3\ne X_4 \Rightarrow X_1=X_2=0$.

Indeed, by pairwise independence, $$ E\Big[ X_1\Big(\frac{X_3+X_4}{2} - X_2\Big) + X_2\Big(\frac{X_3+X_4}{2} - X_1\Big) \Big] =0 $$ and if additionally $X_1=X_2=1 \Rightarrow X_3=X_4=1$ then both terms inside the expectation are non-negative. Under $X_1=X_2=1 \Rightarrow X_3=X_4=1$ both terms are identically 0, which in turn gives $X_3\ne X_4 \Rightarrow X_1=X_2=0$. The claim is proved.

The "then" part of the claim cannot hold due to $P(X_3\ne X_4)=1/2$ and $P(X_1=X_2=0)=1/4$.

Essentially, we try to find a polynomial of order 2 (whose expectation can be computed by pairwise independence) that is always non-negative.