信息论

信息论笔记。

信源与信息熵

马尔可夫信源

信源记忆长度为$m+1$时，该时刻发出的信号只与之前的$m$个有关系，则称这种信源为马尔可夫信源。对于一阶马尔可夫信源，类似于下面的式子都成立：

$$p(x_1\mid x_2,x_3)=p(x_1\mid x_2)$$

因为$x_1$并不影响$x_3$ 。

离散信源信息熵

定义

离散信源信息熵：

$$H(X)=E[I(X)]=E[-\log p(x_i)]=-\sum_i p(x_i)\log p(x_i)$$

条件信息熵：

$$\begin{aligned} H(X\mid Y)=\sum_j p(y_j)H(X\mid y_j)&=-\sum_{i,j}p(y_j)p(x_i\mid y_j)\log p(x_i\mid y_j)\\ &=-\sum_{i,j}p(x_i,y_j)\log p(x_i\mid y_j) \end{aligned}$$

联合信息熵：

$$H(X,Y)=-\sum_{i,j}p(x_i,y_j)\log p(x_i,y_j)$$

重要关系

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

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

证明：

$$\begin{aligned} H(Y)+H(X\mid Y)&=-\sum_j p(y_j)\log p(y_j)-\sum_{i,j}p(x_i,y_j)\log p(x_i\mid y_j)\\ &=-\sum_{i,j} p(x_i,y_j)\log p(y_j)-\sum_{i,j}p(x_i,y_j)\log p(x_i\mid y_j)\\ &=-\sum_{i,j} p(x_i,y_j)\log p(y_j)p(x_i\mid y_j)\\ &=-\sum_{i,j}p(x_i,y_j)\log p(x_i,y_j)=H(X,Y) \end{aligned}$$

推广：

$$H(X_1,X_2,\cdots ,X_n)=\sum_i^n H(X_i\mid X_1,X_2,\cdots ,X_{i-1})$$

互信息

定义

$$I(X;Y)=H(X)-H(X\mid Y)$$

条件互信息定义

$$\begin{aligned} I(X;Y\mid Z)&=H(X\mid Z)-H(X\mid Y,Z)\\ &=\sum_{i,j,k}p(x_i,y_j,z_k)\log \dfrac{p(x_i\mid y_j,z_k)}{p(x_i\mid z_k)} \end{aligned}$$

重要关系

$I(X;Y)=I(Y;X)$

证明：

$$\begin{aligned} I(X;Y)&=H(X)-H(X\mid Y)\\ &=-\sum_i p(x_i)\log p(x_i)+\sum_{i,j}p(x_i,y_j)\log p(x_i\mid y_j)\\ &=-\sum_{i,j} p(x_i,y_j)\log p(x_i)+\sum_{i,j}p(x_i,y_j)\log p(x_i\mid y_j)\\ &=\sum_{i,j} p(x_i,y_j)\log \dfrac{p(x_i,y_j)}{p(x_i)p(y_j)}=I(Y;X) \end{aligned}$$

$0\leqslant I(X;Y)\leqslant H(X)$

$I(X;Y,Z)=I(X;Y)+I(X;Z\mid Y)$

证明：

$$\begin{aligned} I(X;Y)+I(X;Z\mid Y)&=\sum_{i,j}p(x_i,y_j)\log \dfrac{p(x_i,y_j)}{p(x_i)p(y_j)}+\sum_{i,j,k}p(x_i,y_j,z_k)\log \dfrac{p(x_i\mid y_j,z_k)}{p(x_i\mid y_j)}\\ &=\sum_{i,j,k}\log \dfrac{p(x_i,y_j)}{p(x_i)p(y_j)}\cdot \dfrac{p(x_i,y_j,z_k)p(y_j)}{p(y_j,z_k)p(x_i,y_j)}\\ &=\sum_{i,j,k}\log \dfrac{p(x_i,y_j,z_k)}{p(x_i)p(y_j,z_k)}=I(X;Y,Z) \end{aligned}$$

$I(X;Y,Z)=I(X;Y)$若$X-Y-Z$构成马尔科夫链

证明：

$$\begin{aligned} I(X;Y,Z)&=\sum_{i,j,k}p(x_i.y_j,z_k)\log \dfrac{p(x_i,y_j,z_k)}{p(x_i)p(y_i,z_k)}\\ &=\sum_{i,j,k}p(x_i.y_j,z_k)\log \dfrac{p(x_i\mid y_j,z_k)}{p(x_i)}\\ &=\sum_{i,j,k}p(x_i.y_j,z_k)\log \dfrac{p(x_i\mid y_j)}{p(x_i)}=I(X;Y) \end{aligned}$$

信息传输不等式

对于构成马尔科夫链的随机变量$X-Y-Z$，他们之间的互信息有关系：

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

证明：

$$\begin{aligned} I(X;Y)-I(X;Z)&=I(X;Y,Z)-I(X;Z)\\ &=I(X;Y\mid Z)\\ &=\sum_k p(z_k)I(X;Y\mid z_k)\geqslant 0. \end{aligned}$$

许可协议

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

分享文章