台交大信息论 Lecture 4

课程主页：https://ocw.nctu.edu.tw/course_detail-c.php?bgid=8&gid=0&nid=612&pid=973

http://shannon.cm.nctu.edu.tw/it18.htm

老师主页：http://shannon.cm.nctu.edu.tw/

课程视频：https://www.youtube.com/playlist?list=PLj6E8qlqmkFsWS54o6gNWeDGXeI7c3eUd

这次回顾第四讲，这一讲主要介绍了各种和熵相关的概念，对应视频8-9。

自信息

自信息，用$\mathcal I(E)$表示，是学习事件$E$所获得的信息
自信息满足三个公理
1. $\mathcal I(E)$是关于概率$p_E$的递减函数，即$\mathcal{I}(E)=I\left(p_{E}\right), I$在$[0,1]$递减
2. $I(p_E)$连续
3. 如果$E_{1} \perp E 2$，其中$\perp$表示独立，那么$\mathcal{I}\left(E_{1} \cap E_{2}\right)=\mathcal{I}\left(E_{1}\right)+\mathcal{I}\left(E_{2}\right)$，即$I\left(p_{E_{1}} \times p_{E_{2}}\right)=I\left(p_{E_{1}}\right)+I\left(p_{E_{2}}\right)$
可以证明，满足上述条件的函数一定为$I(p)=-c \cdot \log _{b}(p)$，可以总结为如下定理。
- 一般我们取$c=1,b=2$，通常省略下标$b$。

定理

定义在$p \in(0,1]$上，并且满足如下$3$个条件的唯一函数为$I(p)=-c \cdot \log _{b}(p)$，其中$c>0, b>1$

$I(p)$递减
$I(p)$在$(0, 1]$连续
$I\left(p_{1} \times p_{2}\right)=I\left(p_{1}\right)+I\left(p_{2}\right)$

证明分为以下三个步骤：

步骤1：证明$I(p)=-c \cdot \log _{b}(p)$对于$p=1/n$成立。

步骤2：证明$I(p)=-c \cdot \log _{b}(p)$对于$p$为有理数成立。

步骤3：证明$I(p)= -c \cdot \log _{b}(p)$对于实数$p$成立。

步骤1

命题：对于$n\in \mathbb Z^+$，

$I\left(\frac{1}{n}\right)=-c \cdot \log _{b}\left(\frac{1}{n}\right)$

证明：

$(n=1)$利用条件3可得

$I(1)= I(1) + I(1)\Rightarrow I(1) = 0=-c. \log_b (1)$

($n>1$)对于任意正整数$r$，$\exists $非负整数$k$，使得

$n^{k} \leq 2^{r}<n^{k+1} \tag 1$

由条件1可得

$I\left(\frac{1}{n^{k}}\right) \leq I\left(\frac{1}{2^{r}}\right)<I\left(\frac{1}{n^{k+1}}\right)$

由条件3可以将上式化为

$k \cdot I\left(\frac{1}{n}\right) \leq r \cdot I\left(\frac{1}{2}\right)<(k+1) \cdot I\left(\frac{1}{n}\right)$

利用$I(1 / n)>I(1)=0$

$\frac{k}{r} \leq \frac{I(1 / 2)}{I(1 / n)} \leq \frac{k+1}{r}$

另一方面，对$(1)$取对数可得，$b>1$

$\log _{b} n^{k} \leq \log _{b} 2^{r} \leq \log _{b} n^{k+1} \Leftrightarrow \frac{k}{r} \leq \frac{\log _{b}(2)}{\log _{b}(n)} \leq \frac{k+1}{r}$

因此

$\left|\frac{\log _{b}(2)}{\log _{b}(n)}-\frac{I(1 / 2)}{I(1 / n)}\right|<\frac{1}{r}$

令$r\to \infty$得到

$I\left(\frac{1}{n}\right)=\frac{I(1 / 2)}{\log _{b}(2)} \cdot \log _{b}(n)=-c \cdot \log _{b}\left(\frac{1}{n}\right)$

其中

$c=I(1 / 2) / \log _{b}(2)>0$

步骤2

命题：对于正有理数$p$，

$I(p)=-c \cdot \log _{b}(p)$

证明：

正有理数$p\in (0, 1]$可以表达为$p=r/s$，其中$r\le s, r,s \in \mathbb Z^{+}$，注意有恒等式：

$\frac 1 s =\frac r s \frac 1 r$

利用性质3可得

$I\left(\frac{1}{s}\right)=I\left(\frac{r }{s} \frac 1 r \right)=I\left(\frac{r}{s}\right)+I\left(\frac{1}{r}\right)$

所以

$I(p)=I\left(\frac{r}{s}\right)=I\left(\frac{1}{s}\right)-I\left(\frac{1}{r}\right)=c \cdot \log _{b} s-c \cdot \log _{b} r=-c \cdot \log _{b} p$

步骤3

对于任意$p\in (0, 1]$，可以利用有理数序列$\{p_n\}$逼近$p$，利用性质2可得

$I(p) =\lim_{n\to \infty} I(p_n) = \lim_{n\to \infty}-c.\log_b (p_n) =-c.\log_b p$

熵

定义

熵

离散随机变量$X$的概率分布为$P_X(.)$，熵用$H(X)$或$H\left(P_{X}\right)$表示，定义为

$H(X):=-\sum_{x \in \mathcal{X}} P_{X}(x) \cdot \log _{2} P_{X}(x)$

联合熵

随机变量$(X, Y)$的联合熵$H(X,Y)$定义为

$\begin{aligned} H(X, Y) &:=-\sum_{(x, y) \in \mathcal{X} \times \mathcal{Y}} P_{X, Y}(x, y) \cdot \log _{2} P_{X, Y}(x, y) \\ &=E\left[-\log _{2} P_{X, Y}(X, Y)\right] \end{aligned}$

条件熵

已知随机变量$X,Y$，给定$X$，$Y$的条件熵定义为

$\begin{aligned} H(Y | X) &:=\sum_{x \in \mathcal{X}} P_{X}(x)\left(-\sum_{y \in \mathcal{Y}} P_{Y | X}(y | x) \cdot \log _{2} P_{Y |X}(y | x)\right)\\ &=-\sum_{(x, y) \in \mathcal{X} \times \mathcal{Y}} P_{X, Y}(x, y) \cdot \log _{2} P_{Y|X}(y|x)\\ &= E\left[-\log _{2} P_{Y|X}(y|x)\right] \end{aligned}$

常用不等式

后续有关熵的内容经常使用如下不等式。

基本不等式(FI)

对于任意$x>0, D>1$，我们有

$\begin{aligned} \log _{D}(e)\left(1-\frac 1 x\right) &\le \log _{D}(x) \leq \log _{D}(e) \cdot(x-1) \Leftrightarrow \\ 1-\frac 1 x &\le \ln x \le x - 1 \end{aligned}$

证明：

令

$f(x)=\ln x - x+1$

然后求导即可证明$f(x)\le 0$，等号成立当且仅当$x=1$。

假设已知

$\ln x \le x - 1$

令$x=\frac 1 x$得到

$\ln \left(\frac 1 x \right) \le \frac 1 x - 1$

即

$1-\frac 1 x \le \ln x$

另一个常用不等式为对数-求和不等式(Log-sum inequality)

对数-求和不等式(Log-sum inequality)

对于非负数$a_{1}, a_{2}, \dots, a_{n}$以及$b_{1}, b_{2}, \ldots, b_{n}$，

$\sum_{i=1}^{n}\left(a_{i} \log _{D} \frac{a_{i}}{b_{i}}\right) \geq\left(\sum_{i=1}^{n} a_{i}\right) \log _{D} \frac{\sum_{i=1}^{n} a_{i}}{\sum_{i=1}^{n} b_{i}}$

等号成立当且仅当$(\forall 1 \leq i \leq n)\left(a_{i} / b_{i}\right)=\left(a_{1} / b_{1}\right)$。备注：$D>1$

证明：

$\begin{aligned} \sum_{i=1}^{n}\left(a_{i} \log _{D} \frac{a_{i}}{b_{i}}\right) - \left(\sum_{i=1}^{n} a_{i}\right) \log _{D} \frac{\sum_{i=1}^{n} a_{i}}{\sum_{i=1}^{n} b_{i}} &= \sum_{i=1}^{n} a_{i} \left(\log _{D} \frac{a_{i}}{b_{i}} - \log _{D}\frac{\sum_{j=1}^{n} a_{j}}{\sum_{j=1}^{n} b_{j}}\right)\\ &= \sum_{i=1}^{n} a_{i} \left(\log _{D} \frac{a_{i} \sum_{j=1}^{n} b_{j}}{b_{i}\sum_{j=1}^{n} a_{j}}\right)\\ &\ge \log_D (e) \sum_{i=1}^{n} a_{i} \left(1- \frac{b_{i}\sum_{j=1}^{n} a_{j}}{a_{i} \sum_{j=1}^{n} b_{j}}\right)\\ &= \log_D (e) \left( \sum_{i=1}^{n} a_{i} -\frac{\sum_{j=1}^{n} a_{j}}{ \sum_{j=1}^{n} b_{j}} \sum_{i=1}^{n} b_i \right) \\ &= 0 \end{aligned}$

等号成立当且仅当$\forall 1 \leq i \leq n$，

$\frac{a_{i} \sum_{j=1}^{n} b_{j}}{b_{i}\sum_{j=1}^{n} a_{j}} =1\Leftrightarrow \frac {a_i}{b_i} =\frac{\sum_{j=1}^{n} a_{j}}{\sum_{j=1}^{n} b_{j}}$

性质

链式法则

$\begin{aligned} H(X, Y)&=H(X)+H(Y | X)\\ H(X, Y |Z)&=H(X |Z)+H(Y |X, Z) \end{aligned}$

证明：

利用

$\begin{aligned} P_{X, Y}(x, y)&=P_{X}(x) P_{Y | X}(y | x)\\ P_{X, Y |Z}(x, y|z)&= P_{X|Z}(x|z)P_{Y|X,Z}(y|x,z) \end{aligned}$

可得

$\begin{aligned} H(X, Y) &=E\left[-\log _{2} P_{X, Y}(X, Y)\right] \\ &=E\left[-\log _{2} P_{X}(X)\right]+E\left[-\log _{2} P_{Y |X}(Y | X)\right] \\ &=H(X)+H(Y | X)\\ H(X, Y|Z) &=E\left[-\log _{2} P_{X, Y|Z}(X, Y|Z)\right] \\ &=E\left[-\log _{2} P_{X|Z}(X|Z)\right]+E\left[-\log _{2} P_{Y |X,Z}(Y | X,Z)\right] \\ &=H(X |Z)+H(Y |X, Z) \end{aligned}$

链式法则（推广）

$H\left(X_{1}, X_{2}, \ldots, X_{n}\right)=\sum_{i=1}^{n} H\left(X_{i}| X_{i-1}, \ldots, X_{1}\right)$

如果记$X^{n}:=\left(X_{1}, \ldots, X_{n}\right)$，那么上式可以记为

$H\left(X^{n}\right)=\sum_{i=1}^{n} H\left(X_{i} | X^{i-1}\right)$

证明：

利用联合概率的链式分解即可。

条件熵的链式法则

$H\left(X_{1}, X_{2}, \ldots, X_{n} | Y\right)=\sum_{i=1}^{n} H\left(X_{i} | X_{i-1}, \ldots, X_{1}, Y\right)$

证明：

利用条件概率的链式法则即可。

熵的非负性

证明：

$0 \leq P_{X}(x) \leq 1 \Rightarrow \log _{2}\left[1 / P_{X}(x)\right] \geq 0$

所以

$H(X)=\sum_{x \in \mathcal{X}} P_{X}(x) \log _{2} \frac{1}{P_{X}(x)} \geq 0$

等号成立当且仅当对于某个$x\in \mathcal X$，$P_X(x)=1$。

熵的上界

如果随机变量$X$取值于有限集$\mathcal X$，那么

$H(X) \leq \log _{2}|\mathcal{X}|$

等号成立当且仅当

$P_{X}(x)=\frac{1}{|\mathcal{X}|} , x\in \mathcal X$

说明：均匀分布给出最大熵。

证明：

利用基本不等式即可：

$\begin{aligned} \log _{2}|\mathcal{X}|-H(X) &=\log _{2}|\mathcal{X}| \times\left(\sum_{x \in \mathcal{X}} P_{X}(x)\right)-\left(-\sum_{x \in \mathcal{X}} P_{X}(x) \log _{2} P_{X}(x)\right) \\ &=\sum_{x \in \mathcal{X}} P_{X}(x) \times \log _{2}|\mathcal{X}|+\sum_{x \in \mathcal{X}} P_{X}(x) \log _{2} P_{X}(x) \\ &=\sum_{x \in \mathcal{X}} P_{X}(x) \log _{2}\left(|\mathcal{X}| \times P_{X}(x)\right) \\ & \geq \sum_{x \in \mathcal{X}} P_{X}(x) \cdot \log _{2}(e)\left(1-\frac{1}{|\mathcal{X}| \times P_{X}(x)}\right) \\ &=\log _{2}(e) \sum_{x \in \mathcal{X}}\left(P_{X}(x)-\frac{1}{|\mathcal{X}|}\right) \\ &=\log _{2}(e) \cdot(1-1)\\ &=0 \end{aligned}$

等号成立当且仅当$\forall x\in \mathcal X,|\mathcal{X}| \times P_{X}(x)=1$，即$P_X(.)$在$X$上服从均匀分布。

条件永远不增加熵

$H(X|Y) \leq H(X)$

等号成立当且仅当$X,Y$独立。

证明：

利用Log-sum不等式即可：

$\begin{aligned} H(X)-H(X | Y) &=\sum_{(x, y) \in \mathcal{X} \times \mathcal{Y}} P_{X, Y}(x, y) \cdot \log _{2} \frac{P_{X | Y}(x | y)}{P_{X}(x)} \\ &=\sum_{(x, y) \in \mathcal{X} \times \mathcal{Y}} P_{X, Y}(x, y) \cdot \log _{2} \frac{P_{X | Y}(x | y) P_{Y}(y)}{P_{X}(x) P_{Y}(y)} \\ &=\sum_{(x, y) \in \mathcal{X} \times \mathcal{Y}} P_{X, Y}(x, y) \cdot \log _{2} \frac{P_{X, Y}(x, y)}{P_{X}(x) P_{Y}(y)} \\ & \geq\left(\sum_{(x, y) \in \mathcal{X} \times \mathcal{Y}} P_{X, Y}(x, y)\right) \log _{2} \frac{\sum_{(x, y) \in \mathcal{X} \times \mathcal{Y}} P_{X, Y}(x, y)}{\sum_{(x, y) \in \mathcal{X} \times \mathcal{Y}} P_{X}(x) P_{Y}(y)} \\ &=0 \end{aligned}$

等号成立当且仅当

$\frac{P_{X, Y}(x, y)}{P_{X}(x) P_{Y}(y)}=\text { constant } \quad \forall(x, y) \in \mathcal{X} \times \mathcal{Y}$

不难推出该条件等价于$X,Y$独立。

联合熵的上界

$H\left(X_{1}, X_{2}, \ldots, X_{n}\right) \leq \sum_{i=1}^{n} H\left(X_{i}\right.)$

等会成立当且仅当$X_i$相互独立。

证明：

利用恒等式

$H\left(X_{1}, X_{2}, \ldots, X_{n}\right)=\sum_{i=1}^{n} H\left(X_{i}| X_{i-1}, \ldots, X_{1}\right)$

以及

$H\left(X_{i}| X_{i-1}, \ldots, X_{1}\right) \le H(X_i)$

等会成立当且仅当$X_i$相互独立。

独立随机变量的联合熵

如果$X,Y$独立，那么

$H(X, Y)=H(X)+H(Y)$

证明：

利用恒等式

$H(X, Y)=H(X)+H(Y | X)$

以及前一个结论等号成立条件即可。

一般的，我们有

$H(X, Y)=H(X)+H(Y | X) \le H(X)+H(Y)$

条件熵的次可加性

$H\left(X_{1}, X_{2} |Y_{1}, Y_{2}\right) \leq H\left(X_{1} |Y_{1}\right)+H\left(X_{2} | Y_{2}\right)$

等号成立当且仅当

$P_{X_{1}, X_{2} | Y_{1}, Y_{2}}\left(x_{1}, x_{2} | y_{1}, y_{2}\right)=P_{X_{1} | Y_{1}}\left(x_{1} |y_{1}\right) P_{X_{2}| Y_{2}}\left(x_{2}| y_{2}\right)$

证明：

$\begin{aligned} H\left(X_{1} |Y_{1}\right)+H\left(X_{2} | Y_{2}\right) -H\left(X_{1}, X_{2} |Y_{1}, Y_{2}\right) &= \sum_{(x_1, y_1) \in \mathcal{X_1} \times \mathcal{Y_1}} P_{X_1, Y_1}(x_1, y_1) \cdot \log _{2} \frac{1}{P_{X_1|Y_1}(x_1|y_1)}\\ &+\sum_{(x_2, y_2) \in \mathcal{X_2} \times \mathcal{Y_2}} P_{X_2, Y_2}(x_2, y_2) \cdot \log _{2} \frac{1}{P_{X_2|Y_2}(x_2|y_2)}\\ &+\sum_{(x_1, x_2,y_1,y_2) \in \mathcal{X_1} \times \mathcal{X_2} \times \mathcal{Y_1}\times \mathcal{Y_2}}P_{X_1,X_2, Y_1, Y_2} (x_1,x_2,y_1,y_2)\cdot \log _{2} {P_{X_1,X_2|Y_1,Y_2}(x_1,x_2|y_1,y_2)}\\ &= \sum_{(x_1, x_2,y_1,y_2) \in \mathcal{X_1} \times \mathcal{X_2} \times \mathcal{Y_1}\times \mathcal{Y_2}}P_{X_1,X_2, Y_1, Y_2} (x_1,x_2,y_1,y_2) \cdot \log _{2} \frac{1}{P_{X_1|Y_1}(x_1|y_1)}\\ &+\sum_{(x_1, x_2,y_1,y_2) \in \mathcal{X_1} \times \mathcal{X_2} \times \mathcal{Y_1}\times \mathcal{Y_2}} P_{X_1,X_2, Y_1, Y_2} (x_1,x_2,y_1,y_2) \cdot \log _{2} \frac{1}{P_{X_2|Y_2}(x_2|y_2)}\\ &+\sum_{(x_1, x_2,y_1,y_2) \in \mathcal{X_1} \times \mathcal{X_2} \times \mathcal{Y_1}\times \mathcal{Y_2}}P_{X_1,X_2, Y_1, Y_2} (x_1,x_2,y_1,y_2)\cdot \log _{2} {P_{X_1,X_2|Y_1,Y_2}(x_1,x_2|y_1,y_2)}\\ &= \sum_{(x_1, x_2,y_1,y_2) \in \mathcal{X_1} \times \mathcal{X_2} \times \mathcal{Y_1}\times \mathcal{Y_2}}P_{X_1,X_2, Y_1, Y_2} (x_1,x_2,y_1,y_2)\cdot \log _{2} \frac {P_{X_1,X_2|Y_1,Y_2}(x_1,x_2|y_1,y_2)}{P_{X_1|Y_1}(x_1|y_1)P_{X_2|Y_2}(x_2|y_2)}\\ &=\sum_{(x_1, x_2,y_1,y_2) \in \mathcal{X_1} \times \mathcal{X_2} \times \mathcal{Y_1}\times \mathcal{Y_2}}P_{X_1,X_2, Y_1, Y_2} (x_1,x_2,y_1,y_2)\cdot \log _{2} \frac {P_{X_1,X_2,Y_1,Y_2}(x_1,x_2,y_1,y_2)}{P_{X_1|Y_1}(x_1|y_1)P_{X_2|Y_2}(x_2|y_2)P_{Y_1,Y_2}(y_1,y_2)}\\ &\ge \left(\sum_{(x_1, x_2,y_1,y_2) \in \mathcal{X_1} \times \mathcal{X_2} \times \mathcal{Y_1}\times \mathcal{Y_2}}P_{X_1,X_2, Y_1, Y_2} (x_1,x_2,y_1,y_2)\right) \\ &\times \log_2\frac {\sum_{(x_1, x_2,y_1,y_2) \in \mathcal{X_1} \times \mathcal{X_2} \times \mathcal{Y_1}\times \mathcal{Y_2}}P_{X_1,X_2,Y_1,Y_2}(x_1,x_2,y_1,y_2)}{\sum_{(x_1, x_2,y_1,y_2) \in \mathcal{X_1} \times \mathcal{X_2} \times \mathcal{Y_1}\times \mathcal{Y_2}}P_{X_1|Y_1}(x_1|y_1)P_{X_2|Y_2}(x_2|y_2)P_{Y_1,Y_2}(y_1,y_2)}\\ &=0 \end{aligned}$

等号成立当且仅当

$\frac {P_{X_1,X_2,Y_1,Y_2}(x_1,x_2,y_1,y_2)}{P_{X_1|Y_1}(x_1|y_1)P_{X_2|Y_2}(x_2|y_2)P_{Y_1,Y_2}(y_1,y_2)} =\text { constant } \quad \forall(x_1, x_2,y_1,y_2) \in \mathcal{X_1} \times\mathcal{X_2} \times \mathcal{Y_1}\times \mathcal{Y_2}$

即

$P_{X_{1}, X_{2} | Y_{1}, Y_{2}}\left(x_{1}, x_{2} | y_{1}, y_{2}\right)=P_{X_{1} | Y_{1}}\left(x_{1} |y_{1}\right) P_{X_{2}| Y_{2}}\left(x_{2}| y_{2}\right)$

互信息

定义

互信息

互信息的定义如下：

$\begin{aligned} I(X ; Y) &:=H(X)+H(Y)-H(X, Y) \\ &=H(Y)-H(Y|X) \\ &=H(X)-H(X| Y) \end{aligned}$

图示如下：

条件互信息

$\begin{aligned} I(X ; Y|Z) &:=H(X|Z)+H(Y|Z)-H(X, Y|Z) \\ &=H(Y|Z)-H(Y|X,Z) \\ &=H(X|Z)-H(X| Y,Z) \end{aligned}$

性质

基本性质

$I(X ; Y)=\sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} P_{X, Y}(x, y) \log _{2} \frac{P_{X, Y}(x, y)}{P_{X}(x) P_{Y}(y)}$
$I(X ; Y)=I(Y ; X)$
$I(X ; Y)=H(X)+H(Y)-H(X, Y)$
$I(X ; Y) \leq H(X)$
等号成立当且仅当$X=f(Y)$
$I(X ; Y) \geq 0$
$I(X ; Y) \leq \min \left\{\log _{2}|\mathcal{X}|, \log _{2}|\mathcal{Y}|\right\}$

证明都是平凡的，这里从略。

链式法则

$I(X ; Y, Z)=I(X ; Y)+I(X ; Z | Y)=I(X ; Z)+I(X ; Y | Z)$

图示如下：

证明：

只证明第二项，第一项同理可得。

$\begin{aligned} I(X ; Y, Z) &=H(X)-H(X | Y, Z) \\ &=H(X)-H(X | Z)+H(X | Z)-H(X | Y, Z) \\ &=I(X ; Z)+I(X ; Y | Z) \end{aligned}$

链式法则（推广）

$I\left(X_{1}, X_{2}, \ldots, X_{n} ; Y\right)=\sum_{i=1}^{n} I\left(X_{i} ; Y | X_{i-1}, \ldots, X_{1}\right)$

其中当$i=1$时

$I\left(X_{i} ; Y| X_{i-1}, \ldots, X_{1}\right):=I\left(X_{1} ; Y\right)$

证明：

$\begin{aligned} I\left(X_{1}, X_{2}, \ldots, X_{n} ; Y\right) &= H(X_{1}, X_{2}, \ldots, X_{n})-H(X_{1}, X_{2}, \ldots, X_{n}| Y)\\ &=\sum_{i=1}^{n} H\left(X_{i}| X_{i-1}, \ldots, X_{1}\right)- \sum_{i=1}^{n} H\left(X_{i} | X_{i-1}, \ldots, X_{1}, Y\right)\\ &= \sum_{i=1}^{n} \left(H\left(X_{i}| X_{i-1}, \ldots, X_{1}\right)- H\left(X_{i} | X_{i-1}, \ldots, X_{1}, Y\right) \right)\\ &= \sum_{i=1}^{n} I\left(X_{i} ; Y | X_{i-1}, \ldots, X_{1}\right) \end{aligned}$

互信息的上界

如果$\left\{\left(X_{i}, Y_{i}\right)\right\}_{i=1}^{n}$满足条件独立假设

$P_{Y^{n} \mid X^{n}}=\prod_{i=1}^{n} P_{Y_{i} \mid X_{i}}$

那么

$I\left(X_{1}, \ldots, X_{n} ; Y_{1}, \ldots, Y_{n}\right) \leq \sum_{i=1}^{n} I\left(X_{i} ; Y_{i}\right)$

等号成立当且仅当$\left\{X_{i}\right\}_{i=1}^{n}$独立。

证明：

$\begin{aligned} I\left(X_{1}, \ldots, X_{n} ; Y_{1}, \ldots, Y_{n}\right) &= H(X_{1}, \ldots, X_{n})-H(X_{1}, \ldots, X_{n}| Y_{1}, \ldots, Y_{n})\\ &=\sum_{i=1}^{n} H\left(X_{i}| X_{i-1}, \ldots, X_{1}\right) -\sum_{i=1}^n H(X_i |Y_i)\\ &= \sum_{i=1}^{n} \left(H\left(X_{i}| X_{i-1}, \ldots, X_{1}\right)- H(X_i |Y_i)\right)\\ &\le \sum_{i=1}^{n} \left(H\left(X_{i}\right)- H(X_i |Y_i)\right)\\ &= \sum_{i=1}^{n} I(X_i;Y_i) \end{aligned}$

等会成立当且仅当$\left\{X_{i}\right\}_{i=1}^{n}$独立。

数据压缩定理

如果$X \rightarrow Y \rightarrow Z$（马氏链），那么$I(X ; Y) \geq I(X ; Z)$。

证明：马氏链性质表明给定$Y$，$X,Z$条件独立，即

$I(X ; Z | Y)=0$

由链式法则可得

$\begin{aligned} I(X ; Z)+I(X ; Y | Z) &=I(X ; Y, Z) \\ &=I(X ; Y)+I(X ; Z | Y) \\ &=I(X ; Y) \end{aligned}$

注意到

$I(X ; Y|Z) \ge 0$

我们得到

$I(X ; Y) \geq I(X ; Z)$

等号成立当且仅当

$I(X ; Y| Z)=0$

定理含义：

压缩只会减少信息。

推论1

对于随机变量$X,Y$以及任意函数$g(Y)$，我们有$X \rightarrow Y \rightarrow g(Y)$，所以

$I(X ; Y) \geq I(X ; g(Y))$

推论2

如果$X \rightarrow Y \rightarrow Z$，那么

$I(X ; Y |Z) \leq I(X ; Y)$

证明：

利用恒等式

$\begin{aligned} I(X ; Z)+I(X ; Y | Z) &=I(X ; Y, Z) \\ &=I(X ; Y)+I(X ; Z | Y) \\ &=I(X ; Y) \end{aligned}$

所以

$I(X ; Y |Z) \leq I(X ; Y)$

推论3

如果$X_{1} \rightarrow X_{2} \rightarrow \cdots \rightarrow X_{n}$，那么对于满足$1 \leq i \leq j \leq k \leq l \leq n$的任意$i,j,k,l$，我们有

$I\left(X_{i} ; X_{l}\right) \leq I\left(X_{j} ; X_{k}\right)$

证明：

已知

$X_i \to X_j \to X_k \to X_l$

考虑

$X_i \to X_j \to X_l$

我们有

$I\left(X_{i} ; X_{l}\right) \leq I\left(X_{j} ; X_{l}\right)$

接着考虑

$X_j \to X_k \to X_l$

我们有

$I\left(X_{j} ; X_{l}\right) \leq I\left(X_{j} ; X_{k}\right)$

所以

$I\left(X_{i} ; X_{l}\right) \leq I\left(X_{j} ; X_{l}\right) \le I\left(X_{j} ; X_{k}\right)$