Exercise 2.7 - Pairwise independence does not imply mutual independence

Consider three boolean variables ${\xi }_1,{\xi }_2,{\xi }_3$, ${\xi }_1$ and ${\xi }_2$ take values in 0 or 1 with equal possibility independently and $x_3=\text{XOR}(x_1,x_2)$. It is easy to prove that $x_3$ is independent with $x_1$ or $x_2$, but given both $x_1$ and $x_2$, the value of $x_3$ is determined and thereby the mutual independence fails. For a detailed examination, denote the space of experiment outcomes by

with the first component denote the value of ${\xi }_1$, the second is for ${\xi }_2$. Then ${\xi }_1$ generates the $\sigma$-algebra:

${\xi }_2$ generates:

${\xi }_3$ generates:

One can easily check that each pair out of the triplet $F_1,F_2$ and $F_3$ is a pair of independent $\sigma$-algebra, hence meets the pairwise independence.

However, each pair out of the triplet $F_1,F_2$ and $F_3$ can span the entire $2^{\mathrm{\Omega }}$. Then we would have counter examples, e.g., consider

Then

Hence the mutual independence does not hold.

This example comes from cryptography. The only theoretical secure (defined by Shannon) encryption system is the one-pad cipher book. With the message denoted by $m$ in binary code, the encryption is done by XOR $m$ with a binary key $k$ drawn from a cipher book. The result is ciphertext $c$. From a statistical point of view, $c$ is equally likely to be the ciphertext of any message, hence the adversary cannot break the security (since the ciphertext can be equally understood as any message, so no specific message prevails). But the encryption is a deterministic process (by using a strictly one-pad cipher book, this cipher is resistant to chosen-plaintext attack as well), so the mutual independence fails.