马尔可夫信源极限熵

1、第 2 章 信源与信息熵香农信息论的基本点用随机变量或随机矢量来表示信源，运用概率论和随机过程的理论来研究信息。信源的分类按照信源发出的消息在时间上和幅度上的分布情况可将信源分成离散信源和连续信源两大类 .单符号信源概率空间描述自信息量单位： bit （一个比特表示一个等概率的二进制符号信息量）自信息量与 不确定度的关系不确定度 :随机事件的不确定度在数量上等于它的自信息量，两者的单位相同，但含义却不相同一个出现概率接近于 1 的随机事件，发生的可能性很大，所以它包含的不确定度就很小。一个出现概率很小的随机事件，很难猜测在某个时刻它 能否发生，所以它包含的不确定度就很大。若是确定性事件，出现概

2、率为1，则它包含的不确定度为0。说明:具有某种概率分布的随机事件不管发生与否，都存在不确定度，不确定度表征了该事件的特性，而自信息量是在该事件发生后给予观察者的信息量。联合自信息量为：条件自信息量为：信源熵=【信源的平均不确定度】=【平均自信息量】条件熵：H(X /Y)p(xi, yj)I (xi | yj)p(xi, yj )log p(xi| yj )i, ji联合熵H(X,Y)p(xi, yj)I (xi, yj )p(xi , yj )log p(xi, yj )i, ji联合熵、条件熵与信源熵的关系H(XY)=H(X)+H(Y/X) ，H(XY)=H(Y)+H(X/Y)互信息定义：后

3、验概率与先验概率比值的对数I (xi; yj ) logp( x / y)ijp(xi )平均互信息量I (X ;Y)p(x, y) logp ( x / y)p ( x)x, y疑义度条件熵 H(X/Y) ：信道上的干扰和噪声所造成的对信源符号 x 的平均不确定度噪声熵或散布度条件熵 H(Y/X) ：可看作唯一地确定信道噪声所需要的平均信息量互信息量与熵的关系H(XY)=H(X)+H(Y/X)=H(Y)+H(X/Y)H(X) H(X/Y) ， H(Y) H(Y/X)I(X;Y)=H(X)-H(X/Y)=H(Y)-H(Y/X)=H(X)+H(Y)-H(XY)H(XY)H(X)+H(Y)信息不增

4、性：数据处理过程中只会失掉一些信息，绝不会创造出新的信息最大熵定理(1) 限峰功率最大熵定理：对于定义域为有限的随机矢量X，当它是均匀分布时，具有最大熵。(2) 限平均功率最大熵定理：若连续变量 X 的方差一定，当它是正态分布时具有最大熵。信源的序列熵：（请注意：序列X 的多种写法！）H(XL) H(X1X2XL) H(X1 ) H(X2/X 1) H(XL/X 1X2XL-1 )平均每个符号的熵为HL(X)1 H(X L1 X 2X L)若当信源退化为无记忆时，有H(X)H(X 1X 2X L )H(X 1)H X 2H X L若进一步又满足平稳性时，则有H(X)LH(X 1 )推广结论马尔

5、可夫信源表述有记忆信源要比表述无记忆信源困难得多。实际上信源发出的符号往往只与前若干个符号的依赖关系强，而与更前面的符号依赖关系弱。为此，可以限制随机序列的记忆长度。当记忆长度为 m+1时，称这种有记忆信源为 m阶马尔可夫信源。也就是信源每次发出的符号只与前 m个符号有关，与更前面的符号无关。稳态分布概率定义：若齐次马尔可夫链对一切 i,j 存在不依赖于 i 的极限，则称其具有遍历性， Wj 称为稳态分布概率马尔可夫信源极限熵：H(X)p(si)H ( X / si)WiH ( X / si)ii其中， H X/s ip(xj /si)logp(xj /si)j冗余度：它表示给定信源在实际发出

6、消息时所包含的多余信息.( 也称为多余度或剩余度 ).定义信息效率:H(X)H m ( X )定义冗余度 :1 1H(X) H m ( X )其中： H (X) 为信源实际熵， Hm(X)信源最大熵。习题 2 信源与信息熵习题2-12.1 一个马尔可夫信源有3 个符号 u1, u2 ,u3 ，转移概率为： p u1 | u11/ 2 ，p u2 | u11/2，p u3| u10 ， p u1 | u21/ 3 ， p u2 | u2 0 ， p u3 | u2 2/3， p u1 | u31/3 ，p u| u2/3 ， p u | u30 ，画出状态图并求出各符号稳态概率。233解：状态图

7、如下状态转移矩阵为：设状态 u1，u2，u3 稳定后的概率分别为W1，W2、W3111W1W 2W3 W1233WP W12W 2W1W 3由W 3 1，得： 23W1 W22W 3W 23W1 W2 W3110W1259计算可得： W 2256W 325习题 2-22.2 由符号集 0 ，1 组成的二阶马尔可夫链，其转移概率为：p(0 | 00) =0.8 ， p(0 |11) =0.2 ，p(1| 00) =0.2 ， p(1|11) =0.8 ， p(0 | 01) =0.5 ， p(0 |10) =0.5 ， p(1| 01) =0.5 ， p(1|10) =0.5 。画出状态图，并计

8、算各状态的稳态概率。解： 因是二阶马尔可夫信源 , 此信源任何时刻发出的符号只与前两个符号有关 , 而与更前面的符号无关。如原来状态为 00, 则此时刻只可能发出符号 0 或 1, 下一时刻只能转移到 00,01 状态 , 由于处于 00 状态发符号 0 的概率为 0.8, 处在 00 状态时发符号 1 的概率为 0.2, 转移到 01 状态 ,00 000 0000 00101p(0 | 00)p(00 | 00)0.8p(0 | 01)p(10 | 01)0.5p(0 |11)p(10 |11)0.2p(0 |10)p(00 |10)0.5p(1| 00)p(01| 00)0.2p(1|

9、01)p(11| 01)0.5p(1|11)p(11|11)0.8p(1|10)p(01|10)0.5于是可以列出转移概率矩阵：0.80.200000.50.5p0.50.500000.20.8状态图为：设各状态 00， 01，10，11 的稳态分布概率为W1,W2,W3,W4有0.8W10.5W 3W1WPW0.2W10.5W 3W 2由4i得0.5W 20.2W 4W 3W10.5W 20.8W 4W 4i1W1 W2W 3W 4 15W1141W 2计算得到71W 375W 414习题 2-3同时掷出两个正常的骰子，也就是各面呈现的概率都为1/6 ，求：(1) “3 和 5 同时出现”这

10、事件的自信息；(2) “两个 1 同时出现”这事件的自信息；(3) 两个点数的各种组合（无序）对的熵和平均信息量；(4) 两个点数之和（即 2, 3, , 12 构成的子集）的熵；(5) 两个点数中至少有一个是 1 的自信息量。解： (1)p ( x i)11111666618I ( xi)logp ( xi )14 .170 bitlog18(2)p ( xi)1116636I ( xi )log p ( xi )log 15.170bit36(3) 两个点数的排列如下：1112131415162122232425263132333435364142434445465152535455566

11、16263646566共有 21 种组合：其中 11， 22， 33， 44， 55， 66 的概率是 1116636其他 15 个组合的概率是 2 1116618H (X)p( xi ) log p(xi )61 log1151 log 14.337 bit / symboli363618 18(4)参考上面的两个点数的排列，可以得出两个点数求和的概率分布如下：X23456789101112P(X )111151511113618129366369121836H (X)p( xi ) log p( xi)(5)i21121log12111125511log1812log2loglog366l

12、og36361812993663.274 bit / symbolp( xi )1111116636I ( xi )log p(xi )log11bit1.71036习题 2-52.5居住某地区的女孩子有25%是大学生，在女大学生中有75%是身高 160 厘米以上的，而女孩子中身高160 厘米以上的占总数的一半。假如我们得知“身高160 厘米以上的某女孩是大学生”的消息，问获得多少信息量？解：设随机变量 X 代表女孩子学历Xx1（是大学生）x2（不是大学生）P(X)0.250.75设随机变量 Y 代表女孩子身高Yy1（身高 >160cm） y2 （身高 <160cm）P(Y)0.5

13、0.5已知：在女大学生中有75%是身高 160 厘米以上的即： p( y1 / x1) 0.75求：身高 160 厘米以上的某女孩是大学生的信息量，即：I ( x1 / y1 )log p( x1 / y1)p(x1 ) p( y1 / x1 )0.250.75loglog1.415 bitp( y1 )0.5习题 2-122.12两个实验 X 和 Y， X=x1x2 x3,Y=y1 y2 y3,l联合概率 r xi, yjr ij 为r 11r12r137/ 241/240r21r22r231/ 241/ 41/ 24r31r32r3301/247/24（ 1）如果有人告诉你 X 和 Y 的

14、实验结果，你得到的平均信息量是多少？（ 2）如果有人告诉你 Y 的实验结果，你得到的平均信息量是多少？（ 3）在已知 Y 实验结果的情况下，告诉你 X 的实验结果，你得到的平均信息量是多少？解：联合概率p( xi , yj ) 为Yy1y2y3Xx17/241/240x21/241/41/24x301/247/24X 概率分布Xx1x2x3P8/248/248/24Y 概率分布是Yy1y2y3P8/248/248/24（ 1）H(X,Y)p( xi , yj )log12ijp( xi , yj )27 log 22441 log 2241 log 24247244=2.3bit/符号（2）

15、H (Y)31 log 231.58（bit/符号）3（3） H(X|Y)H(X,Y)H(Y)2.3 1.58= 0.72 （bit/符号）习题 2-14在一个二进制信道中， 信源消息集X=0,1 ，且 P(0)=P(1), 信宿的消息集Y=0,1, 信道传输概率P（ y=1| x=0 ） =1/4, P(y=0 | x=1)=1/8 。求：（ 1）在接收端收到y=0 后，所提供的关于传输消息X的平均条件互信息量I(X ； y=0).(2)该情况所能提供的平均互信息量I(X;Y).解：(1)P(y|x)=P(xy)=P(x|y)=I ( X ; y0 )p ( x i| y 0 ) logp

16、( xi | y 0)p ( xi )i(2)I(X;Y)p ( xi, y j ) logp ( x i/ y j )p ( x i )i , j=习题 2-26一个信源发出二重符号序列消息（ X1 ，X2), 其中， 第一个符号X1 可以是 可以是 A,B,C 中的一个， 第二个符号 X2 可以是 D,E,F,G 中的一个。已知各个p (x 1i ) 为 p(A)=1/2,p(B)=1/3,p(C)=1/6;各个 p(x2j | x 1i )值列成如下。求这个信源的熵（联合熵H(X1 ， X2) ）。解： P(y|x)=P(x)=P(xy)=根据公式H (XY)p( xi yj )I ( xi yj )p( xi yj ) log p( xi yj )i , ji , j得，H(X1 ， X2)=习题 2-302-30 有一个马尔可夫信源，已知转移概率为 p(s 1|s