2.5 Chain Rules for Entropy, Relative Entropy, and Mutual Information

Theorem 2.5.1 (Chain rule for entropy). Let \(X_1, \dots, X_n\) be drawn according to \(p(x_1, \dots, x_n)\). Then

\[H(X_1, \dots, X_n) = \sum_{i=1}^n H(X_i \mid X_{i-1}, \dots, X_1)\]

Definition. The conditional mutual information of random variables \(X\) and \(Y\) given \(Z\) is defined by

\[\begin{split}I(X; Y \mid Z) & = H(X \mid Z) - H(X \mid Y, Z) \\ & = E_{p(x, y, z)} \log \frac{p(X, Y \mid Z)}{p(X \mid Z)p(Y \mid Z)}\end{split}\]

Theorem 2.5.2 (Chain rule for information).

\[I(X_1, \dots, X_n; Y) = \sum_{i=1}^n I(X_i; Y \mid X_{i-1}, \dots, X_1)\]

Definition. For joint probability mass functions \(p(x, y)\) and \(q(x, y)\), the conditional relative entropy \(D(p(y \mid x) \mid\mid q(y \mid x))\) is the average of the relative entropies between the conditional probability mass functions \(p(y \mid x)\) and \(q(y \mid x)\) averaged over the probability mass function \(p(x)\). More precisely,

\[\begin{split}D(p(y \mid x) \mid\mid q(y \mid x)) & = \sum_x p(x) \sum_y p(y \mid x) \log \frac{p(y\mid x)}{q(y \mid x)} \\ & = E_{p(x, y)} \log \frac{p(Y \mid X)}{q(Y \mid X)}\end{split}\]

Theorem 2.5.3 (Chain rule for relative entropy).

\[D(p(x, y) \mid\mid q(x, y)) = D(p(x) \mid\mid q(x)) + D(p(y \mid x) \mid\mid q(y \mid x))\]