How can three events be pairwise independent but not mutually independent?

## The definitions, stated precisely **Pairwise independence** of a collection of events means that for every pair `i` and `j`, ``` P(Ai and Aj) = P(Ai) * P(Aj) ``` **Mutual independence** (often just called independence) is stronger: for *every* subset of size two or more, the probability of the intersection equals the product of the individual probabilities. For three events that means four equations — the three pairs *plus* ``` P(A and B and C) = P(A) * P(B) * P(C) ``` In general, `n` events have `2^n` subsets; subtracting the empty set and the `n` singletons leaves `2^n - n - 1` conditions. For `n = 3` that is `8 - 3 - 1 = 4`, matching the count above. Pairwise independence checks only `n(n-1)/2` of them, so for three events it verifies three of the four required equations and says nothing about the fourth. ## The canonical counterexample Flip two fair coins. The sample space is `{HH, HT, TH, TT}`, each outcome with probability 1/4. Define - `A` = the first flip is heads = `{HH, HT}`, `P(A) = 1/2` - `B` = the second flip is heads = `{HH, TH}`, `P(B) = 1/2` - `C` = exactly one head = `{HT, TH}`, `P(C) = 1/2` `C` is the XOR of the two flips: it is the parity bit that says whether the flips differ. Check the pairs: - `P(A and B) = P(HH) = 1/4 = (1/2)(1/2)` — independent. - `P(A and C) = P(HT) = 1/4 = (1/2)(1/2)` — independent. - `P(B and C) = P(TH) = 1/4 = (1/2)(1/2)` — independent. Now the triple. `A and B` forces `HH`, which has two heads, so it is not in `C`. The intersection is empty: ``` P(A and B and C) = 0, but P(A)P(B)P(C) = 1/8 ``` The three events are pairwise independent and not mutually independent. ## Why the intuition fails Each single flip tells you nothing about the parity bit: given that the first coin came up heads, the second is still fair, so 'the flips differ' still has probability 1/2. That is what pairwise independence records. But *any two* of the three events determine the third completely — knowing the first flip and the parity tells you the second flip with certainty. Total redundancy at the three-way level is invisible to every two-way check. So pairwise independence is a genuinely weaker property: 'no pair informs each other' does not imply 'no coalition informs the rest'. The same structure appears whenever a variable is a deterministic function of others while remaining marginally balanced. Parity bits are the cleanest source of such examples. ## Why anyone cares The distinction matters because several results need only the weaker condition while others need the full one. - **Variance of a sum** needs only that the terms are pairwise uncorrelated: `Var(X1 + ... + Xn) = Var(X1) + ... + Var(Xn)` holds under pairwise uncorrelatedness, which pairwise independence implies. Nothing three-way is required. - **Factorising a joint distribution** as a product of marginals needs mutual independence. Writing `P(A and B and C) = P(A)P(B)P(C)` after checking only pairs is exactly the error the counterexample punishes. - **Simulation and sampling** schemes sometimes deliberately use only pairwise-independent randomness because it is far cheaper to generate, and the estimator being computed only relies on second-moment properties. ## How to answer this in an interview State the two definitions and the fact that mutual independence is a condition on every subset, not just pairs. Then produce the two-coins-plus-parity example with the four short arithmetic checks — it takes about thirty seconds and is completely convincing. If the interviewer pushes, add the general count `2^n - n - 1` and the observation that any two events here pin down the third. One more direction is worth having ready: the failure can go the other way too. There exist collections where the full `n`-way product rule holds but some pair fails to factor, so the `n`-way equation alone is also not sufficient. That is why the definition insists on *all* subsets rather than picking a convenient one.