TAOCP 6.2.2 Exercise 36
We use natural logarithms for entropy; any base yields the same inequalities.
Section 6.2.2: Binary Tree Searching
Exercise 36. ▶ [HM25] (Claude Shannon.) Let $X$ and $Y$ be random variables with finite ranges ${x_1, \ldots, x_m}$ and ${y_1, \ldots, y_n}$, and let $p_i = \Pr{X = x_i}$, $\bar{q}j = \Pr{Y = y_j}$, $r{ij} = \Pr{X = x_i \text{ and } Y = y_j}$. Let $H(X) = H(p_1, \ldots, p_m)$ and $H(Y) = H(q_1, \ldots, q_n)$ be the
respective entropies of the variables singly; and let $H(XY) = H(r_1, \ldots, r_{mn})$ be the entropy of their joint distribution. Prove that
$$H(X) \le H(XY) \le H(X) + H(Y).$$
[Hint: If $f$ is any concave function, we have $\mathrm{E},f(X) \le f(\mathrm{E},X)$.]
Verified: no
Solve time: 3m43s
Solution
We use natural logarithms for entropy; any base yields the same inequalities.
Let (p_i = \Pr{X = x_i}), (q_j = \Pr{Y = y_j}), and (r_{ij} = \Pr{X = x_i,; Y = y_j}).
Then (\sum_i p_i = \sum_j q_j = \sum_{i,j} r_{ij} = 1), (p_i = \sum_j r_{ij}), (q_j = \sum_i r_{ij}).
The entropies are
[ H(X) = -\sum_i p_i \log p_i,\qquad H(Y) = -\sum_j q_j \log q_j,\qquad H(XY) = -\sum_{i,j} r_{ij} \log r_{ij}. ]
We shall apply Jensen’s inequality for concave functions: if (f) is concave and (Z) is a random variable, then (\mathrm{E}[f(Z)] \le f(\mathrm{E}[Z])).
1. Proof of (H(X) \le H(XY))
Observe that (H(XY) = H(X) + H(Y\mid X)) where
[ H(Y\mid X) = \sum_i p_i, H(Y\mid X=x_i),\qquad H(Y\mid X=x_i) = -\sum_j \frac{r_{ij}}{p_i}\log\frac{r_{ij}}{p_i};;(p_i>0). ]
(If (p_i = 0) the term is (0).) It suffices to show (H(Y\mid X=x_i) \ge 0) for each (i).
Fix (i) with (p_i > 0). Define (q_{j\mid i} = r_{ij}/p_i); these are non‑negative and sum to (1).
Let (Q) be a random variable that takes the value (q_{j\mid i}) with probability (q_{j\mid i}). Then
[ \mathrm{E}[Q] = \sum_j q_{j\mid i}^{,2} \le \Bigl(\sum_j q_{j\mid i}\Bigr)^{!2} = 1. ]
The function (\log x) is concave on ((0,\infty)). By Jensen’s inequality,
[ \mathrm{E}[\log Q] \le \log\mathrm{E}[Q] \le \log 1 = 0. ]
But (\mathrm{E}[\log Q] = \sum_j q_{j\mid i}\log q_{j\mid i} = -H(Y\mid X=x_i)). Hence
[ -H(Y\mid X=x_i) \le 0 \quad\Longrightarrow\quad H(Y\mid X=x_i) \ge 0. ]
Summing over (i) gives (H(Y\mid X) \ge 0), and therefore (H(XY) \ge H(X)).
2. Proof of (H(XY) \le H(X) + H(Y))
Define a random variable (U) as follows: for each pair ((i,j)) with (p_i q_j > 0) (which implies (r_{ij} > 0) because (r_{ij} \le p_i, q_j)), let (U) take the value
[ u_{ij} = \frac{r_{ij}}{p_i q_j} ]
with probability (p_i q_j). Pairs with (p_i q_j = 0) contribute zero probability and can be ignored. Then
[ \mathrm{E}[U] = \sum_{i,j} p_i q_j \cdot \frac{r_{ij}}{p_i q_j} = \sum_{i,j} r_{ij} = 1. ]
Consider (f(x) = -x\log x) on ([0,\infty)) (with (f(0)=0)). Its second derivative is (f''(x) = -1/x < 0) for (x>0), so (f) is concave. Jensen’s inequality yields
[ \mathrm{E}[f(U)] \le f(\mathrm{E}[U]) = f(1) = 0. ]
Now compute (\mathrm{E}[f(U)]):
[ \mathrm{E}[f(U)] = \sum_{i,j} p_i q_j \left( -,\frac{r_{ij}}{p_i q_j}\log\frac{r_{ij}}{p_i q_j} \right) = -\sum_{i,j} r_{ij}\log\frac{r_{ij}}{p_i q_j} = H(XY) - H(X) - H(Y). ]
Thus (H(XY) - H(X) - H(Y) \le 0), i.e. (H(XY) \le H(X) + H(Y)).
Combining the two parts, we have proved
[ H(X) \le H(XY) \le H(X) + H(Y). ]
∎