信息论基础 1~8

1 绪论与概览

2 熵 相对熵与互信息

2.1 熵

H(X)=−∑x∈Xp(x)logp(x)$$H(X)=-\sum _{x\in X}p(x)\log p(x)$$

2.2 联合熵

H(X,Y)=−∑x∈X∑y∈Yp(x,y)logp(x,y)$$H(X,Y)=-\sum _{x\in X}\sum _{y\in Y}p(x,y)\log p(x,y)$$

H(Y|X)=∑x∈Xp(x)H(Y|X=x)$$H(Y|X)=\sum _{x\in X}p(x)H(Y|X=x)$$

定理2.2.1(链式法则): H(X,Y)=H(X)+H(Y|X)$H(X,Y)=H(X)+H(Y|X)$

2.3 相对熵与互信息

相对熵(relative entropy): D(p||q)=∑x∈Xp(x)logp(x)q(x)=Eplogp(x)q(x)$D(p||q)=\sum _{x\in X}p(x)\log \frac{p(x)}{q(x)}=E_p\log \frac{p(x)}{q(x)}$

互信息(mutual information): I(X;Y)=∑x∈X∑y∈Yp(x,y)logp(x,y)p(x)p(y)=D(p(x,y)||p(x)p(y))$I(X;Y)=\sum _{x\in X}\sum _{y\in Y}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}=D(p(x,y)||p(x)p(y))$

2.4 熵与互信息的关系

I(X;Y)=H(X)−H(X|Y)=H(Y)−H(Y|X)$$I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)$$

互信息I(X;Y)是在给定Y知识的条件下X的不确定度的缩减量

I(X;Y)=H(X)+H(Y)−H(X,Y)$$I(X;Y)=H(X)+H(Y)-H(X,Y)$$

2.5 熵,相对熵与互信息的链式法则

定理2.5.1(熵的链式法则): H(X1,X2,…,Xn)=∑ni=1H(Xi|Xi−1,…,X1)$H(X_1,X_2,\dots ,X_n)=\sum _{i=1}^{n}H(X_i|X_{i-1},\dots ,X_1)$

定理2.5.2(互信息的链式法则): I(X1,X2,…,Xn;Y)=∑ni=1I(Xi;Y|Xi−1,…,X1)$I(X_1,X_2,\dots ,X_n;Y)=\sum _{i=1}^{n}I(X_i;Y|X_{i-1},\dots ,X_1)$

条件相对熵: D(p(y|x)||q(y|x))=∑xp(x)∑yp(y|x)logp(y|x)q(y|x)=Ep(x,y)logp(Y|X)q(Y|X)$D(p(y|x)||q(y|x))=\sum _{x}p(x)\sum _{y}p(y|x)\log \frac{p(y|x)}{q(y|x)}=E_{p(x,y)}\log \frac{p(Y|X)}{q(Y|X)}$

定理2.5.3(相对熵的链式法则): D(p(x,y)||q(x,y))=D(p(x)||q(x))+D(p(y|x)||q(y|x))$D(p(x,y)||q(x,y))=D(p(x)||q(x))+D(p(y|x)||q(y|x))$

2.6 Jensen不等式及其结果

定理2.6.2(Jensen不等式): 若给定凸函数f和一个随机变量X,则 Ef(X)≥f(EX)$Ef(X)\ge f(EX)$

定理2.6.3(信息不等式): D(p||q)≥0$D(p||q)\ge 0$

推论(互信息的非负性): I(X;Y)≥0$I(X;Y)\ge 0$

定理2.6.4: H(X)≤log|X|$H(X)\le \log |X|$

定理2.6.5(条件作用使熵减小): H(X|Y)≤H(X)$H(X|Y)\le H(X)$

从直观上讲,此定理说明知道另一随机变量Y的信息只会降低X的不确定度. 注意这仅对平均意义成立. 具体来说, H(X|Y=y)$H(X|Y=y)$ 可能比H(X)$H(X)$大或者小,或者两者相等.

定理2.6.6(熵的独立界): H(X1,X2,…,Xn)≤∑ni=1H(Xi)$H(X_1,X_2,\dots ,X_n)\le \sum _{i=1}^{n}H(X_i)$

2.7 对数和不等式及其应用

定理2.7.1(对数和不等式): ∑ni=1ailogaibi≥(∑ni=1ai)log∑ni=1ai∑ni=1bi$\sum _{i=1}^n{a}_i\log \frac{a_i}{b_i}\ge (\sum _{i=1}^n{a}_i)\log \frac{\sum _{i=1}^n{a}_i}{\sum _{i=1}^n{b}_i}$

定理2.7.2(相对熵的凸性): D(p||q)$D(p||q)$ 关于对(p,q)是凸的

定理2.7.3(熵的凹性): H(p)是关于p的凹函数

2.8 数据处理不等式

2.9 充分统计量

这节很有意思,利用统计量代替原有抽样,并且不损失信息.

2.10 费诺不等式

定理2.10.1(费诺不等式): 对任何满足 X→Y→X^,$X\to Y\to \hat{X},$ 设 Pe=Pr{X≠X^},$P_e=Pr\{X\ne \hat{X}\},$ 有

H(Pe)+Pelog|X|≥H(X|X^)≥H(X|Y)$$H(P_e)+P_e\log |\mathcal{X}|\ge H(X|\hat{X})\ge H(X|Y)$$

上述不等式可以减弱为

1+Pelog|X|≥H(X|Y)$$1+P_e\log |\mathcal{X}|\ge H(X|Y)$$

或

Pe≥H(X|Y)−1log|X|$$P_e\ge \frac{H(X|Y)-1}{\log |\mathcal{X}|}$$

引理 2.10.1: 如果X和X’独立同分布,具有熵H(X),则

Pr(X=X′)≥2−H(X)$$Pr(X=X^{\prime })\ge 2^{-H(X)}$$

3 渐进均分性

4 随机过程的熵率

4.1 马尔科夫链

4.2 熵率

4.3 例子:加权图上随机游动的熵率

4.4 热力学第二定律

4.5 马尔科夫链的函数

H(Yn|Yn−1,…,Y1,X1)≤H(Y)≤H(Yn|Yn−1,…,Y1)$$H(Y_n|Y_{n-1},\dots ,Y_1,X_1)\le H(\mathcal{Y})\le H(Y_n|Y_{n-1},\dots ,Y_1)$$

5 数据压缩

5.1 有关编码的几个例子

5.2 Kraft不等式

定理5.2.1(Kraft不等式): 对于D元字母表上的即时码,码字长度 l1,l2,…,lm$l_1,l_2,\dots ,l_m$必定满足不等式

∑iD−li≤1$$\sum _i{D}^{-l_i}\le 1$$

5.3 最优码

l∗i=−logDpi$$l_i^{\ast }=-{\log }_D{p}_i$$

5.4 最优码长的界

5.5 唯一可译码的Kraft不等式

5.6 赫夫曼码

5.7 有关赫夫曼码的评论

5.8 赫夫曼码的最优性

5.9 Shannon-Fano-Elias编码

5.10 香农码的竞争最优性

5.11由均匀硬币投掷生成离散分布

6 博弈与数据压缩

6.1 赛马

6.2 博弈与边信息

6.3 相依的赛马及其熵率

6.4 英文的熵

6.5 数据压缩与博弈

6.6 英语的熵的博弈估计

7 信道容量

离散信道: C=maxp(x)I(X;Y)$C=\underset{p(x)}{max}I(X;Y)$

7.1 信道容量的几个例子

7.2 对称信道

如果信道转移矩阵 p(y|x)$p(y|x)$ 的任何两行相互置换,任何两列也相互置换,那么称该信道是对称的.

7.3 信道容量的性质

7.4 信道编码定理预览

7.5 定义

7.6 联合典型序列

7.7 信道编码定理

7.8 零误差码

7.9 费诺不等式与编码定理的逆定理

7.10 信道编码定理的逆定理中的等式

7.11 汉明码

7.12 反馈容量

7.13 信源信道分离定理

8 微分熵

8.1 定义

h(X)=−∫Sf(x)logf(x)dx$$h(X)=-{\int }_{S}f(x)\log f(x)dx$$

均匀分布 h(X)=loga$h(X)=\log a$

正态分布 h(X)=1/2log2πeδ2$h(X)=1/2\log 2\pi e{\delta }^2$

8.2 连续随机变量的AEP

8.3 微分熵与离散熵的关系

8.4 联合微分熵与条件微分熵

8.5 相对熵与互信息

8.6 微分熵, 相对熵以及互信息的性质