1 绪论与概览

2 熵相对熵与互信息

2.1 熵

H(X)=−∑x∈Xp(x)log⁡p(x)" role="presentation" style="position: relative;">H(X)=−∑x∈Xp(x)logp(x)H(X)=−∑x∈Xp(x)log⁡p(x)

2.2 联合熵

H(X,Y)=−∑x∈X∑y∈Yp(x,y)log⁡p(x,y)" role="presentation" style="position: relative;">H(X,Y)=−∑x∈X∑y∈Yp(x,y)logp(x,y)H(X,Y)=−∑x∈X∑y∈Yp(x,y)log⁡p(x,y)

定理2.2.1(链式法则): H(X,Y)=H(X)+H(Y|X)" role="presentation" style="position: relative;">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)log⁡p(x)q(x)=Eplog⁡p(x)q(x)" role="presentation" style="position: relative;">D(p||q)=∑x∈Xp(x)logp(x)q(x)=Eplogp(x)q(x)D(p||q)=∑x∈Xp(x)log⁡p(x)q(x)=Eplog⁡p(x)q(x)

互信息(mutual information): I(X;Y)=∑x∈X∑y∈Yp(x,y)log⁡p(x,y)p(x)p(y)=D(p(x,y)||p(x)p(y))" role="presentation" style="position: relative;">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)=∑x∈X∑y∈Yp(x,y)log⁡p(x,y)p(x)p(y)=D(p(x,y)||p(x)p(y))

2.4 熵与互信息的关系

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

I(X;Y)=H(X)+H(Y)−H(X,Y)" role="presentation" style="position: relative;">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)=∑i=1nH(Xi|Xi−1,…,X1)" role="presentation" style="position: relative;">H(X1,X2,…,Xn)=∑ni=1H(Xi|Xi−1,…,X1)H(X1,X2,…,Xn)=∑i=1nH(Xi|Xi−1,…,X1)

定理2.5.2(互信息的链式法则): I(X1,X2,…,Xn;Y)=∑i=1nI(Xi;Y|Xi−1,…,X1)" role="presentation" style="position: relative;">I(X1,X2,…,Xn;Y)=∑ni=1I(Xi;Y|Xi−1,…,X1)I(X1,X2,…,Xn;Y)=∑i=1nI(Xi;Y|Xi−1,…,X1)

条件相对熵: D(p(y|x)||q(y|x))=∑xp(x)∑yp(y|x)log⁡p(y|x)q(y|x)=Ep(x,y)log⁡p(Y|X)q(Y|X)" role="presentation" style="position: relative;">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))=∑xp(x)∑yp(y|x)log⁡p(y|x)q(y|x)=Ep(x,y)log⁡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))" role="presentation" style="position: relative;">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)" role="presentation" style="position: relative;">Ef(X)≥f(EX)Ef(X)≥f(EX)

定理2.6.3(信息不等式): D(p||q)≥0" role="presentation" style="position: relative;">D(p||q)≥0D(p||q)≥0

推论(互信息的非负性): I(X;Y)≥0" role="presentation" style="position: relative;">I(X;Y)≥0I(X;Y)≥0

定理2.6.4: H(X)≤log⁡|X|" role="presentation" style="position: relative;">H(X)≤log|X|H(X)≤log⁡|X|

定理2.6.5(条件作用使熵减小): H(X|Y)≤H(X)" role="presentation" style="position: relative;">H(X|Y)≤H(X)H(X|Y)≤H(X)

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

定理2.6.6(熵的独立界): H(X1,X2,…,Xn)≤∑i=1nH(Xi)" role="presentation" style="position: relative;">H(X1,X2,…,Xn)≤∑ni=1H(Xi)H(X1,X2,…,Xn)≤∑i=1nH(Xi)

2.7 对数和不等式及其应用

定理2.7.1(对数和不等式): ∑i=1nailog⁡aibi≥(∑i=1nai)log⁡∑i=1nai∑i=1nbi" role="presentation" style="position: relative;">∑ni=1ailogaibi≥(∑ni=1ai)log∑ni=1ai∑ni=1bi∑i=1nailog⁡aibi≥(∑i=1nai)log⁡∑i=1nai∑i=1nbi

定理2.7.2(相对熵的凸性): D(p||q)" role="presentation" style="position: relative;">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^," role="presentation" style="position: relative;">X→Y→X^,X→Y→X^, 设 Pe=Pr{X≠X^}," role="presentation" style="position: relative;">Pe=Pr{X≠X^},Pe=Pr{X≠X^}, 有

H(Pe)+Pelog⁡|X|≥H(X|X^)≥H(X|Y)" role="presentation" style="position: relative;">H(Pe)+Pelog|X|≥H(X|X^)≥H(X|Y)H(Pe)+Pelog⁡|X|≥H(X|X^)≥H(X|Y)

上述不等式可以减弱为

1+Pelog⁡|X|≥H(X|Y)" role="presentation" style="position: relative;">1+Pelog|X|≥H(X|Y)1+Pelog⁡|X|≥H(X|Y)

或

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

Pr(X=X′)≥2−H(X)" role="presentation" style="position: relative;">Pr(X=X′)≥2−H(X)Pr(X=X′)≥2−H(X)

3 渐进均分性

4 随机过程的熵率

4.1 马尔科夫链

4.2 熵率

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

4.4 热力学第二定律

4.5 马尔科夫链的函数

5 数据压缩

5.1 有关编码的几个例子

5.2 Kraft不等式

定理5.2.1(Kraft不等式): 对于D元字母表上的即时码,码字长度 l1,l2,…,lm" role="presentation" style="position: relative;">l1,l2,…,lml1,l2,…,lm必定满足不等式

∑iD−li≤1" role="presentation" style="position: relative;">∑iD−li≤1∑iD−li≤1

5.3 最优码

li∗=−logD⁡pi" role="presentation" style="position: relative;">l∗i=−logDpili∗=−logD⁡pi

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)" role="presentation" style="position: relative;">C=maxp(x)I(X;Y)C=maxp(x)I(X;Y)

7.1 信道容量的几个例子

7.2 对称信道

如果信道转移矩阵 p(y|x)" role="presentation" style="position: relative;">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)log⁡f(x)dx" role="presentation" style="position: relative;">h(X)=−∫Sf(x)logf(x)dxh(X)=−∫Sf(x)log⁡f(x)dx

均匀分布 h(X)=log⁡a" role="presentation" style="position: relative;">h(X)=logah(X)=log⁡a

正态分布 h(X)=1/2log⁡2πeδ2" role="presentation" style="position: relative;">h(X)=1/2log2πeδ2h(X)=1/2log⁡2πeδ2

信息论基础 1~8