The Exercise

Three random variables $X$, $Y$ and $Z$ take finitely many values, with a joint distribution $p$. Strong subadditivity of the Shannon entropy says that the entropy of all three, plus the entropy of the middle variable $Y$, is at most the sum of the entropies of the two pairs $(X,Y)$ and $(Y,Z)$ that share $Y$.^✦ The exercise asks for this inequality and for the case of equality, which occurs exactly when $Z \to Y \to X$ is a Markov chain.

The library states both the inequality and the condition for equality, for random variables with values in finite sets.

Distributions and Entropy

A joint distribution $p$ of $X$, $Y$, $Z$ on finite sets $\mathcal{X}$, $\mathcal{Y}$, $\mathcal{Z}$ is a real function on $\mathcal{X} \times \mathcal{Y} \times \mathcal{Z}$, nonnegative at every triple $(x,y,z)$, whose values sum to one.

The Shannon entropy $H(q)$ of a distribution $q$ on a finite set $\mathcal{A}$ is the sum over outcomes of $-q(a)\log q(a)$, $$H(q) = -\sum_{a \in \mathcal{A}} q(a) \log q(a),$$(1)^✦ with the natural logarithm, so that it is measured in nats.

Marginals

The marginal $p_{XY}$ of $p$ is the joint distribution of $X$ and $Y$, obtained by summing out $Z$: $$p_{XY}(x,y) = \sum_{z \in \mathcal{Z}} p(x,y,z).$$(2)^✦

The marginal $p_{YZ}$ of $p$ is the joint distribution of $Y$ and $Z$, obtained by summing out $X$: $$p_{YZ}(y,z) = \sum_{x} p(x,y,z).$$(3)^✦

The marginal $p_Y$ of $p$ is the distribution of $Y$ alone, obtained by summing $p_{YZ}$ over $z$: $$p_Y(y) = \sum_{z} p_{YZ}(y,z) = \sum_{x,z} p(x,y,z).$$(4)^✦

The entropies of the exercise are those of $p$ and its marginals: $H(X,Y,Z) = H(p)$, $H(X,Y) = H(p_{XY})$, $H(Y,Z) = H(p_{YZ})$ and $H(Y) = H(p_Y)$.

The Markov Condition

The random variables $X$, $Y$, $Z$ with joint distribution $p$ form a Markov chain $Z \to Y \to X$ when $X$ and $Z$ are conditionally independent given $Y$: $$p(x,y,z)\, p_Y(y) = p_{XY}(x,y)\, p_{YZ}(y,z) \quad \text{for all } x, y, z.$$(5)^✦ The condition is symmetric in $X$ and $Z$, so it says equally that $X \to Y \to Z$ is a Markov chain.

The Claim

What Is Checked

The theorem is stated over a joint distribution $p$ of three random variables on finite sets, the Shannon entropy (1) of $p$ and of its marginals (2), (3) and (4), and the Markov condition (5).

For every such distribution the library proves strong subadditivity (6) and the characterization (7) of its case of equality.