信息论第5讲——平均互信息的凸性(含习题)

1、平均互信息平均互信息 定义及含义定义及含义 信息信息/数据处理定理数据处理定理Review)()()()|()()|()();(XYHYHXHXYHYHYXHXHYXI);();();();(VUIYXIZXIYXI 凸性凸性 性质：性质： 对称性、非负性、极值性对称性、非负性、极值性凸集凸集若集合若集合nRC（n维欧氏空间），有维欧氏空间），有CqCp , 且对任意实数且对任意实数有有(1),pqC显然，显然，n维欧氏空间维欧氏空间 为一凸集合。为一凸集合。01则称为则称为C为凸集合。为凸集合。概率矢量构成集合为凸集概率矢量构成集合为凸集定义定义 若一个若一个K维矢量维矢量 =( 1, 2,

2、 , K)的所有分量的所有分量为非负的，且和为为非负的，且和为1，即就称，即就称 为概率矢量。为概率矢量。引理引理 概率矢量全体所构成的区域概率矢量全体所构成的区域R是凸的。是凸的。证：若证：若 ,R，对，对0 1构造矢量构造矢量 =(1- )Kkakkk, 2, 10)1 (因此因此 是概率矢量，仍属于是概率矢量，仍属于R，所以，所以R是凸的。是凸的。KkKkkkKkka1111)1 (凸函数定义凸函数定义定义在凸集定义在凸集R上的一个上的一个实函数实函数f，若它对所有，若它对所有,R和和0 1满足满足 f( )+(1 ) f ()f ( (1 ) 就称函数就称函数f为为R上的上的凸凸函数函

3、数。若式中不等号的方向相反，就称若式中不等号的方向相反，就称f为为凸凸函数函数。若等号仅当若等号仅当 =0或或1时成立，就称时成立，就称f为为严格凸严格凸或严格凸或严格凸的。的。在在a,b上定义的上凸函数上定义的上凸函数在在a,b上定义的下凸函数上定义的下凸函数凸函数性质凸函数性质1) 若若f( )是凸是凸的，则的，则-f( )是凸是凸的，反过来也成立。的，反过来也成立。 2) 若若f1( ), f2( ), fL( )是是R上的凸上的凸函数，函数，c1,c2,cL是正是正数，则数，则 为为R上的凸上的凸函数，若其中任一个是严函数，若其中任一个是严格凸的，则和式也是严格凸的。格凸的，则和式也是

4、严格凸的。 Llllfc1)(3) (Jensen不等式不等式) 若若f( )是是R上的凸上的凸函数，则函数，则Ef( ) f (E ( )Jensen不等式不等式:若f( )是R上的凸函数，则 E f( ) f (E ( ) 其中，E表示数学期望。证明证明：只对离散情况证明。 对于离散变量，令 ，则E f( ) f (E ( ) 可写成可用归纳法进行证明。对两点分布，根据凸函数的定义有假设当分布点个数为n时不等式成立，考察分布点个数为n+1时的情况。Llllpp11, 011221()()LLLlllf pppp f1212(1)()(1) ()fff对 ，令 则有 证毕证毕 111, 0n

5、iiippniip1 1111111111111111()()()()()()1() nnnnnnnnniinniniinniniiip fp fpfppffpffppffppfp定理定理: 如果函数f(x)在某个区间上存在非负(正)的二阶导数，则 f(x)为该区间上的凸函数(严格凸函数)。 证明证明：利用函数f(x)在x0点的泰勒级数展开:其中x*位于x0和x之间。根据假设 ，因此，对任意的x，最后一项总是非负。设 取 ，可得类似地，取 ，可得20000( *)( )()()()()2fxf xf xfxxxxx( *)0fx012(1)xxx1xx10012()()(1)()()f xf

6、xfxxx2xx20021()()()()f xf xfxxx因此，得 证毕证毕 同理可证：如果函数f(x)在某个区间上存在的二阶导数0（0 对所有对所有 k k =0 =0 )(f)(kf)(kf其中为一常数。证证：首先证明充分性。首先证明充分性。设函数f在 点满足KT条件，今证明 为极大值，即对任意 ，恒有 。由于f是凸函数，所以 f ( )(1 ) f ( )f (1 ) 0 1即f ( )f ( )f (1 ) f ( )/ 01R( )( ) 0ff( )f 1211122212111222122212221( )(,)(1) )( )(),(),()(,)(),(),()(,(),

7、()(,(),()(KKKKKKKKKKKKKKffffffffff 21212112,()(,()(,()(,)KKKKKKkKKKKfff 0(1)()()()lim( )()kkkkfffff 因上式对任意 (0 1)成立，可令 0，得由KT条件有将其代入上式得从而证明 为极大值。现在证明必要性。令 使f 达到极大值，并假定偏导数在 处连续。则对任意 ,有式中01。以除两边并令0 得)()()(kkkkkf0)()(11KkKkkkff( )f RR0)()1(ff0)1(0ddf即因 为是概率矢量，所以至少有一个分量，例如i是严格正的，即i0。选择另一概率矢量满足式中 。于是有对于 也

8、可选负值和正数，有 和kikkkkf0)()(ilkllilkl其 它 值( )( )0kiff0,k1( )( )0kff1( )( )0kff即( )( )kiff对对 ，因为概率矢量的关系，只能选择，因为概率矢量的关系，只能选择 ，由此得，由此得0k0( )( )kiff证毕证毕熵的凸性熵的凸性证明：证明：),(112111KpppP),(222212KpppP10)()1 ()()1 (2121PHPHPPH令令则则KiiiiiPpPpPPH1212121)1 (log()1 ()1 (KiiiiKiiiiPpPPpp12121211)1 (log()1 ()1 (log(1)1 (1

9、21KiiiPp由于由于KiiiKiiippppPPH12211121log1log)1 ()()1 ()(21PHPH当且仅当当且仅当 时等号成立时等号成立21PP p平均互信息量凸性平均互信息量凸性由互信息的定义式：由互信息的定义式：可知，它是输入分布可知，它是输入分布 及转移概率分布及转移概率分布 的函数。的函数。可以记为：可以记为： 如果转移概率分布固定，I(X,Y)就是先验概率Q(X)的函数； 如果信源先验概率固定，I(X,Y)就是转移概率P(Y/X)的函数。( )q x( / )p y x(;)( ),(/)I X Yf Q xP yxxyyxypxypxqYXI)()(log)(

10、)()(；例例 设二元对称信道(BSC)的信源空间为：X=0,1; Q(X)=, 1-; 0 1-p 0 p p 1 1-p 1因为已知转移概率，所以利用公式I(X,Y)=H(Y)-H(Y/X) 。 H(Y/X)=-q(xi) p(yj/xi) log p(yj/xi) =q(xi) -plog p+(1-p) log (1-p) =H(p) 其中：H(p)= -plog p+(1-p) log (1-p) 另外：为了求H(Y)，利用w(yj)= q(xi) p(yj/xi)；可得： w(y=0)=(1-p)+(1-)p w(y=1)=p+(1-)(1-p)所以：H(Y)=-(1-p)+(1-

11、)plog(1-p)+(1-)p+p+(1-)(1-p)logp+(1-)(1-p) =H(1-p)+(1-)p) 可得平均互信息量为： I(X,Y)=H(1-p)+(1-)p)-H(p)当固定信源先验概率分布当固定信源先验概率分布时，时，I(X,Y)是信道转移概率是信道转移概率p的下凸函数的下凸函数，如图所示。 0 1/2 1 p从图中可知，当信源固定后，存在一种BSC信道，p=(1-p)=1/2，使在信道输出端获得信息量最小，即等于0。也就是说，信源的信息全部损失在信道中了。这是最差的信道，这个性质说明，每个信源都存在一种最差的信道，此信道的干扰最大。 I(X,Y) H() 根据这个关系，

12、当当p值一定，即固定信道，可知值一定，即固定信道，可知I(X,Y)是是的上凸函数的上凸函数，其曲线如图： I(X,Y) 1-H(p) 0 1/2 1 从图中可知，当BSC信道的信道矩阵固定后，若输入符号集X的概率分布不同，在接收端平均每个符号获得的信息量就不同。只有当输入为等概分布时即，p(0)=p(1)=1/2时，接收端的信息量才为最大值1-H(p)。定理定理2.5.2 当条件分布当条件分布 p(y/x)给定时，平均互信息给定时，平均互信息I(X;Y)是是输入分布输入分布q(x)的凸的凸函数。函数。证明：令q1和q2是输入集X上的任意两个概率矢量，相应的互信息为I1和I2，令满足01，q=q

13、1(1)q2是合成概率矢量，此时输入X和输出Y之间的互信息为I。 今需要证明: . 令p1(xy)=q1(x)p(y/x), p2(xy)=q2(x)p(y/x), 有 p(xy)= q(x)p(y/x)=p1(xy) (1) p2(xy) 1122( )(),( )()xxw yp xyw yp xyIII21)1 (12( )()( )(1)( )xw yp xyw yw y根据平均互信息的定义，得因为 log x 是严格凸函数，所以 证毕121212121212()()(1)()log(1)()log( )( )()()(1)()log( )( )( )()log(1)()log( )(

14、 )xyxyxyxyxyp y xp y xIIIp xypxyw ywyp y xp xypxyw yw yw yp xypxyw ywy12121212121212( )( )(1)()log(1)()log( )( )( )( )log()(1)log()( )( )( )( )log()(1)log()( )( )0 xyxyxyxyyxyxw yw yIIIp xypxyw ywyw yw yp xypxyw ywyw yw yp xypxyw ywy 当信道一定时，平均互信息是信源先验概率的上凸函数当信道一定时，平均互信息是信源先验概率的上凸函数1) 对于一定的信道转移概率分布，总

15、可以找到一个对于一定的信道转移概率分布，总可以找到一个先验概率分布为先验概率分布为P的信源的信源X，使平均互信息达到相，使平均互信息达到相应的最大值应的最大值Imax，这时称这个信源为该信道的匹，这时称这个信源为该信道的匹配信源。配信源。2) 不同的信道转移概率对应不同的不同的信道转移概率对应不同的Imax，或者说，或者说Imax是是P(Y/X)的函数。的函数。 平均互信息的凸性平均互信息的凸性定理定理2.5.3 当集当集X的概率分布保持不变时，平均互信息量是的概率分布保持不变时，平均互信息量是条件概率分布条件概率分布p(y/x)的凸的凸函数。函数。证明：令p1和p2是两个任意条件概率分布，相

16、应的平均互信息为I1和I2，令满足01,p=p1(1)p2是合成条件概率分布，此时输入X和输出Y之间的互信息为I。今需要证明 . 令 根据平均互信息的定义，得12(1)III1111122222( )( )( / ),( /)( )( / )/( )( )( )( / ),( /)( )( / )/( )( )( )( / ),( /)( ) ( / )/( )xxxw yq x py xp x yq x py xw ywyq x py xpx yq x py xwywyq x py xp x yq x p y xwy因为logx是严格凸函数，所以 证毕121212121212()(1)( )

17、(/ )(1) ( )(/ )log( )()()( )(/ )log(1)( )(/ )log( )( )()()( )(/ )log(1)( )(/ )log( /)( /)xyxyxyxyxyp x yIIIq x py xq x py xq xpx ypx yq x py xq x py xq xq xp x yp x yq x py xq x py xpxypxy121212121212()()(1)log( ) ( / ) (1)log( )( / )( / )( / )()()log() (1)log()( / )( / )log( ) () (1)log( ) ()0 xyxy

18、xyxyxyxyp x yp x yIIIq x p y xq x p y xp x yp x yp x yp x yp xyp xyp x yp x yw y p x yw y p x yn 当信源一定，平均互信息是信道转移概率的下凸函数当信源一定，平均互信息是信道转移概率的下凸函数1) 对于一个已知先验概率为对于一个已知先验概率为P的离散信源，总可以找到一的离散信源，总可以找到一个转移概率分布为个转移概率分布为P(Y/X)的信道，使平均互信息达到相的信道，使平均互信息达到相应的最小值应的最小值Imin。2) 可以说不同的信源先验概率对应不同的可以说不同的信源先验概率对应不同的Imin，或者

19、说，或者说Imin是是P(X)的函数。即平均互信息的最小值是由体现了信源的函数。即平均互信息的最小值是由体现了信源本身的特性。本身的特性。 平均互信息的凸性平均互信息的凸性本章小结本章小结 熵、互信息定义及含义熵、互信息定义及含义互信息互信息与熵的关系与熵的关系 信息处理定理信息处理定理)()()()|()()|()();(XYHYHXHXYHYHYXHXHYXI);();(ZXIYXI 凸性凸性信道一定时，平均互信息是信源先验概率的上凸函数信道一定时，平均互信息是信源先验概率的上凸函数信源一定时，平均互信息是信道转移概率的下凸函数信源一定时，平均互信息是信道转移概率的下凸函数 微分熵的定义及

20、与熵的差别微分熵的定义及与熵的差别27个硬币中有一个重量偏轻，其它个硬币中有一个重量偏轻，其它26个为标准个为标准重量。重量。试用信息量观点分析在试用信息量观点分析在不用砝码的天平上至少不用砝码的天平上至少称多少次，就能发现这个轻的硬币？怎样称？称多少次，就能发现这个轻的硬币？怎样称？思考思考:设有设有4枚同值硬币，其中枚同值硬币，其中1枚硬币可能是假币，枚硬币可能是假币，如是假币，其重量与真币不同，但不知比真币如是假币，其重量与真币不同，但不知比真币轻还是重。现在给你一部没有砝码的天平和轻还是重。现在给你一部没有砝码的天平和1枚真币，要求你回枚真币，要求你回答有无假币？如答有无假币？如有假币

21、要求有假币要求找出那枚假币，并指出那枚假币是比真币轻还找出那枚假币，并指出那枚假币是比真币轻还是重？是重？试用信息量观点分析最少需称多少次才能保证试用信息量观点分析最少需称多少次才能保证一定能找出那枚假币，并给出具体称法。一定能找出那枚假币，并给出具体称法。思考思考:第二章 习题2.1 莫尔斯电报系统中，若采用点长为莫尔斯电报系统中，若采用点长为0.2s，划长为，划长为0.4s，且点和划出现的概率分别为且点和划出现的概率分别为2/3和和1/3，试求它的信息，试求它的信息速率速率(bits/s)。解: 平均每个符号长为 秒秒 每个符号的熵为 比特比特 所以，信息速率为 比特比特/秒秒1544 .

22、0312 .0329183. 03log3123log32444. 34159183. 02.3 掷一对无偏的骰子，若告诉你得到的总的点数为：掷一对无偏的骰子，若告诉你得到的总的点数为：(a) 7；(b) 12。 试问各得到了多少信息量试问各得到了多少信息量?366585.2)366(log236117.5361log2解: (a)一对骰子总点数为7的概率是所以，得到的信息量为 (b) 一对骰子总点数为12的概率是所以，得到的信息量为 比特比特2.4 经过充分洗牌后的一付扑克经过充分洗牌后的一付扑克(含含52张牌张牌)，试问：，试问： (a) 任何一种特定排列所给出的信息量是多少任何一种特定排

23、列所给出的信息量是多少? (b) 若从中抽取若从中抽取13张牌，所给出的点数都不相同时得到张牌，所给出的点数都不相同时得到多少信息量多少信息量?!52158.225!521log21 31 31 31 35 25 21 3 !44AC21.134log1313522C 解: (a)任一特定排列的概率为所以，给出的信息量为 (b) 从中任取13张牌,所给出的点数都不相同的概率为 所以，得到的信息量为 比特.比特2.5 设有一个非均匀骰子，若其任一面出现的概率与该面设有一个非均匀骰子，若其任一面出现的概率与该面上的点数成正比，试求各点出现时所给出的信息量，上的点数成正比，试求各点出现时所给出的信息

24、量，并求掷一次平均得到的信息量。并求掷一次平均得到的信息量。 解解:易证每次出现i点的概率为21i所以 比特比特比特比特比特比特比特398.221log21)(807.1)6(070.2)5(392.2)4(807.2)3(392.3)2(392.4)1(6,5,4,3,2,1,21log)(2612iiXHxIxIxIxIxIxIiiixIi2-6 园丁植树一行，若有园丁植树一行，若有3棵白杨、棵白杨、4棵白桦和棵白桦和5棵梧桐。设棵梧桐。设这这12棵树可随机地排列，且每一种排列都是等可能的。棵树可随机地排列，且每一种排列都是等可能的。若告诉你没有两棵梧桐树相邻时，你得到了多少关于若告诉你没

25、有两棵梧桐树相邻时，你得到了多少关于树的排列的信息树的排列的信息? 解解: 可能有的排列总数为可能有的排列总数为 27720!5!4!3!12没有两棵梧桐树相邻的排列数可如下图求得.Y X Y X Y X Y X Y X Y X Y X Y3758图中:X表示白杨或白桦，它有种排法，种排法.Y表示梧桐树可以栽种的位置，它有5837所以共有*=1960种排法保证没有两棵梧桐树相邻。 因此，若告诉你没有两棵梧桐树相邻时，得到关于树排因此，若告诉你没有两棵梧桐树相邻时，得到关于树排列的信息为列的信息为 =3.822 比特比特1960log27720log222.9 随机掷三颗骰子，以随机掷三颗骰子，

26、以X表示第一颗骰子抛掷的结果，表示第一颗骰子抛掷的结果，以以Y表示第一和第二颗骰子抛掷的点数之和，以表示第一和第二颗骰子抛掷的点数之和，以Z表示表示三颗骰子的点数之和。试求三颗骰子的点数之和。试求H(Z|Y)、H(X|Y)、H(Z|XY)，H(XZ|Y)和和H(Z|X)。6log2 解解:令令X=X1,Y=X1+X2,Z=X1+X2+X3, H(X1)=H(X2)=H(X3)=H(X)= H(X1) =2.585 比特比特=2.585 比特比特 H(Y)= H(X2+X3) 6log61)536log365436log364336log363236log36236log361( 2222222

27、= 3.2744 比特比特H(Z)= H(XH(Z)= H(X1 1+X+X2 2+X+X3 3) )27216log2162725216log2162521216log2162115216log2161510216log216106216log21663216log2163216log2161( 222222222= 3.5993 = 3.5993 比特比特所以所以H(Z/Y)= H(X3)= 2.585 比特比特H(Z/X) = H(X2+X3)= 3.2744 比特比特H(X/Y)=H(X)-H(Y)+H(Y/X) = 2.585-3.2744+2.585 =1.8955 比特比特H(Z

28、/XY)=H(Z/Y)= 2.585 比特比特H(XZ/Y)=H(X/Y)+H(Z/XY) =1.8955+2.585 =4.4805 比特比特2-12 计算习题计算习题2.9中的中的I (Y；Z)，I (X；Z)，I (XY；Z)， I (Y；Z|X)和和I (X；Z|Y)。 解解:I(Y;Z)=H(Z)-H(Z/Y) =H(Z)- H(X3)= 3.5993-2.585 =1.0143比特比特I(X;Z)=H(Z)-H(Z/X)=3.5993- 3.2744=0.3249比特比特I(XY ;Z)=H(Z)-H(Z/XY) =H(Z)-H(Z/Y) =1.0143比特比特I(Y;Z/X)=H

29、(Z/X)-H(Z/XY)= H(X2+X3)-H(X3) =3.2744-2.585 =0.6894比特比特I(X;Z/Y)=H(Z/Y)-H(Z/XY)=H(Z/Y)-H(Z/Y) =02-10 设有一个系统传送10个数字：0, 1, , 9。奇数在传送时以0.5的概率错成另外的奇数，而其它数字总能正确接收。试求收到一个数字平均得到的信息量。解:设系统输出10个数字X等概,接收数字为Y,显然显然 101)(101)()()(9190i jpi jpiQjwii，H(Y)=log10 比特奇奇奇奇偶18log81101452log211015)(log)()()(log)()(0)(log)

30、,()(log),()/(22,2222 xypxypxpxxpxxpxpxypyxpxypyxpXYHxyxiyxyx所以所以 I(X;Y)= 3219. 2110log2比特比特2.11 令令ul, u2, , u8为一等概消息集，各消息相应被为一等概消息集，各消息相应被编成下述二元码字编成下述二元码字: cl=0000， c2=0011，c3=0101，c4=0110 c5=1001，c6=1010，c7=1100，c8=1111通过转移概率为通过转移概率为p的的BSC传送。试求传送。试求 (a) 接收的第一个数字接收的第一个数字0与与u l之间的互信息量。之间的互信息量。 (b) 接收

31、的前二个数字接收的前二个数字00与与u l之间的互信息量。之间的互信息量。 (c) 接收的前三个数字接收的前三个数字000与与u l之间的互信息量。之间的互信息量。 (d) 接收的前四个数字接收的前四个数字0000与与u l之间的互信息量。之间的互信息量。解:（a）接收前一个数字为0的概率2180)0()()0(iiiupuqwbitsppwupuI)1 (log11log)0()0(log)0 ;(2212121（b）同理 4180)00()()00(iiiupuqwbitsppwupuI)1 (log22)1 (log)00()00(log)00;(24122121（c）同理 8180)0

32、00()()000(iiiupuqwbitsppwupuI)1 (log33)1 (log)000()000(log)000;(28132121（d）同理 )1 (6)1()0000()()0000(42268180ppppupuqwiiibitsppppppppppwupuI42264242268142121)1 (6)1 ()1 (8log)1 (6)1()1 (log)0000()0000(log)0000;(2.13 令X、Y、Z是概率空间，试证明下述关系式成立。 (a) H(YZ|X)H(Y|X)H(Z|X)，给出等号成立的条件。 (b) H(YZ|X)=H(Y|X)H(Z|XY)。

33、 (c) H(Z|XY)H(Z|X)，给出等号成立的条件。证明: (b) )/()/()/(1log)()/(1log)()/()/(1log)()/(1log)()/(XYZHXYHxyzpxyzpxypxyzpxyzpxypxyzpxyzpxyzpXYZHxyzxyzxyzxyz(c)/()/(1log)/()()/(1log)/()()/(XZHxzpxyzpxypxyzpxyzpxypXYZHxyzxyz 等号成立的条件为等号成立的条件为 , 对所有对所有 ,即在给定即在给定X条件下条件下Y与与Z相互相互独立。独立。)/()/(xzpxyzpZzYyXx,(a) )/()/()/()/

34、()/(XYZHXYZHXYHXZHXYH等号成立的条件同（等号成立的条件同（c c）2.14 对于任意概率事件集X、Y、Z，证明下述三角不等式成立。 H(X|Y)H(Y|Z)H(X|Z) H(X|Y)/H(XY)H(Y|Z)/H(YZ)H(X|Z)/H(XZ)证明: (a) )/()/()/()/()/()/(ZXHZXYHZYHYZXHZYHYXH(b) baabaaaabaaababababaa221121221121210,0)()/()()/()/()()/()/()/()/()()/()()/(0)(,0)/()/()/()()/()/()/()/()/()()/()/()/()/

35、()()/()/()/()/()()/()/()/()()/()/()()/()/()()/()()/()()/(XZHZXHZHZXHZXHZHZYHYXHZYHYXHYZHZYHXYHYXHZHZXHZYHYXHZHZYHYXHZYHYXHYXHYZHZYHYXHYZHYXHYHZYHYXHYXHYZHYHZYHYZHYXHYHYXHYZHYHZYHYXHYHYXHYZHZYHXYHYXH2.18 若三个随机变量有如下关系：xy=z，其中x和y独立。试证明： H(X)H (Z) H(Y)H(Z) H(XY)H(Z) I(X；Z)=H(Z)H(Y) I(XY；Z)=H(Z) I(X；YZ)=H(X) I(Y；Z|X)=H(Y) I(X；Y|Z)=H(X|Z)=H(Y|Z)证明: (a)()(0)