要点
- 熵：$H(X)=E_{Xsim P}[I(X)]=-E_{Xsim P}[log P(x)]$
- 相对熵：$D_{p||g}=E[logfrac{p(x)}{g(x)}]geqslant 0$。
- 互信息：$I(X;Y)=sum_{x,y} P(x,y) log frac {P(x,y)}{P(x)P(y)}=H(X)-H(X|Y)=H(Y)-H(Y|X)$
- 渐进均分性质 AEP：$frac{1}{n}log(x_1,...,x_n) o H(X)$
- 数据压缩：$H(X)leqslant H(X)+1$
- 信道容量：$C=max_{p(x)} I(X;Y)$
- 数据传输：R<C，可以渐进达到无差错的通信。
- 高斯信道容量：$C=frac{1}{2}log(1+frac{P}{N})$
- 率失真：$R(D)=min I(X,hat{X})\,where\,E_{p(x)p(hat{x}|x)}d(X;hat{X})leqslant D$
- Kolmogorov 复杂度：$K(x)=min_{U(p)=x} l(p)$
- 普适概率：$-log P_U(x)=K(x)$
- 投资增长率：$W^*=max_{b^*}E[log b^tX]$
基础
熵
- 信息量：$-log p(x)$
- 概率分布P的香农熵：$H(p)=E_{Xsim p}[I(X)]=-E_{Xsim p}[log p(x)]=H(X)$，单调、非负、可加的泛函，凹函数。
- 条件熵：$H(Y|X) = -sum_{x,y}p(x,y) log frac {p(x,y)} {p(x)}$
- 联合熵：$H(X,Y) = -sum_{x,y}p(x,y) log {p(x,y)} = H(X) + H(Y|X)$
- KL距离、相对熵：$D_{KL}(p||q)=E_{Xsim P}[log frac{p(x)}{q(x)}]$半正定，对称性，可逆变换下不变性，凸函数。
- 互信息：$I(X;Y)=sum_{x,y} p(x,y) log frac {p(x,y)}{p(x)p(y)}=D(p(x,y)||p(x)p(y))=H(X)-H(X|Y)=H(Y)-H(Y|X)$。非负、对称性、可逆变换下不变性。
- 条件作用使熵减少：$H(X|Y)leqslant H(X)$
- $D(p||q)geqslant 0Rightarrow H(X)leqslantlog|X|$
- 最大熵原则：选择具有最大熵的概率分布。对于给定的方差，高斯分布具有最大熵$max_{EXX'=K}h(X)=frac{1}{2}log({2pi e})^n|K|$
- 估计误差与微分熵$E(x-hat{X})^2geqslantfrac{1}{2pi e} e^{2h(X)}$
链式法则
- 熵：$H(X_1,...,X_n)=sum_{i=1}^nH(X_i|X_{i-1},...,X_1)$
- 相对熵：$D(p(x,y)||q(x,y))=D(p(x)||q(x))+D(p(y|x)||q(y|x))$
- 互信息：$H(X_1,...,X_n;Y)=sum_{i=1}^nI(X_i;Y|X_{i-1},...,X_1)$
不等式
- Jensen: if f is convex, $f(EX)leqslant Ef(x)$
- 对数和不等式：$sum a_ilogfrac{a_i}{b_i}geqslant(sum a_i)log frac{sum a_i}{sum b_i}$
- 交叉熵：$H(p,q)=E_{Xsim p}[log q(x)]=H(p)+D_{KL}(p||q)$
- 数据处理不等式：$X o Y o ZRightarrow I(X;Y)geqslant I(X;Z)$。如果等号成立，称Y为X的充分统计量。
- 费诺不等式：对于任何满足$X o Y o hat{X},P_e=P{X eq hat{X}}$ $$H(P_e)+P_elog |X|geqslant H(X|hat{X})geqslant H(X|Y)$$
- $X,X',i.i.dRightarrow P(X=X')geqslant 2^{-H(X)}$
- 马尔可夫不等式$Rightarrow$
- 切比雪夫不等式，弱大数定律$$P{Xgeqslant t}leqslantfrac{E[X]}{t}Rightarrow P{|Y-mu|geqslant epsilon}leqslantfrac{sigma^2}{epsilon^2}, P{|ar{Z}_n-mu|geqslant epsilon}leqslantfrac{sigma^2}{nepsilon^2}$$
最大熵分布
最大熵分布：设f为概率密度函数，且满足$int_Sf(x)r_i(x)=alpha_i$。令$f^*(x)=f_lambda(x)=exp(lambda_0+sum_ilambda_ir_i)$，选择$lambda_i$满足约束，则$f^*$为唯一使得$h(f)$达到最大值的分布函数。
[Burg最大熵]满足$E[X_iX_{i+k}]=alpha_k$的最大熵率随机过程为p阶的高斯-马尔可夫过程$X_i=-sum_ka_kX_{i-k}+Z_i,Z_isim N(0,sigma^2),a_k$通过Yule-Walker方程组得到。
最大熵密度估计：如果随机过程的熵率可以被满足自相关约束条件$R(p)$的p阶0均值的高斯-马尔可夫过程最大化，那么最大熵率是$$h^*=frac{1}{2}log(2pi e)|frac{K_p}{K_{p-1}}|$$最大熵谱密度为$$S(lambda)=frac{sigma^2}{|1+sum_kq_ke^{-iklambda}|^2}$$
渐进均分性AEP
$AEP：X_isim p(x)为i.i.d序列，则-frac{1}{n}log p(X_1,...,X_n) o H(X)$
典型集：$$A_epsilon^{(n)}={x^n:-frac{1}{n}log p(x^n)-H(X)|leqslant epsilon}$$ $$(1-epsilon)2^{n(H(X)-epsilon)}leqslant |A_epsilon^{(n)}|leqslant 2^{n(H(X)+epsilon)}$$
联合典型集：$$A_epsilon^{(n)}={(x^n,y^n)in(X^n,X^n):|-frac{1}{n}log p(x^n)-H(X)|leqslant epsilon,|-frac{1}{n}log p(y^n)-H(Y)|leqslant epsilon,|-frac{1}{n}log p(x^n,y^n)-H(X,Y)|leqslant epsilon}$$ $$|A_epsilon^{(n)}|leqslant 2^{n(H(X,Y)+epsilon)},P((X^n,Y^n)in A_epsilon^{(n)})leqslant 2^{-n(I(X;Y)-3epsilon)}$$
压缩：$X^nsim p(x)为i.i.d序列，则存在一个编码，对于充分大的n，有E[frac{1}{n}l(X^n)]leqslant H(X)+epsilon$
一阶指数意义相等：$adoteq biff lim_{n oinfty}frac{1}{n}logfrac{a_n}{b_n}=0$
最小概率集：$X_isim p(x)为i.i.d序列，则对于delta<frac{1}{2}，设B_delta^{(n)}subset X^n$是使$P{B_delta^{(n)}}geqslant 1-delta$成立的最小集合，则$|B_delta^{(n)}|doteq |A_epsilon^{(n)}| doteq 2^{nH}$
随机过程的熵
随机过程的熵率：$H(chi)=lim_{n oinfty}frac{1}{n}H(X_1,...,X_n)$
平稳随机过程的熵率：$H(chi)=H'(chi)=lim_{n oinfty}frac{1}{n}H(X_n|X_1,...,X_{n-1})$
Cesaro均值：$a_n o awedge b_n=frac{1}{n}sum a_iRightarrow b_n o a$
平稳马尔可夫链的熵率：$H(chi)=H(X_2|X_1)=sum_{i,j}mu_iP_{ij}log P_{ij}$
$X_i$为平稳马尔可夫链，且$Y_i=Phi(X_i)$，那么$H(Y_n|Y_{n-1},...,Y_1,X_1)leqslant H(Y)leqslant H(Y_n|Y_{n-1},...,Y_1)$，并且$lim H(Y_n|Y_{n-1},...,Y_1,X_1)=H(Y)=lim H(Y_n|Y_{n-1},...,Y_1,X_1)$
热力学第二定律
- 相对熵$D(mu||mu')$随$n$递减。
- 如平稳分布为均匀分布，则熵增加
- 对于平稳的马尔可夫过程，条件熵$H(X_n|X_1)$随$n$递增。
统计学
序列$x_nin X$的型：$forall a,P_x(a)=N(a|x)/N$
序列$x_nin X$的型类：$$T(P)={xin X^n:P_x=P},frac{1}{(n+1)^{|X|}}2^{nH(P)}leqslant|T(P)|leqslant 2^{nH(P)}$$
$X_nsim Q(X)为i.i.d$，则$$Q^n(x)=2^{-n(H(P_x)+D(P_x||Q)},frac{1}{(n+1)^{|X|}}2^{-nD(P||Q)}leqslant|T(P)|leqslant 2^{-nD(P||Q)}$$
信源与信道
数据压缩
- 信源编码$C:X o D^*,L(C)=sum_{xin X}p(x)l(x)$
- 非奇异：$x eq x' Rightarrow C(x) eq C(x')$
- 扩展编码：$C(x_1...x_n)=C(x_1)...C(x_n)$
- 唯一可译：扩展编码非奇异。
- 前缀码：无任何码字是其它码字的前缀。Kraft不等式：$sum_iD^{-l_i}leqslant 1$，$l_i$为码字长度，$D$为字母个数。
- $sum_iD^{-l_i}leqslant 1, L=sum p_il_iRightarrow H_D(X) leqslant Lwedge L^*< H_D(X)+1$
- 码长分配：$l(x)=left lceil frac{1}{q(x)} ight ceil$关于$p(x)$的期望码长满足：$H_D(X)+D(p||q) leqslant E_pl(X)< H_D(X)+D(p||q)+1$
- 哈夫曼码：按照概率排序分配码字。最优性：$L(C^*)leqslant L(C')$
- SFL编码：$left lfloorsum_{a<x}p(a) +frac{1}{2}p(x) ight floor_{l(x)}$
- 竞争最优性：$l(x)=left lceil frac{1}{p(x)} ight ceilRightarrowforall l'(P[l(X)geqslant l'(X)+c])leqslant 2^{1-c}$
信道容量
离散信道：输入字母表$X$，输出字母表$Y$，概率转移矩阵$p(y|x)$。信道容量：可区别信号数目的对数值，或者可达码率的上确界$$C=max_{p(x)}I(X;Y)$$
$(M,n)$码：下标集${1,...,M}$，编码函数$X^n:{M} o X$，译码函数$g:Y o {M}$。条件误差概率：$lambda_i=sum_yp(y|X^n(i))I(g(y) eq i)$。平均误差概率：$P_e^{(n)}=frac{1}{M}sumlambda_i$。码率：$R=frac{log M}{n}$
信道编码定理：对于离散无记忆信道$DMC$，小于信道容量$C$的所有码率都是可达的。对于任意码率$R<C,exists (2^{nR},n),lambda^{(n)} o 0$。反之亦然。
信源信道定理：如果随机过程的熵率$H>C$，则该过程不可能通过$DMC$可靠传输。如果满足$AEP,H<C$，则传输可靠。
高斯信道：$Y_i=X_i+Z_i,Z_isim N(0,N)$，噪声$Z_i$与信号$X_i$相互独立。
功率限制$frac{1}{n}sum_{i=1}^nx_i^2leqslant P$。
信道容量：$$C=max_{f(x):E[X^2]leqslant P}I(X;Y)=frac{1}{2}log(1+frac{P}{N})$$
噪声谱密度$frac{N_0}{2}$，带宽$W$的高斯信道容量：$C=Wlog(1+frac{P}{W})$
- 并联k个高斯信道：$C=sum_ifrac{1}{2}log(1+frac{(v-N_i)^+}{N_i}),sum(v-N_i)^+=nP$
- 并联k个，彩色噪声的高斯信道：$C=frac{1}{n}sum_ifrac{1}{2}log(1+frac{(v-lambda_i)^+}{lambda_i}),sum(v-lambda_i)^+=P,lambda$为$K$的特征值。
- 无反馈容量：$C_n=max_{tr(K_X)leqslant nP}frac{1}{2n}logfrac{|K_X+K_Z|}{|K_Z|}$
率失真函数
率失真：信源$Xsim p(x)$，率失真度量$d(x,hat{x})$，率失真函数$$R(D)=min_{p(hat{x}|x):sum_{(x,hat{x})} p(x)p(hat{x}|x)d(x,hat{x})leqslant D}I(X;hat{X})$$
- 伯努利信源：$R(D)=H(p)-H(D)$
- 高斯信源：$frac{1}{2}logfrac{sigma^2}{D}$
率失真定理：如果$R>R(D)$，则存在码字数目为的码序列，使得。若$R<R(D)$，则码序列不存在。
信道容量与率失真函数的EM算法：$$R(D)=min_{pin A}min_{q(hat{x})in B}D(p||q)$$
网络信息论
- 多接入信道：$X_1,X_2,Y,p(y|x_1,x_2)$。容量区域为满足下面条件的$(R_1,R_2)$的凸闭包。$$R_1<I(X_1;Y|X_2),R_2<I(X_2;Y|X_1),R_1+R_2<I(X_1,X_2;Y)$$
- 高斯多接入信道：$R_1leqslant C(frac{P_1}{N}),R_2leqslant C(frac{P_2}{N}),R_1+R_2leqslant C(frac{P_1+P_2}{N}),C(x)=frac{1}{2}log(1+x)$
- 分布式信源编码：$R_1geqslant H(X|Y),R_2geqslant H(Y|X),R_1+R_2geqslant H(X,Y)$。利用$H(Y|X)$对Y编码，因为与X构成典型序列的Y并不多。
- 退化广播信道：$X o Y_1 o Y_2$。容量区域为满足下面条件的$(R_1,R_2)$的凸闭包。$$exists p(u)p(x|u)p(y_1,y_2|x)Rightarrow R_2leqslant I(U;Y_2),R_1leqslant I(X;Y_1|U),|U|leqslant min(|X|,|Y_1|,|Y_2|)$$
- 物理退化中继信道：$p(y,y_1|x,x_1)$的容量$$C=sup_{p(x,x_1)}min{I(X,X_1;Y),I(X;Y_1|X_1) }$$
- 具有边信息的信源编码，设$(X,Y)sim p$，码率为$R_1,R_2$，X可以任意小的误差概率恢复$iff exists p(y,u), X o Y o URightarrow R_2geqslant I(U;Y),R_1geqslant H(X|U)$
- 具有边信息的率失真，设$(X,Y)sim p$ $$ R_Y(D)=min_{p(w|x)}min_{f:Y imes W o X}I(X;W)-I(Y;W)$$
参考文献
- Thomas M. Cover, etal, Elements of Information Theory, Second Edition, John Wiley & Sons, Inc.