信息论第二章课件及习题答案.ppt

1、2020/8/7,1,第二章：信息量和熵,2.1 离散型随机变量的非平均信息量（事件的信息量） 2.2 离散型随机变量的平均自信息量（熵） 2.4 离散型随机变量的平均互信息量 2.5 连续型随机变量的平均互信息量和微分熵 2.6 凸函数与(离散型随机变量的)平均互信息量的凸性,2020/8/7,2,2.1 离散型随机变量的非平均信息量（事件的信息量）,（本章将给出各种信息量的定义和它们的性质。） 定义2.1.1(非平均互信息量) 给定一个二维离散型随机变量 (X, Y), (xk, yj), rkj, k=1K; j=1J （因此就给定了两个离散型随机变量 X, xk, qk, k=1K和Y

2、, yj, wj, j=1J）。 事件xkX与事件yjY的互信息量定义为I(xk; yj),2020/8/7,3,2.1 离散型随机变量的非平均信息量（事件的信息量）,（本章将给出各种信息量的定义和它们的性质。） 定义2.1.1(非平均互信息量) 给定一个二维离散型随机变量 (X, Y), (xk, yj), rkj, k=1K; j=1J （因此就给定了两个离散型随机变量 X, xk, qk, k=1K和Y, yj, wj, j=1J）。 事件xkX与事件yjY的互信息量定义为I(xk; yj),2020/8/7,4,2.1 离散型随机变量的非平均信息量（事件的信息量）,（本章将给出各种信息

3、量的定义和它们的性质。） 定义2.1.1(非平均互信息量) 给定一个二维离散型随机变量 (X, Y), (xk, yj), rkj, k=1K; j=1J （因此就给定了两个离散型随机变量 X, xk, qk, k=1K和Y, yj, wj, j=1J）。 事件xkX与事件yjY的互信息量定义为I(xk; yj),2020/8/7,5,2.1 离散型随机变量的非平均信息量（事件的信息量）,（本章将给出各种信息量的定义和它们的性质。） 定义2.1.1(非平均互信息量) 给定一个二维离散型随机变量 (X, Y), (xk, yj), rkj, k=1K; j=1J （因此就给定了两个离散型随机变量

4、 X, xk, qk, k=1K和Y, yj, wj, j=1J）。 事件xkX与事件yjY的互信息量定义为I(xk; yj),2020/8/7,6,2.1 离散型随机变量的非平均信息量（事件的信息量）,其中底数a是大于1的常数。 常用a=2或a=e 。 当a=2时互信息量的单位为“比特”。bit,2020/8/7,7,2.1 离散型随机变量的非平均信息量（事件的信息量）,互信息量的性质：,2020/8/7,8,2.1 离散型随机变量的非平均信息量（事件的信息量）,互信息量的性质：,（1）I(xk; yj)=loga(rkj/(qkwj)。因此有对称性：I(xk; yj)=I(yj; xk)。

5、,2020/8/7,9,2.1 离散型随机变量的非平均信息量（事件的信息量）,互信息量的性质：,（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）。,2020/8/7,10,2.1 离散型随机变量的非平均信息量（事件的信息量）,互信息量的性质：,（1）I(xk; yj)=loga(rkj/(

6、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）。,（3）当rkjqkwj时I(xk; yj)0，当rkj wj时，I(xk; yj)0；当(rkj/qk) wj时，I(xk; yj)0。 换句话说， 当“X=xk”与“Y= yj”这两个事件相互肯定时，互信息量为正值； 当“X=xk”与“Y= yj”这两个事件相互否定时，互信息量为负

7、值。）,2020/8/7,11,2.1 离散型随机变量的非平均信息量（事件的信息量）,定义2.1.3(非平均自信息量) 给定一个离散型随机变量X, xk, qk, k=1K。事件xkX的自信息量定义为 h(xk)=loga(1/qk)， 其中底数a是大于1的常数。 自信息量的性质： （1）h(xk)0。 （2）qk越小，h(xk)越大。 （3）I(xk; yj)minh(xk)，h(yj)，即互信息量不超过各自的自信息量。 证明 注意到总有rkjminqk, j。（为什么？什么情况下相等？）。因此根据定义， I(xk; yj)h(xk)，I(xk; yj)h(yj)。得证。,2020/8/7,

8、12,2.1 离散型随机变量的非平均信息量（事件的信息量）,定义2.1.4(条件的非平均自信息量) 给定一个二维离散型随机变量(X, Y), (xk, yj), rkj, k=1K; j=1J。在事件yj发生的条件下事件xk的条件自信息量定义为 h(xk|yj)=loga(1/P(X=xk|Y=yj)=loga(wj/rkj)。 （条件的非平均自信息量实际上是非平均自信息量的简单推广，只不过将概率换成了条件概率）。 条件的非平均自信息量的特殊性质： h(xk|yj)=h(xk)-I(xk; yj) 。,2020/8/7,13,2.1 离散型随机变量的非平均信息量（事件的信息量）,定义2.1.5

9、(联合的非平均自信息量) 给定一个二维离散型随机变量(X, Y), (xk, yj), rkj, k=1K; j=1J。事件(xk, yj)(X, Y)的自信息量定义为 h(xk, yj)=loga(1/rkj)。 （联合的非平均自信息量实际上是非平均自信息量的简单推广。即可以将(X, Y)直接看成是一维的随机变量）。 联合的非平均自信息量的特殊性质： h(xk, yj)=h(yj)+h(xk|yj)=h(xk)+h(yj|xk)。 h(xk, yj)=h(xk)+h(yj)-I(xk; yj)。,2020/8/7,14,2.1 离散型随机变量的非平均信息量（事件的信息量）,小结 非平均互信息

10、量I(xk; yj)。 非平均自信息量h(xk)，h(yj)。 条件的非平均自信息量h(xk|yj)， h(yj|xk)。 联合的非平均自信息量h(xk, yj)。 相互关系： I(xk; yj)minh(xk)，h(yj)。 h(xk|yj)=h(xk)-I(xk; yj) 。 h(xk, yj)=h(yj)+h(xk|yj)=h(xk)+h(yj|xk)。 h(xk, yj)=h(xk)+h(yj)-I(xk; yj)。,2020/8/7,15,2.2 离散型随机变量的平均自信息量（熵）,定义2.2.1(平均自信息量熵) 离散型随机变量X, xk, qk, k=1K的平均自信息量（又称为熵

11、）定义为如下的H(X)，其中底数a是大于1的常数。,2020/8/7,16,2.2 离散型随机变量的平均自信息量（熵）,注意： （1）事件xk的自信息量值为h(xk)=loga(1/qk)，因此H(X)是随机变量X的各事件自信息量值的“数学期望”。 （2）定义H(X)时，允许某个qk=0。（此时将qkloga(1/qk) 通盘考虑）此时补充定义qkloga(1/qk)=0。这个定义是合理的，因为,2020/8/7,17,2.2 离散型随机变量的平均自信息量（熵）,例2.2.1 离散型随机变量X有两个事件x1和x2， P(X=x1)=p，P(X=x2)=1-p。 则X的平均自信息量（熵）为 H(

12、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） 当00。p越靠近1/2， H(X)越大。 （X是真正的随机变量时，总有正的熵。随机性越大，熵越大） 当p=1/2时，H(X)达到最大。（随机变量X的随机性最大时，熵最大。特别如果底数a=2，则H(X)=1比特）,2020/8/7,18,图2.2.1,H(X) 1.0 0.5 0 0.5 1 P,2020/8/7,19,2.2 离散型随机变量的平均自信息量（熵）,定义2.2.2

13、(条件熵) 给定一个二维离散型随机变量 (X, Y), (xk, yj), rkj, k=1K; j=1J。 称如下定义的H(X|Y)为X相对于Y的条件熵。,2020/8/7,20,2.2 离散型随机变量的平均自信息量（熵）,定义2.2.2(条件熵) 给定一个二维离散型随机变量 (X, Y), (xk, yj), rkj, k=1K; j=1J。 称如下定义的H(X|Y)为X相对于Y的条件熵。,H(X|Y),2020/8/7,21,2.2 离散型随机变量的平均自信息量（熵）,定义2.2.2(条件熵) 给定一个二维离散型随机变量 (X, Y), (xk, yj), rkj, k=1K; j=1J

14、。 称如下定义的H(X|Y)为X相对于Y的条件熵。,H(X|Y),2020/8/7,22,2.2 离散型随机变量的平均自信息量（熵）,定义2.2.2(条件熵) 给定一个二维离散型随机变量 (X, Y), (xk, yj), rkj, k=1K; j=1J。 称如下定义的H(X|Y)为X相对于Y的条件熵。,H(X|Y),2020/8/7,23,2.2 离散型随机变量的平均自信息量（熵）,定义2.2.2(条件熵) 给定一个二维离散型随机变量 (X, Y), (xk, yj), rkj, k=1K; j=1J。 称如下定义的H(X|Y)为X相对于Y的条件熵。,H(X|Y),2020/8/7,24,2

15、.2 离散型随机变量的平均自信息量（熵）,定义2.2.2(条件熵) 给定一个二维离散型随机变量 (X, Y), (xk, yj), rkj, k=1K; j=1J。 称如下定义的H(X|Y)为X相对于Y的条件熵。,H(X|Y),2020/8/7,25,2.2 离散型随机变量的平均自信息量（熵）,定义2.2.2(条件熵) 给定一个二维离散型随机变量 (X, Y), (xk, yj), rkj, k=1K; j=1J。 称如下定义的H(X|Y)为X相对于Y的条件熵。,H(X|Y),2020/8/7,26,2.2 离散型随机变量的平均自信息量（熵）,定义2.2.3(联合熵) 二维离散型随机变量 (X

16、, Y), (xk, yj), rkj, k=1K; j=1J 的联合熵定义为,2020/8/7,27,2.2 离散型随机变量的平均自信息量（熵）,熵、条件熵、联合熵之间的关系： （1）H(XY)=H(X)+H(Y|X)=H(Y)+H(X|Y)。（由定义容易证明） （2）当X与Y相互独立时，H(Y|X)=H(Y)，因此此时H(XY)=H(X)+H(Y)。 证明 此时,2020/8/7,28,2.2 离散型随机变量的平均自信息量（熵）,熵的性质 对于随机变量X, xk, qk, k=1K的熵H(X)=kqkloga(1/qk)，有以下的性质。 1、 H(X)与事件xk, k=1K的具体形式无关，

17、仅仅依赖于概率向量qk, k=1K。 而且H(X)与概率向量qk, k=1K的分量排列顺序无关。 2、H(X)0。完全同理， H(X|Y)0；H(Y|X)0；H(XY)0。 3、确定性：当概率向量qk, k=1K的一个分量为1时（此时其它分量均为0），H(X)=0。（这就是说，当随机变量X实际上是个常量时，不含有任何信息量）。,2020/8/7,29,2.2 离散型随机变量的平均自信息量（熵）,4、可忽略性：当随机变量X的某个事件的概率很小时，该事件对熵的贡献可以忽略不计。（虽然小概率事件的自信息量很大。这是因为当qk0时，qkloga(1/qk)0）。 5、可加性： H(XY)=H(X)+H

18、(Y|X)=H(Y)+H(X|Y)。 因此，H(XY)H(X)； H(XY)H(Y)。 （性质5有一个隐含的结论：设X的概率向量为 q1, q2, , qK， Y的概率向量为 q1, q2, , qK-2, qK-1+qK， 其中qK-1qK0，则H(X) H(Y)。 ）,2020/8/7,30,2.2 离散型随机变量的平均自信息量（熵）,6、极值性：H(X)logaK。当q1=q2=qK=1/K时，才有 H(X)=logaK。 （以下是极值性的证明过程） 引理1 对任何x0总有lnxx-1。 证明 令f(x)=lnx-(x-1)，则f(x)=1/x-1。因此 当00；当x1时f(x)1时，f

19、(x)的值严格单调减。 注意到f(1)=0。所以对任何x0总有f(x)f(1)=0。得证。,2020/8/7,31,2.2 离散型随机变量的平均自信息量（熵）,引理2 设有两个K维概率向量（什么叫概率向量？每个分量都是非负的，且各分量之和等于1） qk, k=1K和pk, k=1K 。 则总满足,2020/8/7,32,2.2 离散型随机变量的平均自信息量（熵）,证明 注意到引理1，,2020/8/7,33,2.2 离散型随机变量的平均自信息量（熵）,引理2得证。（注意：此证明过程省略了若干细节，比如当概率向量的某个分量为0时，情况比较复杂） 极值性的证明 qk, k=1K是一个K维概率向量。

20、令pk=1/K，k=1K。则pk, k=1K也是一个K维概率向量。由引理2， H(X)=kqkloga(1/qk)kqkloga(1/(1/K)=logaK。 得证。,2020/8/7,34,2.4 离散型随机变量的平均互信息量,定义2.4.1(平均互信息量) 给定一个二维离散型随机变量(X, Y), (xk, yj), rkj, k=1K; j=1J（因此就给定了两个离散型随机变量X, xk, qk, k=1K和Y, yj, wj, j=1J）。X与Y的平均互信息量定义为如下的I(X; Y)：,2020/8/7,35,2.4 离散型随机变量的平均互信息量,定义2.4.1等价形式(一),202

21、0/8/7,36,2.4 离散型随机变量的平均互信息量,定义2.4.1等价形式(二),2020/8/7,37,2.4 离散型随机变量的平均互信息量,此处： I(xk; yj)表示事件“X=xk”与事件“Y=yj”的“非平均互信息量” 。 I(xk; Y)表示事件“X=xk”与随机变量Y之间的“半平均互信息量”。 I(X; yj)表示事件“Y=yj”与随机变量X之间的“半平均互信息量”。,2020/8/7,38,2.4 离散型随机变量的平均互信息量,定义2.4.1等价形式(三),2020/8/7,39,注意：事件对(xk, yj)的“非平均互信息量”值为I(xk; yj)。此外，可以定义“半平均

22、互信息量”I(xk; Y)和I(X; yj)。,I(xk; Y)表示事件“X=xk”与随机变量Y之间的半平均互信息量； I(X; yj)表示事件“Y=yj”与随机变量X之间的半平均互信息量。,2020/8/7,40,2.4 离散型随机变量的平均互信息量,平均互信息量的性质 1、I(X; Y)0。（虽然每个“非平均互信息量” I(xk; yj)未必非负，但平均互信息量I(X; Y)非负） 证明,2020/8/7,41,2.4 离散型随机变量的平均互信息量,rkj, k=1K; j=1J是一个概率向量： qkwj, k=1K; j=1J是另一个概率向量： 故由引理2知，,2020/8/7,42,2

23、.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)。 证明,2020/8/7,43,2.4 离散型随机变量的平均互信息量,2020/8/7,44,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=1K; j=1J。 因此此时loga(rkj/(qkwj)=0， k=1K;

24、j=1J。 因此I(X; Y)=0。再由性质3，性质3得证。,2020/8/7,45,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)。 （证略）,2020/8/7,46,2.4 离散型随机变量的平

25、均互信息量,一般印象 （平均互信息量I(X; Y)的各种性质与我们对“平均互信息量”这个名词的直观理解非常吻合）。 一般情形：总有0I(X; Y)minH(X), H(Y)。 一种极端情形：若X与Y相互独立，则I(X; Y)=0。 另一种极端情形：若X、Y中有一个完全是另一个的确定的函数，则I(X; Y)=minH(X), H(Y)。,2020/8/7,47,2.4 离散型随机变量的平均互信息量,定理2.4.1(信息处理定理) 对于以下给定的系统串联有： I(X; Y)I(X; Z)。 信息处理定理的含义：串联的系统越多，两端的平均互信息量越小。 信息处理定理的证明思想：注意到X、Z、Y构成了

26、马尔可夫链。简单地说，在已知Z的条件下， X与Y条件独立。根据这种马尔可夫链结构，可以证明I(X; Y)I(X; Z)。 （证略）,2020/8/7,48,2.1 2.4 诸概念直观理解,两个事件的非平均互信息量：互相肯定的程度。 一个事件的非平均自信息量：令人震惊的程度。 一个随机变量的平均自信息量（熵）：不可预测的程度。 一个随机变量X相对于另一个随机变量Y的条件熵：当Y的值确定时， X剩余的不可预测的程度。 二维随机变量(XY)的联合熵：联合不可预测的程度。 两个随机变量X与Y的平均互信息量：互相依赖的程度。（当Y的值确定时， X的可预测的程度；当Y的值确定时， 所能够给出的X的信息量

27、） （当X的值确定时，Y的可预测的程度；当X的值确定时， 所能够给出的Y的信息量 ） 事件X=x与随机变量Y的半平均互信息量：当X=x时， 所能够给出的Y 的信息量 。,2020/8/7,49,2.2 和2.4 中的若干公式,2020/8/7,50,2.5 连续型随机变量的平均互信息量和微分熵,定义2.5.1 给定二维连续型随机变量(X, Y), f(X,Y)(x, y)（因此就给定了两个连续型随机变量X, fX(x)和Y, fY(y)）。事件xX与事件yY的互信息量定义为 定义2.5.2 给定二维连续型随机变量(X, Y), f(X,Y)(x, y)（因此就给定了两个连续型随机变量X, fX

28、(x)和Y, fY(y)）。 X与Y的平均互信息量定义为,2020/8/7,51,2.5 连续型随机变量的平均互信息量和微分熵,平均互信息量的性质 1、I(X; Y)0。 2、对称性：I(X; Y)=I(Y; X)。 3、信息处理定理：对于如下的系统串联有I(X; Y)I(X; Z)。,2020/8/7,52,2.5 连续型随机变量的平均互信息量和微分熵,（连续型随机变量为什么不能类似地定义平均自信息量熵？这是因为，连续型随机变量的事件有无穷多个，每个事件发生的概率无穷小。如果类似地定义熵，则熵是无穷大。因此只能定义所谓“微分熵”，而“微分熵”的直观合理性大打折扣。比如“微分熵” 可以是负的）

29、 微分熵的定义 给定连续型随机变量X, fX(x)。 X的微分熵(又称为相对熵)定义为,2020/8/7,53,2.5 连续型随机变量的平均互信息量和微分熵,联合的微分熵的定义 给定二维连续型随机变量(X, Y), f(X,Y)(x, y) 。 (X, Y)的联合的微分熵定义为,2020/8/7,54,2.5 连续型随机变量的平均互信息量和微分熵,例2.5.1 设(XY)是连续型的二维随机变量，其联合分布密度函数pXY(xy)为二维高斯概率密度函数（二元正态密度函数）：,2020/8/7,55,2.5 连续型随机变量的平均互信息量和微分熵,2020/8/7,56,2.5 连续型随机变量的平均互

30、信息量和微分熵,例2.5.2 设XU(a, b)，求X的微分熵（相对熵） （我们将发现， X的相对熵未必非负）。,2020/8/7,57,2.5 连续型随机变量的平均互信息量和微分熵,例2.5.3 设XN(m, 2)，求X的微分熵（相对熵） （我们将发现， X的相对熵未必非负）。,2020/8/7,58,2.5 连续型随机变量的平均互信息量和微分熵,2020/8/7,59,2.5 连续型随机变量的平均互信息量和微分熵,微分熵的极大化 （已知：当离散型随机变量X的事件有K个时，H(X)logaK；只有当X服从等概分布时才有H(X)=logaK） 定理2.5.1 若连续型随机变量X的取值范围在区间

31、(-M, M)之内（即当x不在区间(-M, M) 时， fX(x)=0），则Hc(X)loga 2M；只有当X服从U (-M, M)分布时才有Hc(X)=loga 2M。 定理2.5.2 若连续型随机变量X的方差等于2 ，则Hc(X)(1/2)loga (2e2)；只有当X服从N(m, 2)分布时才有Hc(X)=(1/2)loga (2e2)。 （定理2.5.1和定理2.5.2的证明略）,2020/8/7,60,2.6 凸函数与(离散型随机变量的)平均互信息量的凸性,记离散型随机变量X的事件为1，2，K。 记X的概率分布为P(X=k)=qk，k=1K。 记离散型随机变量Y的事件为1，2，J。

32、记条件概率P(Y=j|X=k)=p(j|k)。则 rkj=P(X, Y)=(k,j)=qkp(j|k)，（概率论中的乘法公式） wj=P(Y=j)=k qkp(j|k)，（概率论中的全概率公式）,2020/8/7,61,2.6 凸函数与(离散型随机变量的)平均互信息量的凸性,设条件概率p(j|k)，k=1K，j=1J被确定。此时I(X, Y)是概率向量q=(q1, q2, , qK)的函数。我们希望找到这样的概率向量，使得对应的I(X, Y)达到最大。这就是说，记 我们希望找到这样的K维概率向量a=(a1, a2, , aK)，使得,2020/8/7,62,2.6 凸函数与(离散型随机变量的)

33、平均互信息量的凸性,（本节的核心内容是定理2.6.2，但它有太长的推导。） 简述定理2.6.2的含义 K维概率向量a=(a1, a2, , aK)使得 当且仅当：以a为X的概率向量的时候，I(X=k; Y)对所有ak0的k都取一个相同的值C； I(X=k; Y)对所有满足ak=0的k都取值不超过上述的相同值C 。其中,2020/8/7,63,2.6 凸函数与(离散型随机变量的)平均互信息量的凸性,I(X=k; Y)表示什么？表示事件X=k与随机变量Y之间的“半平均互信息量”。,2020/8/7,64,2.6 凸函数与(离散型随机变量的)平均互信息量的凸性,例 设X的事件有0、1； Y的事件有0

34、、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)达到最大。因为此时,2020/8/7,65,2.6 凸函数与(离散型随机变量的)平均互信息量的凸性,2020/8/7,66,习题课,2.3 掷一对无偏的骰子，若告诉你得到的总的点数为：(a) 7；(b) 12。试问各得到了多少信息量? 2.3的解答 这是求事件的自信息量。记随机变量X=“总的点数”，则 所以，事件“X=7”的自信息量为log2(36/7)；事件“X=12”的自信息量为log2(36)。,2020

35、/8/7,67,习题课,2.4 经过充分洗牌后的一付扑克(含52张牌)，试问： (a) 任何一种特定排列所给出的信息量是多少? (b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量? 2.4的解答 这是求事件的自信息量。 (a) 任一特定排列的概率都是(1/52!)，所以自信息量为log2(52!)； (b) 从52张牌中抽取13张牌，共有 种抽取方法。 而使得所给出的点数都不相同的抽取方法有 种。 所以事件“点数都不相同”的概率为 ，自信息量为 。,2020/8/7,68,习题课,2.6 园丁植树一行，若有3棵白杨、4棵白桦和5棵梧桐。设这12棵树可随机地排列，且每一种排列都是等

36、可能的。若告诉你没有两棵梧桐树相邻时，你得到了多少关于树的排列的信息? 2.6的解答 共有12！种不同的排列。满足“没有两棵梧桐树相邻”的排列个数为 81+72+63+54+45+36+27+18=120（为什么？） 记X=“树的排列情况”， Y=“梧桐树有无相邻位置”。则本题要求半平均互信息量,2020/8/7,69,习题课,X有12！个不同的事件x，每个事件x的概率为1/(12！)。 Y有2个不同的事件，“Y=无”的概率为120/(12！)，“Y=有”的概率为(12！-120)/(12！)。 以下要计算：在“Y=无”的条件下， X= x（ x为某个特定排列）的条件概率P(X=x|Y=无)。

37、 若在x这个特定排列中，梧桐树有相邻位置，则P(X=x|Y=无)=0； 若在x这个特定排列中，梧桐树无相邻位置，则,2020/8/7,70,习题课,2020/8/7,71,习题课,2.7 某校入学考试中有1/4考生被录取，3/4考生未被录取。被录取的考生中有50%来自本市，而落榜考生中有10来自本市。所有本市的考生都学过英语，而外地落榜考生中以及被录取的外地考生中都有40%学过英语。 (a) 当己知考生来自本市时，给出多少关于考生是否被录取的信息? (b) 当已知考生学过英语时，给出多少有关考生是否被录取的信息? (c) 以x表示是否被录取，y表示是否为本市学生，z表示是否学过英语，x、y和z

38、取值为0或1。试求H(x)，H(y|x)，H(z|y)。,2020/8/7,72,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=01

39、1)=(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%。,2020/8/7,73,各个边际分布,(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、)=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%。,2020/8/7,74,习题课,2020/8/7,75,习题课,2020/8/7,76,习题课,2.8 在A、B两组人中进行民意测验，组A中的人有50%讲真话(T)，30%讲假话(F)，20%拒绝回答(R)。而组B中有30%讲真话，50%讲假话和20%拒绝回答。设选A组进行测

41、验的概率为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)。,2020/8/7,77,习题课,计算X的概率分布： P(X=A)=p；P(X=B)=1-p。 计算Y的概率分布： P(Y=T)=p50%+(1-p)30%=30%+ p20%； P(Y=F)=p30%+(1-p)50%=50%- p20%； P(Y=R)=p20%+(1-p)20%=20%。 计算联合概率分布： P(XY=AT)

42、=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。,2020/8/7,78,习题课,2020/8/7,79,习题课,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)的联合

43、概率分布和Y的概率分布； 求H(Z|X)，必须先求(XZ)的联合概率分布和X的概率分布； 求H(Z|XY)，必须先求(XYZ)的联合概率分布和(XY)的联合概率分布； 求H(XZ|Y)，必须先求(XYZ)的联合概率分布和Y的概率分布。,2020/8/7,80,(XYZ)的联合概率分布为：P(XYZ)=(x,y,z)=1/216；x=16，y=x+1x+6，z=y+1y+6。(XY)的联合概率分布为：P(XY)=(x,y)=1/36；x=16，y=x+1x+6。,2020/8/7,81,习题课,(YZ)的联合概率分布为： P(YZ)=(2,3)=1/63，P(YZ)=(2,4)=1/63， ，

44、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)

45、=2/63， P(YZ)=(12,13)=1/63，P(YZ)=(12,14)=1/63， ， P(YZ)=(12,18)=1/63。,2020/8/7,82,2020/8/7,83,习题课,(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，

46、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。,2020/8/7,84,习题课,2020/8/7,85,习题课,X的概率分布： P(X=x)=1/6，其中x=16。 Y的概率分布： 当y=27时，P(Y=y)=(y-1)/36； 当y=812时，P(Y=y)=(13-y)/36 。

47、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。,2020/8/7,86,习题课,2020/8/7,87,将以上的概率分布代入以下的计算公式：,2020/8/7,88,

48、习题课,2020/8/7,89,2020/8/7,90,习题课,2.10 设有一个系统传送10个数字：0, 1, , 9。奇数在传送时以0.5的概率错成另外的奇数（？！），而偶数总能正确接收。试求收到一个数字平均得到的信息量。 2.10的解答 问题一：这是什么信息量？ “收到一个数字平均得到的信息量”似乎指的是“收到的数字”这个随机变量的平均自信息量（熵）：H(收到的数字)。 “发送一个数字x时，所给出的收到数字的平均信息量”应该指的是半平均互信息量： I(发送的数字=x；收到的数字)。 “发送数字时，所给出的收到数字的平均信息量”应该指的是平均互信息量： I(发送的数字；收到的数字)。,20

49、20/8/7,91,习题课,问题二：既然是求 “收到的数字”这个随机变量的平均自信息量（熵），那么“收到的数字”的概率分布如何计算？ 假设“发送的数字”服从等概分布： P(发送的数字=j)=1/10， j=09 则 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),2020/8/7,92,习题课,这就是说，当假设“发送的数

50、字”服从等概分布时， “收到的数字”服从等概分布。 H(收到的数字)=log10。 I(发送的数字；收到的数字),2020/8/7,93,习题课,2.11 令ul, u2, , u8为一等概消息集，各消息相应被编成下述二元码字: ul=0000，u2=0011，u3=0101，u4=0110 u5=1001，u6=1010，u7=1100，u8=1111 码字通过转移概率为p的BSC传送。试求 (a) 接收的第一个数字0与ul之间的互信息量。 (b) 接收的前二个数字00与ul之间的互信息量。 (c) 接收的前三个数字000与ul之间酌互信息量。 (d) 接收的前四个数字0000与ul之间的互

51、信息量。 2.11的解答 显然是求事件之间的（非平均）互信息量。 首先什么是“转移概率为p的BSC”？解释如下（详见第四章）。,2020/8/7,94,习题课,“转移概率为p的BSC”是这样一种输入/输出机制： （1）在一个固定时刻， P(输出0|输入0)=P(输出1|输入1)= 1-p P(输出1|输入0)=P(输出0|输入1)= p （2）在不同时刻的输入/输出操作是相互独立的： P(t1t2tn时刻输出v1v2vn |t1t2tn时刻输入u1u2un) =P(t1时刻输出v1|t1时刻输入u1) P(t2时刻输出v2|t2时刻输入u2) P(tn时刻输出vn|tn时刻输入un),2020

52、/8/7,95,习题课,(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。,2020/8/7,96,习题课,P(发送ul)=1/8。 P(发送ul，且接收的第一个数字为0) =P(发送ul)P(接收的第一个数字为0|发送ul) =P(发送ul)P(接收的第一

53、个数字为0|发送的第一个数字为0) =(1/8)(1-p)。 因此，I(发送ul；接收的第一个数字为0),2020/8/7,97,(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(

54、1-p)+P(发送u7或u8)p2 =1/4,2020/8/7,98,习题课,P(发送ul，且接收的前两个数字为00) =P(发送ul)P(接收的前两个数字为00 |发送ul) =P(发送ul)P(接收的前两个数字为00 |发送的前两个数字为00) =(1/8)(1-p)2。 因此，I(发送ul；接收的前两个数字为00),2020/8/7,99,(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/8,2020/8/7,100,习