台交大信息论 Lecture 5

课程主页：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

这次回顾第五讲，这一讲主要介绍了Fano不等式以及KL散度，对应视频9-11。

Fano不等式

令$X,Y$为两个相关随机变量，$X$取值于$\mathcal X$，$Y$取值于$\mathcal Y$，$\mathcal X$有限，$\mathcal Y$可数无限。假设$\hat{X}:=g(Y)$为通过观测$Y$得到对于$X$的估计，其中$g: \mathcal{Y} \rightarrow \mathcal{X}$是给定的估计函数。定义误差概率

$$P_{e}:=\operatorname{Pr}[\hat{X} \neq X]$$

那么如下不等式成立

$$H(X | Y) \leq h_{b}\left(P_{e}\right)+P_{e} \cdot \log _{2}(|\mathcal{X}|-1)$$

其中

$$h_{\mathrm{b}}(x):=-x \log _{2} x-(1-x) \log _{2}(1-x)$$

证明1

证明：

定义

$$E:=\left\{\begin{array}{l} 1, \text { if } g(Y) \neq X \\ 0, \text { if } g(Y)=X \end{array}\right.$$

那么利用条件熵的链式法则可得

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

注意$X,Y$可以唯一确定$E$，所以

$$H(E | X, Y)=0$$

此时上述等式化为

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

利用条件熵小于等于无条件熵，我们可得

$$H(E | Y) \leq H(E)=h_{b}\left(P_{e}\right)$$

对于另一项，首先有

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

其次回顾如下不等式

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

注意在$E=1$的条件下，$X$共有$|\mathcal X| -1$的可选值，因此

$$\begin{aligned} H(X | Y, E=1) &\le \log _{2}(|\mathcal{X}|-1) \end{aligned}$$

所以

$$\begin{aligned} H(X | E, Y) &=\operatorname{Pr}[E=0] H(X | Y, E=0)+\operatorname{Pr}[E=1] H(X | Y, E=1) \\ & \leq\left(1-P_{e}\right) \cdot 0+P_{e} \cdot \log _{2}(|\mathcal{X}|-1) \end{aligned}$$

结合上述两个部分我们有

$$\begin{aligned} H(X | Y) &=H(E | Y)+H(X | E, Y)\\ &\le h_{b}\left(P_{e}\right) + P_{e} \cdot \log _{2}(|\mathcal{X}|-1) \end{aligned}$$

证明2

证明：

注意到$X \rightarrow Y \rightarrow \hat{X}$是马氏链，利用数据压缩定理可得

$$I(X ; Y) \geq I(X ; \hat{X})$$

利用互信息的定义可得

$$\begin{aligned} H(X)-H(X|Y) &\ge H(X)-H(X|\hat X)\\ H(X|Y) &\le H(X|\hat X) \end{aligned}$$

如果能证明

$$H(X | \hat X) \leq h_{b}\left(P_{e}\right)+P_{e} \cdot \log _{2}(|\mathcal{X}|- 1)$$

那么原不等式即可得证。

注意到

$$P_{e}=\sum_{x \in \mathcal{X}} \sum_{\hat{x} \in \mathcal{X}: \hat{x} \neq x} P_{X, \hat{X}}(x, \hat{x})$$

以及

$$1-P_{e}=\sum_{x \in \mathcal{X}} \sum_{\hat{x} \in \mathcal{X}: \hat{x}=x} P_{X, \hat{X}}(x, \hat{x})=\sum_{x \in \mathcal{X}} P_{X, \hat{X}}(x, x)$$

我们得到

$$\begin{aligned} H(X | \hat{X})-h_{b}\left(P_{e}\right)-P_{e} \log _{2}(|\mathcal{X}|-1) &=\sum_{x \in \mathcal{X}} \sum_{\hat{x} \in \mathcal{X}: \hat{x} \neq x} P_{X, \hat{X}}(x, \hat{x}) \log _{2} \frac{1}{P_{X | \hat{X}}(x | \hat{x})}+\sum_{x \in \mathcal{X}} P_{X, \hat{X}}(x, x) \log _{2} \frac{1}{P_{X | \hat{X}}(x | x)}\\ &+ P_e \log_2 P_e +(1-P_e)\log_2 (1-P_e) - P_e \log _{2}(|\mathcal{X}|-1) \\ &= \sum_{x \in \mathcal{X}} \sum_{\hat{x} \in \mathcal{X}: \hat{x} \neq x} P_{X, \hat{X}}(x, \hat{x}) \log _{2} \frac{1}{P_{X | \hat{X}}(x | \hat{x})}+\sum_{x \in \mathcal{X}} P_{X, \hat{X}}(x, x) \log _{2} \frac{1}{P_{X | \hat{X}}(x | x)}\\ &-\left[\sum_{x \in \mathcal{X}} \sum_{\hat{x} \in \mathcal{X}: \hat{x} \neq x} P_{X,\hat X}(x, \hat{x})\right] \log _{2} \frac{(|\mathcal{X}|-1)}{P_{e}}+\left[\sum_{x \in \mathcal{X}} P_{X,\hat X}(x, x)\right] \log _{2}\left(1-P_{e}\right)\\ &=\sum_{x \in \mathcal{X}} \sum_{\hat{x} \in \mathcal{X}: \hat{x} \neq x} P_{X, \hat{X}}(x, \hat{x}) \log _{2} \frac{P_{e}}{P_{X | \hat{X}}(x | \hat{x})(|\mathcal{X}|-1)} +\sum_{x \in \mathcal{X}} P_{X, \hat{X}}(x, x) \log _{2} \frac{1-P_{e}}{P_{X | \hat{X}}(x | x)} \\ &\le \log _{2}(e) \sum_{x \in \mathcal{X}} \sum_{\hat{x} \in \mathcal{X}: \hat{x} \neq x} P_{X, \hat{X}}(x, \hat{x})\left[\frac{P_{e}}{P_{X | \hat{X}}(x | \hat{x})(|\mathcal{X}|-1)}-1\right] \\ &+\log _{2}(e) \sum_{x \in \mathcal{X}} P_{X, \hat{X}}(x, x)\left[\frac{1-P_{e}}{P_{X | \hat{X}}(x | x)}-1\right] \\ &= \log _{2}(e) \left[\frac{P_{e}}{(|\mathcal{X}|-1)} \sum_{x \in \mathcal{X}} \sum_{\hat{x} \in \mathcal{X}: \hat{x} \neq x} P_{\hat{X}}(\hat{x})-\sum_{x \in \mathcal{X}} \sum_{\hat{x} \in \mathcal{X}: \hat{x} \neq x} P_{X, X}(x, \hat{x})\right] \\ &+\log _{2}(e)\left[\left(1-P_{e}\right) \sum_{x \in \mathcal{X}} P_{\hat{X}}(x)-\sum_{x \in \mathcal{X}} P_{X, X}(x, x)\right]\\ &= \log _{2}(e) \left[\frac{P_{e}}{(|\mathcal{X}|-1)} \sum_{x \in \mathcal{X}} (1-P_{\hat X}(x))-P_e\right]+\log _{2}(e)\left[\left(1-P_{e}\right) -(1-P_e)\right]\\ &= \log _{2}(e) \left[\frac{P_{e}}{(|\mathcal{X}|-1)}(|\mathcal X| -1)-P_e\right]+\log _{2}(e)\left[\left(1-P_{e}\right) -(1-P_e)\right]\\ &=0 \end{aligned}$$

KL散度和变分距离

KL散度

随机变量$X,\hat X$定义在集合$\mathcal X$，那么KL散度$D(X | \hat{X})$或$D\left(P_{X} | P_{\hat{X}}\right)$定义为

$$D(X \| \hat{X})=D\left(P_{X} \| P_{\hat{X}}\right):=E_{X}\left[\log _{2} \frac{P_{X}(X)}{P_{\hat{X}}(X)}\right]=\sum_{x \in \mathcal{X}} P_{X}(x) \log _{2} \frac{P_{X}(x)}{P_{\hat{X}}(x)}$$

备注：KL散度也称为相对熵。

非负性

$$D(X \| \hat{X}) \geq 0$$

等号成立当且仅当$P_{X}(x)=P_{\hat{X}}(x)$对所有$x \in \mathcal{X}$。

证明：

$$\begin{aligned} D(X \| \hat{X}) &=\sum_{x \in \mathcal{X}} P_{X}(x) \log _{2} \frac{P_{X}(x)}{P_{\hat{X}}(x)}\\ & \geq\left(\sum_{x \in \mathcal{X}} P_{X}(x)\right) \log _{2} \frac{\sum_{x \in \mathcal{X}} P_{X}(x)}{\sum_{x \in \mathcal{X}} P_{\hat{X}}(x)} \\ &=0 \end{aligned}$$

等号成立当且仅当

$$\frac{P_{X}(x)}{P_{\hat{X}}(x)}=\frac{\sum_{a \in \mathcal{X}} P_{X}(a)}{\sum_{b \in \mathcal{X}} P_{\hat{X}}(b)}=1, \forall x \in \mathcal X$$

互信息和KL散度

利用定义不难看出

$$I(X ; Y)=D\left(P_{X, Y} \| P_{X} \times P_{Y}\right)$$

因为

$$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)}$$

分布的细化

给定定义在$\mathcal X$上的分布$P_{X}$，将$\mathcal X$划分为$k$个不相交集合$\mathcal{U}_{1}, \mathcal{U}_{2}, \ldots, \mathcal{U}_{k}$，满足

$$\mathcal{X}=\bigcup_{i=1}^{k} \mathcal{U}_{i}$$

定义一个新的分布$P_{U}$，该分布取值于$\mathcal{U}=\{1,2, \ldots, k\}$，其中

$$P_{U}(i)=\sum_{x \in U_{i}} P_{X}(x)$$

那么$P_X$被称为$P_U$的细化（$k-$细化）。

细化不会减少散度

令$P_X$和$P_{\hat X}$为$P_U$和$P_{\hat U}$的细化（$k-$细化），那么

$$D\left(P_{X} \| P_{\hat{X}}\right) \geq D\left(P_{U} \| P_{\hat{U}}\right)$$

证明：

首先对任意$i \in\{1,2, \ldots, k\}$，我们有

$$\begin{aligned} \sum_{x \in \mathcal{U}_{i}} P_{X}(x) \log _{2} \frac{P_{X}(x)}{P_{\hat{X}}(x)} & \geq\left(\sum_{x \in U_{i}} P_{X}(x)\right) \log _{2} \frac{\sum_{x \in \mathcal{U}_{i}} P_{X}(x)}{\sum_{x \in \mathcal{U}_{i}} P_{\hat{X}}(x)} \\ &=P_{U}(i) \log _{2} \frac{P_{U}(i)}{P_{\hat{U}}(i)} \end{aligned}$$

等号成立当且仅当

$$\frac{P_{X}(x)}{P_{X}(x)}=\frac{P_{U}(i)}{P_{U}(i)},\forall x\in \mathcal U$$

因此

$$\begin{aligned} D\left(P_{X} \| P_{\hat{X}}\right) &=\sum_{i=1}^{k} \sum_{x \in U_{i}} P_{X}(x) \log _{2} \frac{P_{X}(x)}{P_{\hat{X}}(x)} \\ & \geq \sum_{i=1}^{k} P_{U}(i) \log _{2} \frac{P_{U}(i)}{P_{\hat{U}}(i)} \\ &=D\left(P_{U} \| P_{U}\right) \end{aligned}$$

等号成立当且仅当对所有$i$以及$x\in \mathcal U_i$

$$\frac{P_{X}(x)}{P_{\hat{X}}(x)}=\frac{P_{U}(i)}{P_{\hat{U}}(i)}$$

变分距离

分布$P_{X}$和$P_{\hat{X}}$定义在相同集合$\mathcal{X}$，两个分布的变分距离定义为

$$\left\|P_{X}-P_{\hat{X}}\right\|:=\sum_{x \in \mathcal{X}}\left|P_{X}(x)-P_{\hat{X}}(x)\right|$$

变分距离满足如下性质

$$\left\|P_{X}-P_{\hat{X}}\right\|=2 \cdot \sum_{x \in \mathcal{X}: P_{X}(x)>P_{\hat{X}}(x)}\left(P_{X}(x)-P_{\hat{X}}(x)\right)=2 \cdot \sup _{E \subset \mathcal{X}}\left|P_{X}(E)-P_{\hat{X}}(E)\right|$$

证明：

$$\begin{aligned} \left\|P_{X}-P_{\hat{X}}\right\| &=\sum_{x \in \mathcal{X}}\left|P_{X}(x)-P_{\hat{X}}(x)\right|\\ &= \sum_{x \in \mathcal{X}: P_{X}(x)>P_{\hat{X}}(x)}\left(P_{X}(x)-P_{\hat{X}}(x)\right) - \sum_{x \in \mathcal{X}: P_{X}(x)< P_{\hat{X}}(x)}\left(P_{X}(x)-P_{\hat{X}}(x)\right) \\ &= \sum_{x \in \mathcal{X}: P_{X}(x)>P_{\hat{X}}(x)}\left(P_{X}(x)-P_{\hat{X}}(x)\right) + \sum_{x \in \mathcal{X}: P_{X}(x)< P_{\hat{X}}(x)}\left((1- P_(x))-(1-P_{\hat X}(x))\right)\\ &= \sum_{x \in \mathcal{X}: P_{X}(x)>P_{\hat{X}}(x)}\left(P_{X}(x)-P_{\hat{X}}(x)\right) + \sum_{x \in \mathcal{X}: 1- P_(x) > 1-P_{\hat X}(x)}\left((1- P_(x))-(1-P_{\hat X}(x))\right)\\ &= 2 \cdot \sum_{x \in \mathcal{X}: P_{X}(x)>P_{\hat{X}}(x)}\left(P_{X}(x)-P_{\hat{X}}(x)\right)\\ &=2 \cdot \sup _{E \subset \mathcal{X}}\left|P_{X}(E)-P_{\hat{X}}(E)\right| \end{aligned}$$

变分距离和散度的关系：Pinsker不等式

$$D(X \| \hat{X}) \geq \frac{\log _{2}(e)}{2} \cdot\left\|P_{X}-P_{\hat{X}}\right\|^{2}$$

证明：

1.定义

$$\mathcal{A}:=\left\{x \in \mathcal{X}: P_{X}(x)>P_{\hat{X}}(x)\right\}$$

那么

$$\left\|P_{X}-P_{\hat{X}}\right\|=2\left[P_{X}(\mathcal{A})-P_{\hat{X}}(\mathcal{A})\right]$$

2.定义随机变量

$$U=\left\{\begin{array}{ll} 1, & \text { if } X \in \mathcal{A}, \\ 0, & \text { if } X \in \mathcal{A}^{c}, \end{array} \text { and } \hat{U}=\left\{\begin{array}{l} 1, \text { if } \hat{X} \in \mathcal{A} \\ 0, \text { if } \hat{X} \in \mathcal{A}^{c} \end{array}\right.\right.$$

那么$P_X,P_{\hat X}$是$P_U, P_{\hat U}$的细化，由之前的定理可得

$$D\left(P_{X} \| P_{\hat{X}}\right) \geq D\left(P_{U} \| P_{\hat{U}}\right)$$

3.证明

$$\begin{aligned} D\left(P_{U} \| P_{\hat{U}}\right) & \geq 2 \log _{2}(e)\left[P_{X}(\mathcal{A})-P_{\hat{X}}(\mathcal{A})\right]^{2} \\ &=2 \log _{2}(e)\left[P_{U}(1)-P_{\hat{U}}(1)\right]^{2} \end{aligned}$$

令

$$\begin{aligned} p&=P_{U}(1)\\ q&=P_{\hat{U}}(1) \end{aligned}$$

那么上述不等式等价于

$$p \cdot \ln \frac{p}{q}+(1-p) \cdot \ln \frac{1-p}{1-q} \geq 2(p-q)^{2}$$

求导即可证明结果。

上界

如果$D\left(P_{X} | P_{\hat{X}}\right)<\infty$，那么

$$D\left(P_{X} \| P_{\hat{X}}\right) \leq \frac{\log _{2}(e)}{\min _{\left\{x: P_{X}(x)>0\right\}} \min \left\{P_{X}(x), P_{\hat{X}}(x)\right\}} \cdot\left\|P_{X}-P_{\hat{X}}\right\|$$

这里不提供证明。

条件散度

给定$Z$，$X$和$\hat X$的条件散度为：

$$\begin{aligned} D(X \| \hat{X} | Z)=D\left(P_{X | Z} \| P_{\hat{X} | Z} | P_{Z}\right) &:=\sum_{z \in \mathcal{Z}} P_{Z}(z) \sum_{x \in \mathcal{X}} P_{X | Z}(x | z) \log \frac{P_{X | Z}(x | z)}{P_{\hat{X} | Z}(x | z)} \\ &=\sum_{z \in \mathcal{Z}} \sum_{x \in \mathcal{X}} P_{X, Z}(x, z) \log \frac{P_{X | Z}(x | z)}{P_{\hat{X} | Z}(x | z)} \end{aligned}$$

给定$P_Z$，$P_{X|Z}$和$P_{\hat X}$的条件散度定义为：

$$D\left(P_{X | Z} \| P_{\hat{X}} | P_{Z}\right):=\sum_{z \in \mathcal{Z}} P_{Z}(z) \sum_{x \in \mathcal{X}} P_{X | Z}(x | z) \log \frac{P_{X | Z}(x | z)}{P_{\hat{X}}(z)}$$

条件互信息和条件散度的关系

$$\begin{aligned} I(X ; Y | Z) &=D\left(P_{X, Y | Z} \| P_{X | Z} P_{Y | Z} | P_{Z}\right) \\ &=\sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} \sum_{z \in \mathcal{Z}} P_{X, Y, Z}(x, y, z) \log _{2} \frac{P_{X, Y | Z}(x, y | z)}{P_{X | Z}(x | z) P_{Y | Z}(y | z)} \end{aligned}$$

链式法则

$P_{X^n}$和$Q_{X^n}$是定义在$\mathcal X^n$上的概率分布，那么

$$D\left(P_{X_{1}, X_{2}} \| Q_{X_{1}, X_{2}}\right)=D\left(P_{X_{1}} \| Q_{X_{1}}\right)+D\left(P_{X_{2} | X_{1}} \| Q_{X_{2} | X_{1}} | P_{X_{1}}\right)$$

更一般的，我们有

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

其中$i=1$时，

$$D\left(P_{X_{i} | X^{i-1} }\|Q_{X_{i}|X^{i-1}}| P_{X^{i-1}}\right):=D\left(P_{X_{1}} \| Q_{X_{1}}\right)$$

证明：

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

条件不减少散度

$$D\left(P_{X | Z} \| P_{\hat{X} | Z} | P_{Z}\right) \geq D\left(P_{X} \| P_{\hat{X}}\right)$$

证明：

$$\begin{aligned} & D\left(P_{X | Z} \| P_{\hat{X} | Z} | P_{Z}\right)-D\left(P_{X} \| P_{\hat{X}}\right) \\ =& \sum_{z \in \mathcal{Z}} \sum_{x \in \mathcal{X}} P_{X, Z}(x, z) \cdot \log _{2} \frac{P_{X | Z}(x | z)}{P_{\hat{X} | Z}(x | z)}-\sum_{x \in \mathcal{X}} P_{X}(x) \cdot \log _{2} \frac{P_{X}(x)}{P_{\hat{X}}(x)} \\ =& \sum_{z \in \mathcal{Z}} \sum_{x \in \mathcal{X}} P_{X, Z}(x, z) \cdot \log _{2} \frac{P_{X | Z}(x | z)}{P_{\hat{X} | Z}(x | z)}-\sum_{x \in \mathcal{X}}\left(\sum_{z \in \mathcal{Z}} P_{X, Z}(x, z)\right) \cdot \log _{2} \frac{P_{X}(x)}{P_{\hat{X}}(x)} \\ =& \sum_{z \in \mathcal{Z}} \sum_{x \in \mathcal{X}} P_{X, Z}(x, z) \cdot \log _{2} \frac{P_{X | Z}(x | z) P_{\hat{X}}(x)}{P_{\hat{X} | Z}(x | z) P_{X}(x)}\\ \geq& \sum_{z \in \mathcal{Z}} \sum_{x \in \mathcal{X}} P_{X, Z}(x, z) \cdot \log _{2}(e)\left(1-\frac{P_{\hat{X} | Z}(x | z) P_{X}(x)}{P_{X | Z}(x | z) P_{\hat{X}}(x)}\right) \\ =&\log _{2}(e)\left(1-\sum_{x \in \mathcal{X}} \frac{P_{X}(x)}{P_{\hat{X}}(x)} \sum_{z \in \mathcal{Z}} P_{Z}(z) P_{\hat{X} | Z}(x | z)\right) \\ =&\log _{2}(e)\left(1-\sum_{x \in \mathcal{X}} \frac{P_{X}(x)}{P_{\hat{X}}(x)} P_{\hat{X}}(x)\right) \\ =&\log _{2}(e)\left(1-\sum_{x \in \mathcal{X}} P_{X}(x)\right)\\ =&0 \end{aligned}$$

等号成立当且仅当对任意$x, z$

$$\frac{P_{X}(x)}{P_{\hat{X}}(x)}=\frac{P_{X | Z}(x | z)}{P_{\hat{X} | Z}(x | z)}$$

独立性不增加散度

$X$独立于$Z$，$\hat X$独立于$\hat Z$，那么

$$D\left(P_{X | Z} \| P_{\hat{X} | \hat{Z}} | P_{Z}\right)=D\left(P_{X} \| P_{\hat{X}}\right)$$

独立性的可加性

$X$独立于$Z$，$\hat X$独立于$\hat Z$，那么

$$D\left(P_{X, Z} \| P_{\hat{X}, \hat{Z}}\right)=D\left(P_{X} \| P_{\hat{X}}\right)+D\left(P_{Z} \| P_{\hat{Z}}\right)$$

信息度量的凹凸性

常用结论

下面介绍几个常用结论，部分证明从略。

1

$H(P_X)$关于$P_X$是凹函数，即对于所有$\lambda \in [0,1]$

$$H\left(\lambda P_{X}+(1-\lambda) P_{\tilde{X}}\right) \geq \lambda H\left(P_{X}\right)+(1-\lambda) H\left(P_{\tilde{X}}\right)$$

等号成立当且仅当对所有$x$，都有$P_{X}(x)=P_{\tilde{X}}(x)$

证明：

利用如下函数为凹函数即可证明：

$$H(P_X) =-\sum_{x} P_X(x)\log_2 P_X(x)$$

2

互信息的定义为

$$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\left(P_{X}, P_{Y | X}\right):=\sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} P_{Y | X}(y | x) P_{X}(x) \log _{2} \frac{P_{Y | X}(y | x)}{\sum_{a \in \mathcal{X}} P_{Y | X}(y | a) P_{X}(a)}$$

那么，对于固定的$P_{Y | X}$，$I(X ; Y)$关于$P_X$是凹函数，即

$$I\left(\lambda P_{X}+(1-\lambda) P_{\tilde{X}}, P_{Y | X}\right) \geq \lambda I\left(P_{X}, P_{Y | X}\right)+(1-\lambda) I\left(P_{\tilde{X}}, P_{Y | X}\right)$$

等号成立当且仅当对于任意$y \in \mathcal{Y}$，

$$P_{Y}(y)=\sum_{x \in \mathcal{X}} P_{X}(x) P_{Y | X}(y | x)=\sum_{x \in \mathcal{X}} P_{\tilde{X}}(x) P_{Y | X}(y | x)=P_{\tilde{Y}}(y)$$

对于固定的$P_X$，$I(X ; Y)$关于$P_{Y|X}$是凸函数，即

$$\lambda I\left(P_{X}, P_{Y | X}\right)+(1-\lambda) I(P_{X}, P_{\tilde{Y} | X}) \geq I\left(P_{X}, \lambda P_{Y | X}+(1-\lambda) P_{\tilde{Y} | X}\right)$$

等号成立当且仅当

$$(\forall x \in \mathcal{X}) \frac{P_{Y | X}(y | x)}{P_{\tilde{Y} | X}(y | x)}=L(y)$$

3

$D\left(P_{X} | P_{\hat{X}}\right)$关于$\left(P_{X}, P_{\hat{X}}\right)$是凸函数，即

$$\begin{array}{l} D\left(\lambda P_{X}+(1-\lambda) Q_{X} \| \lambda P_{\hat{X}}+(1-\lambda) Q_{\hat{X}}\right) \\ \leq \lambda \cdot D\left(P_{X} \| P_{\hat{X}}\right)+(1-\lambda) \cdot D\left(Q_{X} \| Q_{\hat{X}}\right) \end{array}$$

等号成立当且仅当

$$(\forall x \in \mathcal{X}) \frac{P_{X}(x)}{P_{\hat{X}}(x)}=\frac{Q_{X}(x)}{Q_{\mathcal{X}}(x)}$$

假设检验

形式

$X_{1}, \ldots, X_{n}$是一列观测值，观测值属于分布$P_{X^{n}}$（零假设）或分布$P_{\hat{X}^{n}}$（备择假设）。假设表示为

$$\begin{array}{l} H_{0}: P_{X^{n}} \\ H_{1}: P_{\hat{X}^{n}} \end{array}$$

定义决策映射

$$\phi\left(x^{n}\right)=\left\{\begin{array}{l}0, \text { if distribution of } X^{n} \text { is classified to be } P_{X^{n}} \\ 1, \text { if distribution of } X^{n} \text { is classified to be } P_{\hat{X}^{n}}\end{array}\right.$$

接受域

$$\begin{aligned} &\text { Acceptance region for } H_{0}:\left\{x^{n} \in \mathcal{X}^{n}: \phi\left(x^{n}\right)=0\right\}\\ &\text { Acceptance region for } H_{1}:\left\{x^{n} \in \mathcal{X}^{n}: \phi\left(x^{n}\right)=1\right\} \end{aligned}$$

错误种类

$$\begin{array}{c} \text { Type I error : } \alpha_{n}=\alpha_{n}(\phi)=P_{X^{n}}\left(\left\{x^{n} \in \mathcal{X}^{n}: \phi\left(x^{n}\right)=1\right\}\right) \\ \text { Type II error : } \beta_{n}=\beta_{n}(\phi)=P_{\hat{X}^{n}}\left(\left\{x^{n} \in \mathcal{X}^{n}: \phi\left(x^{n}\right)=0\right\}\right) \end{array}$$

贝叶斯假设检验

根据下式选择$\phi$

$$\min _{\{\phi\}}\left[\pi_{0} \alpha_{n}(\phi)+\pi_{1} \beta_{n}(\phi)\right]$$

NP引理

对于假设检验问题，通过似然比定义接受域

$$\mathcal{A}_{n}(\tau):=\left\{x^{n} \in \mathcal{X}^{n}: \frac{P_{X^{n}}\left(x^{n}\right)}{P_{\hat{X}^{n}}\left(x^{n}\right)}>\tau\right\}$$

令

$$\begin{aligned} \alpha_{n}^{*}&:=P_{X^{n}}\left\{\mathcal{A}_{n}^{c}(\tau)\right\}\\ \beta_{n}^{*}&:=P_{\hat{X}^{n}}\left\{\mathcal{A}_{n}(\tau)\right\} \end{aligned}$$

那么对于其他任意接受域$\mathcal B$以及对应的第一类错误$\alpha_n$，第二类错误$\beta_n$，我们有

$$\alpha_{n} \leq \alpha_{n}^{*} \Longrightarrow \beta_{n} \geq \beta_{n}^{*}$$

证明：

$$\begin{aligned} \alpha_{n}+\tau \beta_{n} &=\sum_{x^{n} \in \mathcal{B}^{c}} P_{X^{n}}\left(x^{n}\right)+\tau \sum_{x^{n} \in \mathcal{B}} P_{\hat{X}^{n}}\left(x^{n}\right) \\ &=\sum_{x^{n} \in \mathcal{B}^{c}} P_{X^{n}}\left(x^{n}\right)+\tau\left[1-\sum_{x^{n} \in \mathcal{B}^{c}} P_{\hat{X}^{n}}\left(x^{n}\right)\right] \\ &=\tau+\sum_{x^{n} \in \mathcal{B}^{c}}\left[P_{X^{n}}\left(x^{n}\right)-\tau P_{\hat{X}^{n}}\left(x^{n}\right)\right] \\ &= \tau+\sum_{x^{n} \in \mathcal{B}^{c} \cap \mathcal A}\left[P_{X^{n}}\left(x^{n}\right)-\tau P_{\hat{X}^{n}}\left(x^{n}\right)\right] +\sum_{x^{n} \in \mathcal{B}^{c} \cap \mathcal A ^{c}}\left[P_{X^{n}}\left(x^{n}\right)-\tau P_{\hat{X}^{n}}\left(x^{n}\right)\right]\\ &\ge \tau+\sum_{x^{n} \in \mathcal{B}^{c} \cap \mathcal A ^{c}}\left[P_{X^{n}}\left(x^{n}\right)-\tau P_{\hat{X}^{n}}\left(x^{n}\right)\right]\\ &\ge \tau+\sum_{x^{n} \in \mathcal A ^{c}}\left[P_{X^{n}}\left(x^{n}\right)-\tau P_{\hat{X}^{n}}\left(x^{n}\right)\right]\\ &=\alpha_{n}^{*}+\tau \beta_{n}^{*} \end{aligned}$$

等号成立当且仅当

$$\mathcal{B}=\mathcal{A}_{n}(\tau)$$

Chernoff-Stein引理

iid序列$X^{n}$属于分布$P_{X^{n}}$（零假设）或分布$P_{\hat{X}^{n}}$（备择假设），$\forall \varepsilon\in (0,1)$，最佳第二类错误满足，

$$\lim _{n \rightarrow \infty}-\frac{1}{n} \log _{2} \beta_{n}^{*}(\varepsilon)=D\left(P_{X} \| P_{\hat{X}}\right)$$

其中$\beta_{n}^{*}(\varepsilon)=\min _{\alpha_{n} \leq \varepsilon} \beta_{n}$

证明：

首先证明存在接受域满足

$$\liminf _{n \rightarrow \infty}-\frac{1}{n} \log _{2} \beta_{n}(\varepsilon) \geq D\left(P_{X} \| P_{\hat{X}}\right)$$

步骤1：定义典型散度集：

$$\mathcal{A}_{n}(\delta):=\left\{x^{n} \in \mathcal{X}^{n}:\left|\frac{1}{n} \log _{2} \frac{P_{X^{n}}\left(x^{n}\right)}{P_{\hat{X}^{n}}\left(x^{n}\right)}-D\left(P_{X} \| P_{\hat{X}}\right)\right|<\delta\right\}$$

在上述集合中的$x^n$满足

$$P_{X^{n}}\left(x^{n}\right) 2^{-n\left(D\left(P_{X} \| P_{\dot{X}}\right)+\delta\right)} \le P_{\hat{X}^{n}}\left(x^{n}\right) \leq P_{X^{n}}\left(x^{n}\right) 2^{-n\left(D\left(P_{X} \| P_{\dot{X}}\right)-\delta\right)}$$

步骤2：计算第一类错误

根据大数定律，我们有

$$P_{X^{n}}\left(\mathcal{A}_{n}(\delta)\right) \rightarrow 1 \quad \text { as } n \rightarrow \infty$$

因此对于充分大的$n$，我们有

$$\alpha_{n}=P_{X^{n}}\left(\mathcal{A}_{n}^{c}(\delta)\right)<\varepsilon$$

步骤3：计算第二类错误

$$\begin{aligned} \beta_{n}(\varepsilon) &=P_{\hat{X}^{n}}\left(\mathcal{A}_{n}(\delta)\right) \\ &=\sum_{x^{n} \in \mathcal{A}_{n}(\delta)} P_{\hat{X}^{n}}\left(x^{n}\right) \\ & \leq \sum_{x^{n} \in \mathcal{A}_{n}(\delta)} P_{X^{n}}\left(x^{n}\right) 2^{-n\left(D\left(P_{X} \| P_{\hat{X}}\right)-\delta\right)} \\ &=2^{-n\left(D\left(P_{X} \| P_{\hat{X}}\right)-\delta\right)} \sum_{x^{n} \in \mathcal{A}_{n}(\delta)} P_{X^{n}}\left(x^{n}\right) \\ &=2^{-n\left(D\left(P_{X} \| P_{\hat{X}}\right)-\delta\right)}\left(1-\alpha_{n}\right) \end{aligned}$$

因此

$$-\frac{1}{n} \log _{2} \beta_{n}(\varepsilon) \geq D\left(P_{X} \| P_{\hat{X}}\right)-\delta+\frac{1}{n} \log _{2}\left(1-\alpha_{n}\right)$$

这推出

$$\liminf _{n \rightarrow \infty}-\frac{1}{n} \log _{2} \beta_{n}(\varepsilon) \geq D\left(P_{X} \| P_{\hat{X}}\right)-\delta$$

由$\delta > 0$的任意性，我们可得

$$\liminf _{n \rightarrow \infty}-\frac{1}{n} \log _{2} \beta_{n}(\varepsilon) \geq D\left(P_{X} \| P_{\hat{X}}\right)$$

接着证明反方向的不等式，即对于任意满足

$$\alpha_{n}\left(\mathcal{B}_{n}\right)=P_{X^{n}}\left(\mathcal{B}_{n}^{c}\right) \leq \varepsilon$$

第二类错误都满足

$$\limsup _{n \rightarrow \infty}-\frac{1}{n} \log _{2} \beta_{n}\left(\mathcal{B}_{n}\right) \leq D\left(P_{X} \| P_{\hat{X}}\right)$$

事实上，我们有

$$\begin{aligned} \beta_{n}\left(\mathcal{B}_{n}\right)=P_{\hat{X}^{n}}\left(\mathcal{B}_{n}\right) & \geq P_{\hat{X}^{n}}\left(\mathcal{B}_{n} \cap \mathcal{A}_{n}(\delta)\right) \\ & \geq \sum_{x^{n} \in \mathcal{B}_{n} \cap \mathcal{A}_{n}(\delta)} P_{\hat{X}^{n}}\left(x^{n}\right) \\ & \geq \sum_{x^{n} \in \mathcal{B}_{n} \cap \mathcal{A}_{n}(\delta)} P_{X^{n}}\left(x^{n}\right) 2^{-n\left(D\left(P_{X} \| P_{\hat{X}}\right)+\delta\right)} \\ &=2^{-n\left(D\left(P_{X} \| P_{\hat{X}}\right)+\delta\right)} P_{X^{n}}\left(\mathcal{B}_{n} \cap \mathcal{A}_{n}(\delta)\right) \\ & \geq 2^{-n\left(D\left(P_{X} \| P_{\hat{X}}\right)+\delta\right)} \left[P_{X^{n}}\left(\mathcal{A}_{n}(\delta)\right)-P_{X^{n}}\left(\mathcal{B}_{n}^{c}\right)\right] \\ &=2^{-n\left(D\left(P_{X} \| P_{\hat{X}}\right)+\delta\right)}\left[P_{X^{n}}\left(\mathcal{A}_{n}(\delta)\right)-\alpha_{n}\left(\mathcal{B}_{n}\right)\right] \\ & \geq 2^{-n\left(D\left(P_{X} \| P_{X}\right)+\delta\right)}\left[P_{X^{n}}\left(\mathcal{A}_{n}(\delta)\right)-\varepsilon\right] \end{aligned}$$

因此

$$-\frac{1}{n} \log _{2} \beta_{n}\left(\mathcal{B}_{n}\right) \leq D\left(P_{X} \| P_{\hat{X}}\right)+\delta+\frac{1}{n} \log _{2}\left[P_{X^{n}}\left(\mathcal{A}_{n}(\delta)\right)-\varepsilon\right] \le D\left(P_{X} \| P_{\hat{X}}\right)+\delta$$

这说明

$$\limsup _{n \rightarrow \infty}-\frac{1}{n} \log _{2} \beta_{n}\left(\mathcal{B}_{n}\right) \leq D\left(P_{X} \| P_{\hat{X}}\right)+\delta$$

由$\delta >0$的任意性可得

$$\limsup _{n \rightarrow \infty}-\frac{1}{n} \log _{2} \beta_{n}\left(\mathcal{B}_{n}\right) \leq D\left(P_{X} \| P_{\hat{X}}\right)$$

瑞利信息度量

瑞利熵

给定参数$\alpha > 0,\alpha\neq 1$，给定离散随机变量$X$以及分布$P_X$，$X$取值于空间$\mathcal X$，阶数为$\alpha$的瑞利熵为

$$H_{\alpha}(X)=\frac{1}{1-\alpha} \log \left(\sum_{x \in \mathcal{X}} P_{X}(x)^{\alpha}\right)$$

瑞利散度

$$D_{\alpha}(X \| \hat{X})=\frac{1}{\alpha-1} \log \left(\sum_{x \in \mathcal{X}}\left[P_{X}^{\alpha}(x) P_{\hat{X}}^{1-\alpha}(x)\right]\right)$$

引理

$$\begin{aligned} \lim _{\alpha \rightarrow 1} H_{\alpha}(X) &=H(X) \\ \lim _{\alpha \rightarrow 1} D_{\alpha}(X \| \hat{X}) &=D(X \| \hat{X}) \end{aligned}$$

证明：

利用洛必达法则即可。