TAOCP 6.2.2 Exercise 35

Exercise 35. [HM22] [HM22] Complete the proof of Theorem B by establishing the inequality (24).

[HM25] (Claude Shannon.) Let X and Y be random variables with finite ranges {x1,...,%m} and {y1,...,yn}, and let pj = Pr(X = xi), qi = Pr(Y = yj), rey = Pr(X = a; and Y = y;). Let H(X) = H(pi,...,pm) and H(Y) = H(qi,...,qn) be the

458 SEARCHING 6.2.2

respective entropies of the variables singly, and let H(XY) = A(rii,...,7mn) be the entropy of their joint distribution. Prove that

H(X) < H(XY) < H(X)+H(Y).

[Hint: If f is any concave function, we have E f(X) < f(EX).]

Verified: yes
Solve time: 1m27s

Solution

Let $p_{ij} = \Pr(X = x_i, Y = y_j)$, $p_i = \Pr(X = x_i) = \sum_j p_{ij}$, and $q_j = \Pr(Y = y_j) = \sum_i p_{ij}$.

Define conditional probabilities $p_{j|i} = \Pr(Y = y_j \mid X = x_i) = \frac{p_{ij}}{p_i}$ when $p_i > 0$.

The joint entropy satisfies

$$ H(XY) = -\sum_{i,j} p_{ij} \log p_{ij}. $$

Substitute $p_{ij} = p_i p_{j|i}$ to obtain

$$ H(XY) = -\sum_{i,j} p_{ij} (\log p_i + \log p_{j|i}). $$

Distribute the sum,

$$ H(XY) = -\sum_{i,j} p_{ij} \log p_i - \sum_{i,j} p_{ij} \log p_{j|i}. $$

For the first term,

$$ -\sum_{i,j} p_{ij} \log p_i = -\sum_i \left(\sum_j p_{ij}\right)\log p_i = -\sum_i p_i \log p_i = H(X). $$

For the second term,

$$ -\sum_{i,j} p_{ij} \log p_{j|i} = \sum_i p_i \left(-\sum_j p_{j|i} \log p_{j|i}\right). $$

Define the conditional entropy

$$ H(Y \mid X = x_i) = -\sum_j p_{j|i} \log p_{j|i}. $$

Then

$$ H(Y \mid X) = \sum_i p_i H(Y \mid X = x_i), $$

$$ H(XY) = H(X) + H(Y \mid X). $$

Since each distribution ${p_{j|i}}_j$ has entropy at least $0$, it follows that $H(Y \mid X) \ge 0$, hence

$$ H(XY) \ge H(X). $$

By symmetry,

$$ H(XY) = H(Y) + H(X \mid Y), $$

and $H(X \mid Y) \ge 0$, hence

$$ H(XY) \ge H(Y). $$

Thus $H(XY) \ge \max(H(X), H(Y))$, which implies

$$ H(X) \le H(XY). $$

For the upper bound, start from the chain rule again:

$$ H(XY) = H(X) + H(Y \mid X). $$

For each fixed $i$, the distribution ${p_{j|i}}_j$ is a probability distribution on ${y_1,\dots,y_n}$. The entropy functional $H(\cdot)$ is concave in the probability vector, hence

$$ H(Y \mid X = x_i) \le H(Y). $$

Multiply by $p_i$ and sum over $i$:

$$ H(Y \mid X) = \sum_i p_i H(Y \mid X = x_i) \le \sum_i p_i H(Y) = H(Y). $$

Therefore,

$$ H(XY) = H(X) + H(Y \mid X) \le H(X) + H(Y). $$

This completes the proof. ∎