The Exercise

Let $X$ and $Y$ be independent bits, each equal to $0$ or $1$ with probability $1/2$, and let $Z = X \oplus Y$ be their sum modulo $2$. The exercise is to show that the information $Z$ shares with the pair $(X,Y)$ exceeds the information it shares with $X$ plus the information it shares with $Y$, so that mutual information is not subadditive.

The library states the inequality for the joint distribution of the three bits, in terms of the Shannon entropies of that distribution and of its marginals.

Entropy and Mutual Information

The Shannon entropy $H(p)$ of a distribution $p$ on a finite set is the sum over outcomes of $-p_i \log p_i$, with the natural logarithm, so that entropy is measured in nats, and with $0 \log 0 = 0$: $$H(p) = -\sum_i p_i \log p_i .$$(1)^✦

The first marginal $p_X$ of a joint distribution $p$ of $X$ and $Y$ on finite sets is the distribution of $X$ alone, obtained by summing out $Y$: $$p_X(x) = \sum_y p(x,y).$$(2)^✦ The second marginal $p_Y$ of $p$ is the distribution of $Y$ alone, obtained by summing out $X$: $$p_Y(y) = \sum_x p(x,y).$$(3)^✦

The mutual information $H(X:Y)$ of a joint distribution $p$ of $X$ and $Y$ is the entropy of $X$ plus the entropy of $Y$ less the joint entropy: $$H(X:Y) = H(p_X) + H(p_Y) - H(p).$$(4)^✦

Three Bits

The joint distribution $p$ of three bits $X$, $Y$, $Z$, in which $X$ and $Y$ are independent and fair and $Z = X \oplus Y$, is $$p(x,y,z) = \begin{cases} 1/4 & \text{if } z = x \oplus y,\\ 0 & \text{otherwise}, \end{cases} \qquad x, y, z \in \{0,1\}.$$(5)^✦

Grouping $X$ and $Y$ into one variable with four values makes $p$ a joint distribution $p_{(XY)Z}$ of the pair $(X,Y)$ and $Z$: $$p_{(XY)Z}\bigl((x,y),z\bigr) = p(x,y,z).$$(6)^✦ Summing out $Y$ gives the joint distribution $p_{XZ}$ of $X$ and $Z$, $$p_{XZ}(x,z) = \sum_y p(x,y,z),$$(7)^✦ and summing out $X$ gives the joint distribution $p_{YZ}$ of $Y$ and $Z$: $$p_{YZ}(y,z) = \sum_x p(x,y,z).$$(8)^✦

The three mutual informations of the exercise are those of these distributions under (4): $H(X,Y:Z)$ of $p_{(XY)Z}$, $H(X:Z)$ of $p_{XZ}$ and $H(Y:Z)$ of $p_{YZ}$.

The Claim

What Is Checked

The claim is stated over the distribution $p$ of the three bits in (5), read as a distribution of $(X,Y)$ and $Z$ in (6) and summed to the distributions (7) and (8), and over the mutual information (4), built from the Shannon entropy (1) and the marginals (2) and (3). What the library proves about these constructions is the strict inequality (9).