The Exercise

Two random variables $X$ and $Y$ take values in finite sets $\mathcal{X}$ and $\mathcal{Y}$ , with joint distribution $p(x,y)$ . The conditional entropy $H(Y|X)$ , the joint entropy less the entropy of $X$ , is the uncertainty left in $Y$ once $X$ is known. The exercise writes $H(Y|X)$ as a relative entropy between $p$ and a second function on the pairs $(x,y)$ , and asks for its sign: $H(Y|X)$ is never negative, and it vanishes exactly when $Y$ is a function of $X$ .

Entropies of a Pair

The Shannon entropy $H(p)$ of a distribution $p$ on a finite set $\mathcal{A}$ is, with the natural logarithm and so in nats, $H(p) = -\sum_{a \in \mathcal{A}} p(a) \log p(a).$ (1)^✦

The first marginal $p_X$ of a joint distribution $p$ of $X$ and $Y$ on $\mathcal{X} \times \mathcal{Y}$ is the distribution of $X$ alone, obtained by summing out $Y$ : $p_X(x) = \sum_{y \in \mathcal{Y}} p(x,y).$ (2)^✦

Applied to $p$ , the entropy (1) is the joint entropy $H(X,Y)$ ; applied to $p_X$ , it is $H(X)$ .

The reference function $q$ of a joint distribution $p$ of $X$ and $Y$ is the function on $\mathcal{X} \times \mathcal{Y}$ that weights each joint probability $p(x,y)$ by the conditional probability $p(x,y)/p_X(x)$ of $y$ given $x$ : $q(x,y) = \frac{p(x,y)^2}{p_X(x)}.$ (3)^✦

The relative entropy of $p$ to $q$ is written $D(p\,\|\,q)$ .

Under a joint distribution $p$ of $X$ and $Y$ , the variable $Y$ is determined by $X$ when there is a function $f$ from $\mathcal{X}$ to $\mathcal{Y}$ with $y = f(x) \quad \text{for every pair } (x,y) \text{ with } p(x,y) \neq 0.$ (4)^✦

The Claim

Theorem 1. Let $\mathcal{X}$ and $\mathcal{Y}$ be finite sets and $p$ a function on $\mathcal{X} \times \mathcal{Y}$ with $p(x,y) \ge 0$ for every pair, with first marginal $p_X$ as in (2) and reference function $q$ as in (3). Then $H(p) - H(p_X) = D(p\,\|\,q)$ (5)^✦ and $D(p\,\|\,q) \ge 0.$ (6)^✦ If moreover $\mathcal{Y}$ is not empty, then $D(p\,\|\,q) = 0 \quad \text{if and only if} \quad Y \text{ is determined by } X \text{ under } p .$ (7)^✦

For a joint distribution $p$ of $X$ and $Y$ the left side of (5) is $H(Y|X)$ , and the theorem is the exercise.

What Is Checked

The theorem is stated for every nonnegative function $p$ on a product of two finite sets, normalized or not, through the Shannon entropy (1), the first marginal (2), the reference function (3) and the relative entropy, with determination (4) in its equality case. About these constructions the library proves the identity (5), the sign (6) and the equality case (7).