Chain Rules for Entropy, Relative Entropy and Mutual Information

We now show that the entropy of a collection of random variables is the sum of the conditional entropies.

Note: 本文的证明还比较粗糙, 后面会改进.

Ref: Elements of Information Theory

Chain rule for entropy

Let $X_1,X_2,\dots ,X_n$ be drawn according to $p(x_1,x_2,\dots ,x_n)$. Then $$H(X_1,X_2,\dots ,X_n)=\sum _{i=1}^{n}H(X_i\mid X_{i-1},\dots ,X_1).$$

Proof: Short

By repeated application of the two-variable expansion rule for entropies, we have $$\begin{array}{rl}H(X_1,X_2)& =H\left(X_1\right)+H(X_2\mid X_1),\\ H(X_1,X_2,X_3)& =H\left(X_1\right)+H(X_2,X_3\mid X_1)\\ & =H\left(X_1\right)+H(X_2\mid X_1)+H(X_3\mid X_2,X_1),\\ & ⋮\\ H(X_1,X_2,\dots ,X_n)& =H\left(X_1\right)+H(X_2\mid X_1)+\cdots +H(X_n\mid X_{n-1},\dots ,X_1)\\ & =\sum _{i=1}^{n}H(X_i\mid X_{i-1},\dots ,X_1).\end{array}$$

Proof: Long

We write $p(x_1,\dots ,x_n)=\prod _{i=1}^{n}p(x_i\mid x_{i-1},\dots ,x_1)$ and evaluate $$\begin{array}{rl}H& (X_1,X_2,\dots ,X_n)\\ & =-\sum _{x_1,x_2,\dots ,x_n}p(x_1,x_2,\dots ,x_n)\log p(x_1,x_2,\dots ,x_n)\\ & =-\sum _{x_1,x_2,\dots ,x_n}p(x_1,x_2,\dots ,x_n)\log \prod _{i=1}^{n}p(x_i\mid x_{i-1},\dots ,x_1)\\ & =-\sum _{x_1,x_2,\dots ,x_n}\sum _{i=1}^{n}p(x_1,x_2,\dots ,x_n)\log p(x_i\mid x_{i-1},\dots ,x_1)\\ & =-\sum _{i=1}^n\sum _{x_1,x_2,\dots ,x_n}p(x_1,x_2,\dots ,x_n)\log p(x_i\mid x_{i-1},\dots ,x_1)\\ & =-\sum _{i=1}^n\sum _{x_1,x_2,\dots ,x_i}p(x_1,x_2,\dots ,x_i)\log p(x_i\mid x_{i-1},\dots ,x_1)\\ & =\sum _{i=1}^{n}H(X_i\mid X_{i-1},\dots ,X_1).\end{array}$$ We now define the conditional mutual information as the reduction in the uncertainty of $X$ due to knowledge of $Y$ when $Z$ is given.

Chain rule for Mutual Information

Mutual information also satisfies a chain rule. $$I(X_1,X_2,\dots ,X_n;Y)=\sum _{i=1}^{n}I(X_i;Y\mid X_{i-1},X_{i-2},\dots ,X_1).$$

Proof

$$\begin{array}{rl}I& (X_1,X_2,\dots ,X_n;Y)\\ & =H(X_1,X_2,\dots ,X_n)-H(X_1,X_2,\dots ,X_n\mid Y)\\ & =\sum _{i=1}^{n}H(X_i\mid X_{i-1},\dots ,X_1)-\sum _{i=1}^{n}H(X_i\mid X_{i-1},\dots ,X_1,Y)\\ & =\sum _{i=1}^{n}I(X_i;Y\mid X_1,X_2,\dots ,X_{i-1}).\end{array}$$

Chain Rule for Relative Entropy

The chain rule for relative entropy is used in Section 4.4 to prove a version of the second law of thermodynamics.

$$D(p(x,y)\Vert q(x,y))=D(p(x)\Vert q(x))+D(p(y\mid x)\Vert q(y\mid x)).$$

Proof

$$\begin{array}{rl}D(& p(x,y)\Vert q(x,y))\\ & =\sum _x\sum _{y}p(x,y)\log \frac{p(x,y)}{q(x,y)}\\ & =\sum _x\sum _{y}p(x,y)\log \frac{p(x)p(y\mid x)}{q(x)q(y\mid x)}\\ & =\sum _x\sum _{y}p(x,y)\log \frac{p(x)}{q(x)}+\sum _x\sum _{y}p(x,y)\log \frac{p(y\mid x)}{q(y\mid x)}\\ & =D(p(x)\Vert q(x))+D(p(y\mid x)\Vert q(y\mid x)).\end{array}$$