Why Pairwise Checks Are Not Enough
For a finite family, checking every pair is a practical way to establish pairwise independence. But those checks do not, by themselves, establish that the whole family is mutually independent. A particularly clear counterexample uses only three binary random variables: their joint law is concentrated on outcomes satisfying a parity constraint. Each pair looks like two independent fair bits, while the three variables together obey a deterministic rule.
The construction is useful because every claim can be checked directly from one small joint probability table. The table will show precisely what pairwise checks establish—and what they leave undetected.
The Even-Parity Construction
Let the sample space consist of four equally likely outcomes, \(\Omega=\{00,01,10,11\}\). Define \(X\) as the first bit and \(Y\) as the second bit. Set \(Z=0\) when the two bits agree, and \(Z=1\) when they differ. Equivalently, \(Z=X\oplus Y\), where \(\oplus\) denotes addition modulo 2. Thus \(X\oplus Y\oplus Z=0\): the three bits have even parity.
The four outcomes for \((X,Y)\) each have probability \(1/4\). The definition of \(Z\) then gives the following joint probability mass function.
| \(x\) | \(y\) | \(z\) | \(P(X=x,Y=y,Z=z)\) |
|---|---|---|---|
| 0 | 0 | 0 | \(1/4\) |
| 0 | 1 | 1 | \(1/4\) |
| 1 | 0 | 1 | \(1/4\) |
| 1 | 1 | 0 | \(1/4\) |
| All other triples | 0 |
Worked Example: Check the Marginals and Pair Tables
First sum the joint probabilities over values not included in a marginal. For \(X\), the two rows with \(x=0\) have total probability \(1/4+1/4=1/2\), and the two rows with \(x=1\) also have total \(1/2\). The table is symmetric in \(X,Y,Z\), so the same calculation gives
For the pair \((X,Y)\), sum over \(z\). Each bit pair occurs in exactly one row of probability \(1/4\), so \(P(X=x,Y=y)=1/4\) for all four choices of \((x,y)\). The pair table is
| \(X\backslash Y\) | 0 | 1 |
|---|---|---|
| 0 | \(1/4\) | \(1/4\) |
| 1 | \(1/4\) | \(1/4\) |
For \((X,Z)\), the supported rows give the pairs \((0,0),(0,1),(1,1),(1,0)\), each once. Hence \(P(X=x,Z=z)=1/4\) for every \((x,z)\). For \((Y,Z)\), the four supported rows likewise give \((0,0),(1,1),(0,1),(1,0)\), each once, so \(P(Y=y,Z=z)=1/4\) for every \((y,z)\). In each pair table, every entry equals the product of the marginal probabilities, \( (1/2)(1/2)=1/4\). Thus all three pairs are independent.
The Triple Does Not Factor
The same joint table rules out mutual independence. If \(X,Y,Z\) were mutually independent, the probability of \((0,0,0)\) would be the product of its three marginal probabilities. But this triple is one of the four supported outcomes, so its joint probability is \(1/4\), whereas the product of the marginals is \( (1/2)^3=1/8\). Since those values differ, the triple does not factor.
The pairwise part follows because each pair table has four entries equal to \(1/4\), and each variable has marginal probabilities \(1/2\) at both values. For the mutual-independence part, the single triple \((0,0,0)\) already violates the required factorization:
This proves the theorem: the pairwise factorization conditions all hold, but the three-variable factorization condition does not. \(\square\)
Worked Example: Find the Deterministic Constraint
Although each pair has all four possible values with probability \(1/4\), the joint table contains only four of the eight possible triples. In each supported row, \(z\) is determined by \(x\) and \(y\): \(z=x\oplus y\). For example, if \(x=0\) and \(y=1\), only \(z=1\) occurs. In fact,
This certainty about the triple does not contradict the pairwise checks. A pair table sums out the third coordinate, and after that summation each of the four pair values has probability \(1/4\). The parity rule is a constraint on all three coordinates together; it is not visible as a failure of any one pair table.
Flipping Labels Preserves the Construction
The example is not tied to the particular choice of which value is called 0. Flipping any of the binary labels produces another joint law with the same pattern of pairwise independence and failure of mutual independence. The next result states this precisely.
For any fixed \(a\), the map \(x\mapsto x\oplus a\) is a bijection of \(\{0,1\}\). Therefore \(P(U=u)=P(X=u\oplus a)=1/2\); the same holds for \(V\) and \(W\). For any \(u,v\), there is exactly one corresponding pair \(x=u\oplus a,\ y=v\oplus b\), so
The same argument applies to the other two pairs. For the triple, the map from \((X,Y,Z)\) to \((U,V,W)\) is also a bijection, so each supported triple still has probability \(1/4\), and every unsupported triple still has probability 0. In particular, \(U,V,W\) have only four supported triples, while mutual independence with three fair marginals would assign probability \(1/8\) to each of the eight triples. Thus they are not mutually independent. \(\square\)
Worked Example: An Odd-Parity Version
Flip the label of \(Z\), setting \(W=1-Z\), while leaving \(X\) and \(Y\) unchanged. The transformed table is
| \(x\) | \(y\) | \(w\) | \(P(X=x,Y=y,W=w)\) |
|---|---|---|---|
| 0 | 0 | 1 | \(1/4\) |
| 0 | 1 | 0 | \(1/4\) |
| 1 | 0 | 0 | \(1/4\) |
| 1 | 1 | 1 | \(1/4\) |
| All other triples | 0 |
Every pair still takes each of its four possible values once in the table, so every pair probability is \(1/4\). Each one-variable marginal is still \(1/2\) at 0 and at 1; hence every pair factors into its marginals. But \(P(X=0,Y=0,W=0)=0\), while \(P(X=0)P(Y=0)P(W=0)=1/8\). This version satisfies \(X\oplus Y\oplus W=1\) with probability 1, illustrating the same distinction using odd parity.
A Sign-Coded View
Worked Example: Convert the Bits to Signs
From the even-parity bits, define \(A=(-1)^X\), \(B=(-1)^Y\), and \(C=(-1)^Z\). Each sign is \(+1\) or \(-1\), with probability \(1/2\) at either value. Because the maps from bits to signs are one-to-one, each pair of signs has four possible values, each with probability \(1/4\); hence every pair is independent.
The parity constraint also gives a fixed product:
for every supported outcome. For example, \(P(A=1,B=1,C=1)=1/4\), since this corresponds to the supported bit triple \((0,0,0)\). If the three signs were mutually independent, that probability would be \((1/2)^3=1/8\). The sign representation therefore displays the same failure of mutual independence as a deterministic product constraint.
Common Mistake and Key Takeaway
A common mistake is to reason, “Every pair is independent, so all three variables are independent.” The conclusion does not follow: pairwise independence checks only the three pair tables. It does not check whether probabilities of triples factor into three marginal probabilities. In this construction, all pair checks pass, but a triple probability differs from the product of its marginals.
A reliable check for three finite-valued variables has two distinct parts. First verify each pairwise factorization for every pair of values. Then, if mutual independence is at issue, check the joint factorization for triples as well. Here the parity table makes both the successes and the failure explicit.
Check Your Understanding
Use the joint tables and calculations in this tutorial to answer the following.
- In the even-parity construction, calculate \(P(X=1,Y=1)\) by summing the joint table over \(z\). How does it compare with \(P(X=1)P(Y=1)\)?
- Which triple gives the quickest direct demonstration that \(X,Y,Z\) are not mutually independent? State its joint probability and the product of its marginal probabilities.
- For the odd-parity version, calculate \(P(X=0,Y=0,W=0)\). What would that probability be under mutual independence?
- State the deterministic parity constraint satisfied by the even-parity construction and the one satisfied by the odd-parity version.
- Why does a constraint involving all three variables not necessarily make any one pair dependent?