信息论与编码理论基础第二章

信息论与编码理论基础第二章2023/7/211第1页，课件共143页，创作于2023年2月§2.1离散型随机变量的非平均信息量（事件的信息量）2023/7/212第2页，课件共143页，创作于2023年2月非平均互信息量输入消息码字（输出）p(xk)收到0收到01收到011X1X2X3X4X5X6X7x80000010100111001011101111/81/81/81/81/81/81/81/81/41/41/41/40000001/21/2000000010000例2.1.12023/7/213第3页，课件共143页，创作于2023年2月非平均互信息量输入消息码字p(xk)收到0收到01收到011X1X2X3X4X5X6X7x80000010100111001011101111/81/41/81/41/161/161/161/161/61/31/61/30000001/32/30000000100002023/7/214第4页，课件共143页，创作于2023年2月直观认识对观察者来说，同样观察事件011，但输入消息等概情况下“收获”要大些，即得到的“信息”要多些。越是不太可能发生的事件竟然发生了，越是令人震惊。获得的“信息”要多些。2023/7/215第5页，课件共143页，创作于2023年2月非平均互信息量例2.1.2输入消息码字p(xk)收到0收到01收到010X1X20001111/21/21-pp1/21/21-pp1-p1-p0011pp2023/7/216第6页，课件共143页，创作于2023年2月直观认识在接收010的过程中，消息出现的可能性，即后验概率也在不断变化，但变化趋势不再像例2.1.1那样单调地变化，而是有起伏的，且最后并未达到1或0.观察到010之后不能断定是哪个消息出现了。但是由观察结果计算出来的某个消息出现的后验概率大于1/2或小于1/2,使我们可比未观察前较有把握地推断消息出现的可能性，因而多少得到了一些有关出现的“信息”。若p<1/2，则1-p>1/2，也即010是消息x1的输出可能性大。2023/7/217第7页，课件共143页，创作于2023年2月直观认识从上述两个系统可以看出，在一个系统中我们所关心的输入是哪个消息的问题，只与事件出现的先验概率和经过观察后事件出现的后验概率有关。信息应当是先验概率和后验概率的函数，即

I(xk;yj)=f[Q(x),P(xk|yj)]2023/7/218第8页，课件共143页，创作于2023年2月研究表明：信息量就表示成为事件的后验概率与事件的先验概率之比的对数函数!!!2023/7/219第9页，课件共143页，创作于2023年2月非平均互信息量（本章将给出各种信息量的定义和它们的性质。）定义2.1.1(非平均互信息量)给定一个二维离散型随机变量（因此就给定了两个离散型随机变量。事件xk∈X与事件yj∈Y的互信息量定义为2023/7/2110第10页，课件共143页，创作于2023年2月非平均互信息量直观认识若信源发某符号xi,由于信道中噪声的随机干扰，收信者收到的是xi的某种变形yj，收信者收到yj后，从yj中获取xi的信息量用I(xi;yj)表示，则有I(xi;yj)=[收到yj

前，收信者对信源发xi

的不确定性]-[收到yj

后，收信者对信源发xi仍然存在的不确定性]=收信者收到yj

前后，收信者对信源发xi

的不确定性的消除2023/7/2111第11页，课件共143页，创作于2023年2月非平均互信息量性质其中底数a是大于1的常数。常用a=2或a=e，当a=2时互信息量的单位为“比特”。互信息量的性质：（1）I(xk;yj)=loga(rkj/(qkwj))。因此有对称性：I(xk;yj)=I(yj;xk)。（2）当rkj=qkwj时I(xk;yj)=0。（即当(rkj/qk)=wj时，I(xk;yj)=0。又即当(rkj/wj)=qk时，I(xk;yj)=0。换句话说，当“X=xk”与“Y=yj”这两个事件相互独立时，互信息量为0）。2023/7/2112第12页，课件共143页，创作于2023年2月非平均互信息量性质（3）当rkj>qkwj时I(xk;yj)>0，当rkj<qkwj时I(xk;yj)<0。（当(rkj/qk)>wj时，I(xk;yj)>0；当(rkj/qk)<wj时，I(xk;yj)<0。换句话说，当“X=xk”与“Y=yj”这两个事件相互肯定时，互信息量为正值；当“X=xk”与“Y=yj”这两个事件相互否定时，互信息量为负值。）2023/7/2113第13页，课件共143页，创作于2023年2月条件互信息和联合事件互信息三个事件集的条件互信息定义（定义2.1.2）为可以推广到任意有限多个空间情况2023/7/2114第14页，课件共143页，创作于2023年2月互信息的可加性系统u1u2u3系统u1u2u3意味着：（u2,u3）联合给出的关于u1的信息量等于u2给出的关于u1的信息量与u2已知条件下u3给出的关于u1的信息量之和。2023/7/2115第15页，课件共143页，创作于2023年2月非平均自信息量定义2.1.3(非平均自信息量)给定一个离散型随机变量{X,xk,qk,k=1~K}。事件xk∈X的自信息量定义为I(xk)=loga(1/qk)，其中底数a是大于1的常数。自信息量的性质：（1）I(xk)≥0。（2）qk越小，I(xk)越大。（3）I(xk;yj)≤min{I(xk)，I(yj)}，即互信息量不超过各自的自信息量。证明注意到总有rkj≤min{qk,ωj}。（为什么？什么情况下相等？）。因此根据定义，I(xk;yj)≤I(xk)，I(xk;yj)≤I(yj)。得证。2023/7/2116第16页，课件共143页，创作于2023年2月非平均自信息量的直观认识若信源发某符号xi,没有信道中噪声的随机干扰，收信者收到的yj就是xi本身。收信者收到yj=xi后，当然就完全消除了对信源发符号xi的不确定性，即

[收到yj=xi

后，收信者对信源发xi仍然存在的不确定性]=0I(xi;xi)=[收到xi前，收信者对信源发xi

的不确定性]=I(xi)

2023/7/2117第17页，课件共143页，创作于2023年2月2023/7/2118第18页，课件共143页，创作于2023年2月2023/7/2119第19页，课件共143页，创作于2023年2月2023/7/2120第20页，课件共143页，创作于2023年2月条件的非平均自信息量定义2.1.4(条件的非平均自信息量)给定一个二维离散型随机变量{(X,Y),(xk,yj),rkj,k=1~K;j=1~J}。在事件yj发生的条件下事件xk的条件自信息量定义为I(xk|yj)=loga(1/P(X=xk|Y=yj))=loga(wj/rkj)。（条件的非平均自信息量实际上是非平均自信息量的简单推广，只不过将概率换成了条件概率）。

条件的非平均自信息量的特殊性质：I(xk|yj)=I(xk)-I(xk;yj)。2023/7/2121第21页，课件共143页，创作于2023年2月联合的非平均自信息量定义2.1.5(联合的非平均自信息量)给定一个二维离散型随机变量{(X,Y),(xk,yj),rkj,k=1~K;j=1~J}。事件(xk,yj)∈(X,Y)的自信息量定义为I(xk,yj)=loga(1/rkj)。（联合的非平均自信息量实际上是非平均自信息量的简单推广。即可以将(X,Y)直接看成是一维的随机变量）。

联合的非平均自信息量的特殊性质：I(xk,yj)=I(yj)+I(xk|yj)=I(xk)+I(yj|xk)。I(xk,yj)=I(xk)+I(yj)-I(xk;yj)。2023/7/2122第22页，课件共143页，创作于2023年2月非平均信息量（事件的信息量）小结非平均互信息量I(xk;yj)。非平均自信息量I(xk)，I(yj)。条件的非平均自信息量I(xk|yj)，I(yj|xk)。联合的非平均自信息量I(xk,yj)。相互关系：I(xk;yj)≤min{I(xk)，I(yj)}。I(xk|yj)=I(xk)-I(xk;yj)。I(xk,yj)=I(yj)+I(xk|yj)=I(xk)+I(yj|xk)。I(xk,yj)=I(xk)+I(yj)-I(xk;yj)。2023/7/2123第23页，课件共143页，创作于2023年2月联合自信息、条件自信息和互信息I(xk)I(yj)I(xk;yj)2023/7/2124第24页，课件共143页，创作于2023年2月§2.2离散型随机变量的平均自信息量——熵2023/7/2125第25页，课件共143页，创作于2023年2月2023/7/2126第26页，课件共143页，创作于2023年2月2023/7/2127第27页，课件共143页，创作于2023年2月2023/7/2128第28页，课件共143页，创作于2023年2月平均自信息量——熵定义2.2.1(平均自信息量——熵)离散型随机变量{X,xk,qk,k=1~K}的平均自信息量（又称为熵）定义为如下的H(X)，其中底数a是大于1的常数。2023/7/2129第29页，课件共143页，创作于2023年2月2023/7/2130第30页，课件共143页，创作于2023年2月2023/7/2131第31页，课件共143页，创作于2023年2月2023/7/2132第32页，课件共143页，创作于2023年2月平均自信息量——熵注意：（1）事件xk的自信息量值为I(xk)=loga(1/qk)，因此H(X)是随机变量X的各事件自信息量值的“数学期望”。（2）定义H(X)时，允许某个qk=0。（此时将qkloga(1/qk)

通盘考虑）此时补充定义qkloga(1/qk)=0。这个定义是合理的，因为2023/7/2133第33页，课件共143页，创作于2023年2月平均自信息量——熵例2.2.1

离散型随机变量X有两个事件x1和x2，P(X=x1)=p，P(X=x2)=1-p。则X的平均自信息量（熵）为H(X)=ploga(1/p)+(1-p)loga(1/(1-p))。观察H(X)（它是p的函数，图2.2.1给出了函数图象，该图象具有某种对称性），有当p=0或p=1时，H(X)=0。（随机变量X退化为常数时，熵为0）当0<p<1时，H(X)>0。p越靠近1/2，H(X)越大。（X是真正的随机变量时，总有正的熵。随机性越大，熵越大）当p=1/2时，H(X)达到最大。（随机变量X的随机性最大时，熵最大。特别如果底数a=2，则H(X)=1比特）2023/7/2134第34页，课件共143页，创作于2023年2月图2.2.1H(X)1.00.500.51P

2023/7/2135第35页，课件共143页，创作于2023年2月2023/7/2136第36页，课件共143页，创作于2023年2月2023/7/2137第37页，课件共143页，创作于2023年2月2023/7/2138第38页，课件共143页，创作于2023年2月2023/7/2139第39页，课件共143页，创作于2023年2月2023/7/2140第40页，课件共143页，创作于2023年2月2023/7/2141第41页，课件共143页，创作于2023年2月2023/7/2142第42页，课件共143页，创作于2023年2月条件平均自信息量（条件熵）定义2.2.2(条件熵)给定一个二维离散型随机变量{(X,Y),(xk,yj),rkj,k=1~K;j=1~J}。称如下定义的H(X|Y)为X相对于Y的条件熵。2023/7/2143第43页，课件共143页，创作于2023年2月§2.2离散型随机变量的平均自信息量（熵）定义2.2.3(联合熵)二维离散型随机变量{(X,Y),(xk,yj),rkj,k=1~K;j=1~J}的联合熵定义为2023/7/2144第44页，课件共143页，创作于2023年2月§2.2离散型随机变量的平均自信息量（熵）熵、条件熵、联合熵之间的关系：（1）H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y)。（由定义容易证明）（2）当X与Y相互独立时，H(Y|X)=H(Y)，因此此时H(X,Y)=H(X)+H(Y)。证明此时2023/7/2145第45页，课件共143页，创作于2023年2月§2.2离散型随机变量的平均自信息量（熵）熵的性质

对于随机变量{X,xk,qk,k=1~K}的熵H(X)=∑kqkloga(1/qk)，有以下的性质。1、H(X)与事件{xk,k=1~K}的具体形式无关，仅仅依赖于概率向量{qk,k=1~K}。而且H(X)与概率向量{qk,k=1~K}的分量排列顺序无关。2、H(X)≥0。完全同理，H(X|Y)≥0；H(Y|X)≥0；H(X,Y)≥0。3、确定性：当概率向量{qk,k=1~K}的一个分量为1时（此时其它分量均为0），H(X)=0。（这就是说，当随机变量X实际上是个常量时，不含有任何信息量）。2023/7/2146第46页，课件共143页，创作于2023年2月§2.2离散型随机变量的平均自信息量（熵）4、可忽略性：当随机变量X的某个事件的概率很小时，该事件对熵的贡献可以忽略不计。（虽然小概率事件的自信息量很大。这是因为当qk→0时，qkloga(1/qk)→0）。5、可加性：H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y)。因此，H(X,Y)≥H(X)；H(X,Y)≥H(Y)。（性质5有一个隐含的结论：设X的概率向量为{q1,q2,…,qK}，Y的概率向量为{q1,q2,…,qK-2,qK-1+qK}，其中qK-1qK>0，则H(X)>H(Y)。）2023/7/2147第47页，课件共143页，创作于2023年2月§2.2离散型随机变量的平均自信息量（熵）6、极值性：H(X)≤logaK。当q1=q2=…=qK=1/K时，才有H(X)=logaK。（以下是极值性的证明过程）引理1

对任何x>0总有lnx≤x-1。证明令f(x)=lnx-(x-1)，则f‘(x)=1/x-1。因此当0<x<1时f‘(x)>0；当x>1时f‘(x)<0。换句话说，当0<x<1时，f(x)的值严格单调增；当x>1时，f(x)的值严格单调减。注意到f(1)=0。所以对任何x>0总有f(x)≤f(1)=0。得证。2023/7/2148第48页，课件共143页，创作于2023年2月§2.2离散型随机变量的平均自信息量（熵）引理2

设有两个K维概率向量（什么叫概率向量？每个分量都是非负的，且各分量之和等于1）{qk,k=1~K}和{pk,k=1~K}。则总满足2023/7/2149第49页，课件共143页，创作于2023年2月§2.2离散型随机变量的平均自信息量（熵）证明注意到引理1，2023/7/2150第50页，课件共143页，创作于2023年2月§2.2离散型随机变量的平均自信息量（熵）引理2得证。（注意：此证明过程省略了若干细节，比如当概率向量的某个分量为0时，情况比较复杂）极值性的证明{qk,k=1~K}是一个K维概率向量。令pk=1/K，k=1~K。则{pk,k=1~K}也是一个K维概率向量。由引理2，H(X)=∑kqkloga(1/qk)≤∑kqkloga(1/(1/K))=logaK。得证。2023/7/2151第51页，课件共143页，创作于2023年2月§2.4离散型随机变量的平均互信息量2023/7/2152第52页，课件共143页，创作于2023年2月§2.4离散型随机变量的平均互信息量2023/7/2153第53页，课件共143页，创作于2023年2月§2.4离散型随机变量的平均互信息量定义2.4.1(平均互信息量)给定一个二维离散型随机变量{(X,Y),(xk,yj),rkj,k=1~K;j=1~J}（因此就给定了两个离散型随机变量{X,xk,qk,k=1~K}和{Y,yj,wj,j=1~J}）。X与Y的平均互信息量定义为如下的I(X;Y)：2023/7/2154第54页，课件共143页，创作于2023年2月注意：

①事件对(xk,yj)的“非平均互信息量”值为I(xk;yj)。

②此外，可以定义“半平均互信息量”I(xk;Y)和I(X;yj)。I(xk;Y)表示事件“X=xk”与随机变量Y之间的半平均互信息量；I(X;yj)表示事件“Y=yj”与随机变量X之间的半平均互信息量。2023/7/2155第55页，课件共143页，创作于2023年2月§2.4离散型随机变量的平均互信息量平均互信息量的性质

1、I(X;Y)≥0。（虽然每个“非平均互信息量”I(xk;yj)未必非负，但平均互信息量I(X;Y)非负）证明2023/7/2156第56页，课件共143页，创作于2023年2月§2.4离散型随机变量的平均互信息量{rkj,k=1~K;j=1~J}是一个概率向量：{qkwj,k=1~K;j=1~J}是另一个概率向量：故由引理2知，2023/7/2157第57页，课件共143页，创作于2023年2月§2.4离散型随机变量的平均互信息量2、对称性：I(X;Y)=I(Y;X)。3、平均互信息量的熵表示：I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)+H(Y)-H(XY)。证明2023/7/2158第58页，课件共143页，创作于2023年2月§2.4离散型随机变量的平均互信息量2023/7/2159第59页，课件共143页，创作于2023年2月§2.4离散型随机变量的平均互信息量3’、若X与Y相互独立，则I(X;Y)=0，H(X|Y)=H(X)，H(Y|X)=H(Y)，H(XY)=H(X)+H(Y)。证明若X与Y相互独立，则rkj=qkwj,k=1~K;j=1~J。因此此时loga(rkj/(qkwj))=0，k=1~K;j=1~J。因此I(X;Y)=0。再由性质3，性质3’得证。2023/7/2160第60页，课件共143页，创作于2023年2月§2.4离散型随机变量的平均互信息量4、I(X;Y)≤H(X)，I(X;Y)≤H(Y)。（性质4有多种简单的证明方法。第一种证明方法：由I(X;Y)的定义，loga(rkj/(qkwj))≤loga(1/qk)。第二种证明方法：由性质3，I(X;Y)=H(X)-H(X|Y)≤H(X)。）4’、若X是Y的确定的函数X=g(Y)，则I(X;Y)=H(X)≤H(Y)。若Y是X的确定的函数Y=g(X)，则I(X;Y)=H(Y)≤H(X)。（证略）2023/7/2161第61页，课件共143页，创作于2023年2月§2.4离散型随机变量的平均互信息量一般印象（平均互信息量I(X;Y)的各种性质与我们对“平均互信息量”这个名词的直观理解非常吻合）。一般情形：总有0≤I(X;Y)≤min{H(X),H(Y)}。一种极端情形：若X与Y相互独立，则I(X;Y)=0。另一种极端情形：若X、Y中有一个完全是另一个的确定的函数，则I(X;Y)=min{H(X),H(Y)}。2023/7/2162第62页，课件共143页，创作于2023年2月§2.4离散型随机变量的平均互信息量定理2.4.1(信息处理定理)对于以下给定的系统串联有：I(X;Y)≤I(X;Z)。信息处理定理的含义：串联的系统越多，两端的平均互信息量越小。信息处理定理的证明思想：注意到X、Z、Y构成了马尔可夫链。简单地说，在已知Z的条件下，X与Y条件独立。根据这种马尔可夫链结构，可以证明I(X;Y)≤I(X;Z)。（证略）2023/7/2163第63页，课件共143页，创作于2023年2月§2.1~§2.4诸概念直观理解两个事件的非平均互信息量：互相肯定的程度。一个事件的非平均自信息量：令人震惊的程度。一个随机变量的平均自信息量（熵）：不可预测的程度。一个随机变量X相对于另一个随机变量Y的条件熵：当Y的值确定时，X剩余的不可预测的程度。二维随机变量(XY)的联合熵：联合不可预测的程度。两个随机变量X与Y的平均互信息量：互相依赖的程度。（当Y的值确定时，X的可预测的程度；当Y的值确定时，所能够给出的X的信息量）（当X的值确定时，Y的可预测的程度；当X的值确定时，所能够给出的Y的信息量）事件X=x与随机变量Y的半平均互信息量：当X=x时，所能够给出的Y

的信息量。2023/7/2164第64页，课件共143页，创作于2023年2月§2.2和§2.4中的若干公式

恒等式I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)+H(Y)-H(XY)由定义容易看出第一类不等式H(X)≤logaK；I(X;Y)≥0；H(XY)≤H(X)+H(Y)；H(X|Y)≤H(X)；H(Y|X)≤H(Y)。根据引理1和引理2来证明第二类不等式I(X;Y)≤min{H(X),H(Y)}；H(XY)≥max{H(X),H(Y)}。根据概率论的基本事实来证明独立情形下的等式I(X;Y)=0，H(X|Y)=H(X)，H(Y|X)=H(Y)，H(XY)=H(X)+H(Y)。第一类不等式的特殊情形2023/7/2165第65页，课件共143页，创作于2023年2月§2.5连续型随机变量的平均互信息量和微分熵2023/7/2166第66页，课件共143页，创作于2023年2月事件互信息量定义2.5.1

给定二维连续型随机变量{(X,Y),p(X,Y)(x,y)}（因此就给定了两个连续型随机变量{X,pX(x)}和{Y,pY(y)}）。事件x∈X与事件y∈Y的互信息量定义为2023/7/2167第67页，课件共143页，创作于2023年2月平均互信息量定义2.5.2

给定二维连续型随机变量{(X,Y),p(X,Y)(x,y)}（因此就给定了两个连续型随机变量{X,pX(x)}和{Y,pY(y)}）。X与Y的平均互信息量定义为2023/7/2168第68页，课件共143页，创作于2023年2月平均互信息量性质平均互信息量的性质

1、I(X;Y)≥0。2、对称性：I(X;Y)=I(Y;X),3、信息处理定理：对于如下的系统串联有I(X;Y)≤I(X;Z)。4、2023/7/2169第69页，课件共143页，创作于2023年2月微分熵、相对熵（连续型随机变量为什么不能类似地定义平均自信息量——熵？这是因为，连续型随机变量的事件有无穷多个，每个事件发生的概率无穷小。如果类似地定义熵，则熵是无穷大。因此只能定义所谓“微分熵”，而“微分熵”的直观合理性大打折扣。比如“微分熵”可以是负的）微分熵的定义给定连续型随机变量{X,pX(x)}。X的微分熵(又称为相对熵)定义为2023/7/2170第70页，课件共143页，创作于2023年2月联合微分熵联合的微分熵的定义给定二维连续型随机变量{(X,Y),p(X,Y)(x,y)}。(X,Y)的联合的微分熵定义为2023/7/2171第71页，课件共143页，创作于2023年2月例题例2.5.1

设(XY)是连续型的二维随机变量，其联合分布密度函数pXY(xy)为二维高斯概率密度函数（二元正态密度函数）：2023/7/2172第72页，课件共143页，创作于2023年2月例题2023/7/2173第73页，课件共143页，创作于2023年2月例题例2.5.2设X~U(a,b)，求X的微分熵（相对熵）（我们将发现，X的相对熵未必非负）。2023/7/2174第74页，课件共143页，创作于2023年2月例题例2.5.3设X~N(m,σ2)，求X的微分熵（相对熵）（我们将发现，X的相对熵未必非负）。2023/7/2175第75页，课件共143页，创作于2023年2月例题熵功率2023/7/2176第76页，课件共143页，创作于2023年2月微分熵的极大化（已知：当离散型随机变量X的事件有K个时，H(X)≤logaK；只有当X服从等概分布时才有H(X)=logaK）1.峰值功率受限均匀分布相对熵最大定理2.5.1

若连续型随机变量X的取值范围在区间(-M,M)之内（即当x不在区间(-M,M)时，fX(x)=0），则Hc(X)≤loga2M；只有当X服从U(-M,M)分布时才有Hc(X)=loga2M。2023/7/2177第77页，课件共143页，创作于2023年2月微分熵的极大化2.平均功率受限高斯分布相对熵最大定理2.5.2

若连续型随机变量X的方差等于σ2

，则Hc(X)≤(1/2)loga(2πeσ2)；只有当X服从N(m,σ2)分布时才有Hc(X)=(1/2)loga(2πeσ2)。3.平均功率大于等于熵功率2023/7/2178第78页，课件共143页，创作于2023年2月§2.6凸函数与(离散型随机变量的)平均互信息量的凸性2023/7/2179第79页，课件共143页，创作于2023年2月凸函数凸集R：a，b属于R，qa+(1-q)b也属于R，其中0≤q≤1概率矢量矢量a的所有分量和为1上凸函数2023/7/2180第80页，课件共143页，创作于2023年2月凸函数的性质f(a)是上凸的，－f(a)是下凸的f1(a),…,fL(a)是R上的上凸函数，c1,…,cL是正数，c1f1(a)+…+cLfL(a)也是上凸函数f(a)是上凸函数，E[f(a)]≤f[E(a)],E为求数学期望2023/7/2181第81页，课件共143页，创作于2023年2月K-T条件f(a)是定义域R上的上凸函数，a是概率矢量。偏导数存在且连续，f(a)在R上为极大的充分必要条件2023/7/2182第82页，课件共143页，创作于2023年2月互信息的凸性记离散型随机变量X的事件为1，2，…，K。记X的概率分布为P(X=k)=qk，k=1~K。记离散型随机变量Y的事件为1，2，…，J。记条件概率P(Y=j|X=k)=p(j|k)。则rkj=P((X,Y)=(k,j))=qkp(j|k)，（概率论中的乘法公式）wj=P(Y=j)=∑kqkp(j|k)，（概率论中的全概率公式）2023/7/2183第83页，课件共143页，创作于2023年2月互信息的凸性p(j|k)给定，I(X;Y)是q(x)的上凸函数q=(q1,q2,…,qK)给定，I(X;Y)是p(j|k)的下凸函数2023/7/2184第84页，课件共143页，创作于2023年2月互信息的凸性设条件概率{p(j|k)，k=1~K，j=1~J}被确定。此时I(X,Y)是概率向量q=(q1,q2,…,qK)的函数。我们希望找到这样的概率向量，使得对应的I(X,Y)达到最大。这就是说，记我们希望找到这样的K维概率向量a=(a1,a2,…,aK)，使得2023/7/2185第85页，课件共143页，创作于2023年2月互信息的凸性（本节的核心内容是定理2.6.2，但它有太长的推导。）简述定理2.6.2的含义

K维概率向量a=(a1,a2,…,aK)使得当且仅当：以a为X的概率向量的时候，I(X=k;Y)对所有ak>0的k都取一个相同的值C；I(X=k;Y)对所有满足ak=0的k都取值不超过上述的相同值C

。其中2023/7/2186第86页，课件共143页，创作于2023年2月§2.6凸函数与(离散型随机变量的)平均互信息量的凸性I(X=k;Y)表示什么？表示事件X=k与随机变量Y之间的“半平均互信息量”。2023/7/2187第87页，课件共143页，创作于2023年2月§2.6凸函数与(离散型随机变量的)平均互信息量的凸性例设X的事件有0、1；Y的事件有0、1；已知p(0|0)=1-u；p(1|0)=u；p(0|1)=u；p(1|1)=1-u。当X服从等概分布（a0=P(X=0)=1/2；a1=P(X=1)=1/2）时，I(X;Y)达到最大。因为此时2023/7/2188第88页，课件共143页，创作于2023年2月§2.6凸函数与(离散型随机变量的)平均互信息量的凸性2023/7/2189第89页，课件共143页，创作于2023年2月习题课2.3掷一对无偏的骰子，若告诉你得到的总的点数为：(a)7；(b)12。试问各得到了多少信息量?[2.3的解答]这是求事件的自信息量。记随机变量X=“总的点数”，则所以，事件“X=7”的自信息量为log2(36/7)；事件“X=12”的自信息量为log2(36)。2023/7/2190第90页，课件共143页，创作于2023年2月习题课2.4经过充分洗牌后的一付扑克(含52张牌)，试问：(a)任何一种特定排列所给出的信息量是多少?(b)若从中抽取13张牌，所给出的点数都不相同时得到多少信息量?[2.4的解答]这是求事件的自信息量。(a)任一特定排列的概率都是(1/52!)，所以自信息量为log2(52!)；(b)从52张牌中抽取13张牌，共有种抽取方法。而使得所给出的点数都不相同的抽取方法有种。所以事件“点数都不相同”的概率为，自信息量为。2023/7/2191第91页，课件共143页，创作于2023年2月习题课2.6园丁植树一行，若有3棵白杨、4棵白桦和5棵梧桐。设这12棵树可随机地排列，且每一种排列都是等可能的。若告诉你没有两棵梧桐树相邻时，你得到了多少关于树的排列的信息?[2.6的解答]共有12！种不同的排列。满足“没有两棵梧桐树相邻”的排列个数为8×1+7×2+6×3+5×4+4×5+3×6+2×7+1×8=120（为什么？）记X=“树的排列情况”，Y=“梧桐树有无相邻位置”。则本题要求半平均互信息量2023/7/2192第92页，课件共143页，创作于2023年2月习题课X有12！个不同的事件x，每个事件x的概率为1/(12！)。Y有2个不同的事件，“Y=无”的概率为120/(12！)，“Y=有”的概率为(12！-120)/(12！)。以下要计算：在“Y=无”的条件下，X=x（x为某个特定排列）的条件概率P(X=x|Y=无)。若在x这个特定排列中，梧桐树有相邻位置，则P(X=x|Y=无)=0；若在x这个特定排列中，梧桐树无相邻位置，则2023/7/2193第93页，课件共143页，创作于2023年2月习题课2023/7/2194第94页，课件共143页，创作于2023年2月习题课2.7某校入学考试中有1/4考生被录取，3/4考生未被录取。被录取的考生中有50%来自本市，而落榜考生中有10％来自本市。所有本市的考生都学过英语，而外地落榜考生中以及被录取的外地考生中都有40%学过英语。(a)当己知考生来自本市时，给出多少关于考生是否被录取的信息?(b)当已知考生学过英语时，给出多少有关考生是否被录取的信息?(c)以x表示是否被录取，y表示是否为本市学生，z表示是否学过英语，x、y和z取值为0或1。试求H(x)，H(y|x)，H(z|y)。2023/7/2195第95页，课件共143页，创作于2023年2月[2.7的解答](a)是求事件“来自本市”与随机变量“是否被录取”的半平均互信息量。(b)是求事件“学过英语”与随机变量“是否被录取”的半平均互信息量。以x表示是否被录取（0表示被录取，1表示未被录取），y表示是否为本市学生（0表示本市学生，1表示非本市学生），z表示是否学过英语（0表示学过英语，1表示未学过英语），则P(xyz=000)=(1/4)×(50%)×1=12.5%；P(xyz=001)=(1/4)×(50%)×0=0；P(xyz=010)=(1/4)×(50%)×(40%)=5%；P(xyz=011)=(1/4)×(50%)×(60%)=7.5%；P(xyz=100)=(3/4)×(10%)×1=7.5%；P(xyz=101)=(3/4)×(10%)×0=0；P(xyz=110)=(3/4)×(90%)×(40%)=27%；P(xyz=111)=(3/4)×(90%)×(60%)=40.5%。2023/7/2196第96页，课件共143页，创作于2023年2月各个边际分布(xy)联合分布P(xy=00)=12.5%；P(xy=01)=12.5%；P(xy=10)=7.5%；P(xy=11)=67.5%。(xz)联合分布P(xz=00)=17.5%；P(xz=01)=7.5%；P(xz=10)=34.5%；P(xz=11)=40.5%。x概率分布P(x=0)=25%；P(x=1)=75%。y概率分布P(y=0)=20%；P(y=1)=80%。z概率分布P(z=0)=52%；P(z=1)=48%。(yz)联合分布P(yz=00)=20%；P(yz=01)=0；P(yz=10)=32%；P(yz=11)=48%。2023/7/2197第97页，课件共143页，创作于2023年2月习题课2023/7/2198第98页，课件共143页，创作于2023年2月习题课2023/7/2199第99页，课件共143页，创作于2023年2月习题课2.8在A、B两组人中进行民意测验，组A中的人有50%讲真话(T)，30%讲假话(F)，20%拒绝回答(R)。而组B中有30%讲真话，50%讲假话和20%拒绝回答。设选A组进行测验的概率为p，若以I(p)表示给定T、F或R条件下得到的有关消息来自组A或组B的平均信息量，试求I(p)的最大值。[2.8的解答]I(p)是什么信息量？记X=“选择的组号”，X的事件有A和B；Y=“得到的回答”，Y的事件有T、F、R。则I(p)=I(X;Y)。2023/7/21100第100页，课件共143页，创作于2023年2月习题课计算X的概率分布：P(X=A)=p；P(X=B)=1-p。计算Y的概率分布：P(Y=T)=p×50%+(1-p)×30%=30%+p×20%；P(Y=F)=p×30%+(1-p)×50%=50%-p×20%；P(Y=R)=p×20%+(1-p)×20%=20%。计算联合概率分布：P(XY=AT)=50p/100；P(XY=BT)=30(1-p)/100；P(XY=AF)=30p/100；P(XY=BF)=50(1-p)/100；P(XY=AR)=20p/100；P(XY=BR)=20(1-p)/100。2023/7/21101第101页，课件共143页，创作于2023年2月习题课2023/7/21102第102页，课件共143页，创作于2023年2月习题课2.9随机掷三颗骰子，以X表示第一颗骰子抛掷的结果，以Y表示第一和第二颗骰子抛掷的点数之和，以Z表示三颗骰子的点数之和。试求H(Z|Y)、H(X|Y)、H(Z|XY)，H(XZ|Y)和H(Z|X)。[2.9的解答]求H(Z|Y)，必须先求(YZ)的联合概率分布和Y的概率分布；求H(X|Y)，必须先求(XY)的联合概率分布和Y的概率分布；求H(Z|X)，必须先求(XZ)的联合概率分布和X的概率分布；求H(Z|XY)，必须先求(XYZ)的联合概率分布和(XY)的联合概率分布；求H(XZ|Y)，必须先求(XYZ)的联合概率分布和Y的概率分布。2023/7/21103第103页，课件共143页，创作于2023年2月(XYZ)的联合概率分布为：

P((XYZ)=(x,y,z))=1/216；x=1~6，y=x+1~x+6，z=y+1~y+6。

(XY)的联合概率分布为：

P((XY)=(x,y))=1/36；x=1~6，y=x+1~x+6。2023/7/21104第104页，课件共143页，创作于2023年2月习题课(YZ)的联合概率分布为：P((YZ)=(2,3))=1/63，P((YZ)=(2,4))=1/63，…，P((YZ)=(2,8))=1/63，P((YZ)=(3,4))=2/63，P((YZ)=(3,5))=2/63，…，P((YZ)=(3,9))=2/63，…，P((YZ)=(6,7))=5/63，P((YZ)=(6,8))=5/63，…，P((YZ)=(6,12))=5/63，P((YZ)=(7,8))=6/63，P((YZ)=(7,9))=6/63，…，P((YZ)=(7,13))=6/63，P((YZ)=(8,9))=5/63，P((YZ)=(8,10))=5/63，…，P((YZ)=(8,14))=5/63，…，P((YZ)=(11,12))=2/63，P((YZ)=(11,13))=2/63，…，P((YZ)=(11,17))=2/63，P((YZ)=(12,13))=1/63，P((YZ)=(12,14))=1/63，…，P((YZ)=(12,18))=1/63。2023/7/21105第105页，课件共143页，创作于2023年2月2023/7/21106第106页，课件共143页，创作于2023年2月习题课(XZ)的联合概率分布为：P((XZ)=(1,3))=1/63，P((XZ)=(1,4))=2/63，…，P((XZ)=(1,7))=5/63，P((XZ)=(1,8))=6/63，P((XZ)=(1,9))=5/63，…，P((XZ)=(1,12))=2/63，P((XZ)=(1,13))=1/63；P((XZ)=(2,4))=1/63，P((XZ)=(2,5))=2/63，…，P((XZ)=(2,8))=5/63，P((XZ)=(2,9))=6/63，P((XZ)=(2,10))=5/63，…，P((XZ)=(2,13))=2/63，P((XZ)=(2,14))=1/63；…，P((XZ)=(6,7))=1/63，P((XZ)=(6,8))=2/63，…，P((XZ)=(6,12))=5/63，P((XZ)=(6,13))=6/63，P((XZ)=(6,14))=5/63，…，P((XZ)=(6,17))=2/63，P((XZ)=(6,18))=1/63。2023/7/21107第107页，课件共143页，创作于2023年2月习题课2023/7/21108第108页，课件共143页，创作于2023年2月习题课X的概率分布：P(X=x)=1/6，其中x=1~6。Y的概率分布：当y=2~7时，P(Y=y)=(y-1)/36；当y=8~12时，P(Y=y)=(13-y)/36。Z的概率分布：

P(Z=3)=1/216，P(Z=4)=3/216，P(Z=5)=6/216，P(Z=6)=10/216，P(Z=7)=15/216，P(Z=8)=21/216，P(Z=9)=25/216，P(Z=10)=27/216，P(Z=11)=27/216，P(Z=12)=25/216，P(Z=13)=21/216，P(Z=14)=15/216，P(Z=15)=10/216，P(Z=16)=6/216，P(Z=17)=3/216，P(Z=18)=1/216。2023/7/21109第109页，课件共143页，创作于2023年2月习题课X值123456概率1/61/61/61/61/61/6Y值23456789101112概率1/362/363/364/365/366/365/364/363/362/361/36Z3456789101112131415161718概率13610152125272725211510631636363636363636363636363636363632023/7/21110第110页，课件共143页，创作于2023年2月将以上的概率分布代入以下的计算公式：2023/7/21111第111页，课件共143页，创作于2023年2月习题课2023/7/21112第112页，课件共143页，创作于2023年2月2023/7/21113第113页，课件共143页，创作于2023年2月习题课2.10设有一个系统传送10个数字：0,1,…,9。奇数在传送时以0.5的概率错成另外的奇数（？！），而偶数总能正确接收。试求收到一个数字平均得到的信息量。[2.10的解答]问题一：这是什么信息量？“收到一个数字平均得到的信息量”似乎指的是“收到的数字”这个随机变量的平均自信息量（熵）：H(收到的数字)。“发送一个数字x时，所给出的收到数字的平均信息量”应该指的是半平均互信息量：I(发送的数字=x；收到的数字)。“发送数字时，所给出的收到数字的平均信息量”应该指的是平均互信息量：I(发送的数字；收到的数字)。2023/7/21114第114页，课件共143页，创作于2023年2月习题课问题二：既然是求“收到的数字”这个随机变量的平均自信息量（熵），那么“收到的数字”的概率分布如何计算？假设“发送的数字”服从等概分布：P(发送的数字=j)=1/10，j=0~9则P(收到的数字=偶数x)=P(发送的数字=偶数x)=1/10；P(收到的数字=奇数x)=P(发送的数字=奇数x)×0.5+P(发送的数字=另个奇数u1)×0.125+P(发送的数字=另个奇数u2)×0.125+P(发送的数字=另个奇数u3)×0.125+P(发送的数字=另个奇数u4)×0.125=1/10(bits)2023/7/21115第115页，课件共143页，创作于2023年2月习题课这就是说，当假设“发送的数字”服从等概分布时，“收到的数字”服从等概分布。H(收到的数字)=log10。I(发送的数字；收到的数字)2023/7/21116第116页，课件共143页，创作于2023年2月习题课2.11令{ul,u2,…,u8}为一等概消息集，各消息相应被编成下述二元码字:ul=0000，u2=0011，u3=0101，u4=0110u5=1001，u6=1010，u7=1100，u8=1111码字通过转移概率为p的BSC传送。试求(a)接收的第一个数字0与ul之间的互信息量。(b)接收的前二个数字00与ul之间的互信息量。(c)接收的前三个数字000与ul之间酌互信息量。(d)接收的前四个数字0000与ul之间的互信息量。[2.11的解答]显然是求事件之间的（非平均）互信息量。首先什么是“转移概率为p的BSC”？解释如下（详见第四章）。2023/7/21117第117页，课件共143页，创作于2023年2月习题课“转移概率为p的BSC”是这样一种输入/输出机制：（1）在一个固定时刻，P(输出0|输入0)=P(输出1|输入1)=1-pP(输出1|输入0)=P(输出0|输入1)=p（2）在不同时刻的输入/输出操作是相互独立的：P(t1t2…tn时刻输出v1v2…vn|t1t2…tn时刻输入u1u2…un)=P(t1时刻输出v1|t1时刻输入u1)×P(t2时刻输出v2|t2时刻输入u2)×…×P(tn时刻输出vn|tn时刻输入un)2023/7/21118第118页，课件共143页，创作于2023年2月习题课(a)P(接收的第一个数字为0)=P(发送的第一个数字为0)×P(接收的第一个数字为0|发送的第一个数字为0)+P(发送的第一个数字为1)×P(接收的第一个数字为0|发送的第一个数字为1)=P(发送的第一个数字为0)×(1-p)+P(发送的第一个数字为1)×p=P(发送ul或u2或u3或u4)×(1-p)+P(发送u5或u6或u7或u8)×p=(1/2)×(1-p)+(1/2)×p=1/2。2023/7/21119第119页，课件共143页，创作于2023年2月习题课P(发送ul)=1/8。P(发送ul，且接收的第一个数字为0)=P(发送ul)×P(接收的第一个数字为0|发送ul)=P(发送ul)×P(接收的第一个数字为0|发送的第一个数字为0)=(1/8)×(1-p)。因此，I(发送ul；接收的第一个数字为0)2023/7/21120第120页，课件共143页，创作于2023年2月(b)P(接收的前两个数字为00)=P(发送的前两个数字为00)×P(接收的前两个数字为00|发送的前两个数字为00)+P(发送的前两个数字为01)×P(接收的前两个数字为00|发送的前两个数字为01)+P(发送的前两个数字为10)×P(接收的前两个数字为00|发送的前两个数字为10)+P(发送的前两个数字为11)×P(接收的前两个数字为00|发送的前两个数字为11)=P(发送ul或u2)×(1-p)2+P(发送u3或u4)×(1-p)p+P(发送u5或u6)×p(1-p)+P(发送u7或u8)×p2=1/42023/7/21121第121页，课件共143页，创作于2023年2月习题课P(发送ul，且接收的前两个数字为00)=P(发送ul)×P(接收的前两个数字为00|发送ul)=P(发送ul)×P(接收的前两个数字为00|发送的前两个数字为00)=(1/8)×(1-p)2。因此，I(发送ul；接收的前两个数字为00)2023/7/21122第122页，课件共143页，创作于2023年2月(c)P(接收的前三个数字为000)=P(发的前面为000)×P(收的前面为000|发的前面为000)+P(发的前面为001)×P(收的前面为000|发的前面为001)+P(发的前面为010)×P(收的前面为000|发的前面为010)+P(发的前面为011)×P(收的前面为000|发的前面为011)+P(发的前面为100)×P(收的前面为000|发的前面为100)+P(发的前面为101)×P(收的前面为000|发的前面为101)+P(发的前面为110)×P(收的前面为000|发的前面为110)+P(发的前面为111)×P(收的前面为000|发的前面为111)=P(发u1)×(1-p)3+P(发u2)×p(1-p)2+P(发u3)×p(1-p)2+P(发u4)×p2(1-p)+P(发u5)×p(1-p)2+P(发u6)×p2(1-p)+P(发u7)×p2(1-p)+P(发u8)×p3=1/82023/7/21123第123页，课件共143页，创作于2023年2月习题课P(发送ul，且接收的前三个数字为000)=P(发送ul)×P(接收的前三个数字为000|发送ul)=P(发送ul)×P(接收的前三个数字为000|发送的前三个数字为000)=(1/8)×(1-p)3。因此，I(发送ul；接收的前三个数字为000)2023/7/21124第124页，课件共143页，创作于2023年2月