The Exercise

The mutual information of two random variables measures how much one of them tells about the other. Mutual information would be superadditive if, for any four random variables $X_1, X_2, Y_1, Y_2$ on one probability space, the pair $(X_1, X_2)$ always shared at least as much information with the pair $(Y_1, Y_2)$ as $X_1$ shares with $Y_1$ and $X_2$ with $Y_2$ together.

The exercise shows that it is not, with one bit and three copies of it. There is a random variable $X_1$ with values $0$ and $1$ such that, with $X_2 = Y_1 = Y_2 = X_1$, the mutual information of $X_1$ with $Y_1$ and that of $X_2$ with $Y_2$ add up to more than the mutual information of the two pairs.^✦

Entropy on a Finite Sample Space

The claim is set on a finite sample space $\Omega$ with a probability distribution $p$: each sample point $\omega$ has a probability $p(\omega) \ge 0$, and these sum to $1$.

A random variable $X$ on $\Omega$ with values in a finite set $\beta$ is a function from $\Omega$ to $\beta$.

The Shannon entropy $H(q)$ of a probability distribution $q$ on a finite set $\iota$ is $$H(q) = \sum_{i \in \iota} \bigl(-q(i) \log q(i)\bigr),$$(1)^✦ with the natural logarithm, so that entropy is measured in nats.

The entropy $H(X)$ of a random variable $X$ on $\Omega$ with values in $\beta$ is the Shannon entropy of its law under $p$, the distribution $p_X$ on $\beta$ that gives each value $b$ the total probability of the sample points where $X$ takes that value: $$H(X) = H(p_X), \qquad p_X(b) = \sum_{\omega \in \Omega \,:\, X(\omega) = b} p(\omega).$$(2)^✦

The mutual information $H(X:Y)$ of two random variables $X$ and $Y$ on $\Omega$ is $$H(X:Y) = H(X) + H(Y) - H(X,Y),$$(3)^✦ where $H(X,Y)$ is the entropy of the random variable $(X,Y)$ that takes the value $(X(\omega), Y(\omega))$ at $\omega$. In the same way, $H(X_1,X_2 : Y_1,Y_2)$ is the mutual information of the joint variables $(X_1,X_2)$ and $(Y_1,Y_2)$.

The Claim

What Is Checked

The claim is stated over the mutual information (3) of random variables on a finite sample space with a probability distribution, built from the entropy (2) of a random variable’s law, which is the Shannon entropy (1) of a distribution on a finite set. The library proves this: the bit with its three copies (4).