馬爾可夫信源極限熵

1、第 2 章 信源與信息熵香農(nóng)信息論的基本點用隨機變量或隨機矢量來表示信源，運用概率論和隨機過程的理論來研究信息。信源的分類按照信源發(fā)出的消息在時間上和幅度上的分布情況可將信源分成離散信源和連續(xù)信源兩大類 .單符號信源概率空間描述自信息量單位： bit （一個比特表示一個等概率的二進(jìn)制符號信息量）自信息量與 不確定度的關(guān)系不確定度 :隨機事件的不確定度在數(shù)量上等于它的自信息量，兩者的單位相同，但含義卻不相同一個出現(xiàn)概率接近于 1 的隨機事件，發(fā)生的可能性很大，所以它包含的不確定度就很小。一個出現(xiàn)概率很小的隨機事件，很難猜測在某個時刻它 能否發(fā)生，所以它包含的不確定度就很大。若是確定性事件，出現(xiàn)概

2、率為1，則它包含的不確定度為0。說明:具有某種概率分布的隨機事件不管發(fā)生與否，都存在不確定度，不確定度表征了該事件的特性，而自信息量是在該事件發(fā)生后給予觀察者的信息量。聯(lián)合自信息量為：條件自信息量為：信源熵=【信源的平均不確定度】=【平均自信息量】條件熵：H(X /Y)p(xi, yj)I (xi | yj)p(xi, yj )log p(xi| yj )i, ji聯(lián)合熵H(X,Y)p(xi, yj)I (xi, yj )p(xi , yj )log p(xi, yj )i, ji聯(lián)合熵、條件熵與信源熵的關(guān)系H(XY)=H(X)+H(Y/X) ，H(XY)=H(Y)+H(X/Y)互信息定義：后

3、驗概率與先驗概率比值的對數(shù)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) ：可看作唯一地確定信道噪聲所需要的平均信息量互信息量與熵的關(guān)系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、性：數(shù)據(jù)處理過程中只會失掉一些信息，絕不會創(chuàng)造出新的信息最大熵定理(1) 限峰功率最大熵定理：對于定義域為有限的隨機矢量X，當(dāng)它是均勻分布時，具有最大熵。(2) 限平均功率最大熵定理：若連續(xù)變量 X 的方差一定，當(dāng)它是正態(tài)分布時具有最大熵。信源的序列熵：（請注意：序列X 的多種寫法?。〩(XL) H(X1X2XL) H(X1 ) H(X2/X 1) H(XL/X 1X2XL-1 )平均每個符號的熵為HL(X)1 H(X L1 X 2X L)若當(dāng)信源退化為無記憶時，有H(X)H(X 1X 2X L )H(X 1)H X 2H X L若進(jìn)一步又滿足平穩(wěn)性時，則有H(X)LH(X 1 )推廣結(jié)論馬爾

5、可夫信源表述有記憶信源要比表述無記憶信源困難得多。實際上信源發(fā)出的符號往往只與前若干個符號的依賴關(guān)系強，而與更前面的符號依賴關(guān)系弱。為此，可以限制隨機序列的記憶長度。當(dāng)記憶長度為 m+1時，稱這種有記憶信源為 m階馬爾可夫信源。也就是信源每次發(fā)出的符號只與前 m個符號有關(guān)，與更前面的符號無關(guān)。穩(wěn)態(tài)分布概率定義：若齊次馬爾可夫鏈對一切 i,j 存在不依賴于 i 的極限，則稱其具有遍歷性， Wj 稱為穩(wěn)態(tài)分布概率馬爾可夫信源極限熵：H(X)p(si)H ( X / si)WiH ( X / si)ii其中， H X/s ip(xj /si)logp(xj /si)j冗余度：它表示給定信源在實際發(fā)出

6、消息時所包含的多余信息.( 也稱為多余度或剩余度 ).定義信息效率:H(X)H m ( X )定義冗余度 :1 1H(X) H m ( X )其中： H (X) 為信源實際熵， Hm(X)信源最大熵。習(xí)題 2 信源與信息熵習(xí)題2-12.1 一個馬爾可夫信源有3 個符號 u1, u2 ,u3 ，轉(zhuǎn)移概率為： 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 ，畫出狀態(tài)圖并求出各符號穩(wěn)態(tài)概率。233解：狀態(tài)圖

7、如下狀態(tài)轉(zhuǎn)移矩陣為：設(shè)狀態(tài) u1，u2，u3 穩(wěn)定后的概率分別為W1，W2、W3111W1W 2W3 W1233WP W12W 2W1W 3由W 3 1，得： 23W1 W22W 3W 23W1 W2 W3110W1259計算可得： W 2256W 325習(xí)題 2-22.2 由符號集 0 ，1 組成的二階馬爾可夫鏈，其轉(zhuǎn)移概率為：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 。畫出狀態(tài)圖，并計

8、算各狀態(tài)的穩(wěn)態(tài)概率。解： 因是二階馬爾可夫信源 , 此信源任何時刻發(fā)出的符號只與前兩個符號有關(guān) , 而與更前面的符號無關(guān)。如原來狀態(tài)為 00, 則此時刻只可能發(fā)出符號 0 或 1, 下一時刻只能轉(zhuǎn)移到 00,01 狀態(tài) , 由于處于 00 狀態(tài)發(fā)符號 0 的概率為 0.8, 處在 00 狀態(tài)時發(fā)符號 1 的概率為 0.2, 轉(zhuǎn)移到 01 狀態(tài) ,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于是可以列出轉(zhuǎn)移概率矩陣：0.80.200000.50.5p0.50.500000.20.8狀態(tài)圖為：設(shè)各狀態(tài) 00， 01，10，11 的穩(wěn)態(tài)分布概率為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習(xí)題 2-3同時擲出兩個正常的骰子，也就是各面呈現(xiàn)的概率都為1/6 ，求：(1) “3 和 5 同時出現(xiàn)”這

10、事件的自信息；(2) “兩個 1 同時出現(xiàn)”這事件的自信息；(3) 兩個點數(shù)的各種組合（無序）對的熵和平均信息量；(4) 兩個點數(shù)之和（即 2, 3, , 12 構(gòu)成的子集）的熵；(5) 兩個點數(shù)中至少有一個是 1 的自信息量。解： (1)p ( x i)11111666618I ( xi)logp ( xi )14 .170 bitlog18(2)p ( xi)1116636I ( xi )log p ( xi )log 15.170bit36(3) 兩個點數(shù)的排列如下：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)參考上面的兩個點數(shù)的排列，可以得出兩個點數(shù)求和的概率分布如下：X23456789101112P(X )111151511113618129366369121836H (X)p( xi ) log p( xi)(5)i21121log12111125511log1812log2loglog366l

12、og36361812993663.274 bit / symbolp( xi )1111116636I ( xi )log p(xi )log11bit1.71036習(xí)題 2-52.5居住某地區(qū)的女孩子有25%是大學(xué)生，在女大學(xué)生中有75%是身高 160 厘米以上的，而女孩子中身高160 厘米以上的占總數(shù)的一半。假如我們得知“身高160 厘米以上的某女孩是大學(xué)生”的消息，問獲得多少信息量？解：設(shè)隨機變量 X 代表女孩子學(xué)歷Xx1（是大學(xué)生）x2（不是大學(xué)生）P(X)0.250.75設(shè)隨機變量 Y 代表女孩子身高Yy1（身高 >160cm） y2 （身高 <160cm）P(Y)0.5

13、0.5已知：在女大學(xué)生中有75%是身高 160 厘米以上的即： p( y1 / x1) 0.75求：身高 160 厘米以上的某女孩是大學(xué)生的信息量，即：I ( x1 / y1 )log p( x1 / y1)p(x1 ) p( y1 / x1 )0.250.75loglog1.415 bitp( y1 )0.5習(xí)題 2-122.12兩個實驗 X 和 Y， X=x1x2 x3,Y=y1 y2 y3,l聯(lián)合概率 r xi, yjr ij 為r 11r12r137/ 241/240r21r22r231/ 241/ 41/ 24r31r32r3301/247/24（ 1）如果有人告訴你 X 和 Y 的

14、實驗結(jié)果，你得到的平均信息量是多少？（ 2）如果有人告訴你 Y 的實驗結(jié)果，你得到的平均信息量是多少？（ 3）在已知 Y 實驗結(jié)果的情況下，告訴你 X 的實驗結(jié)果，你得到的平均信息量是多少？解：聯(lián)合概率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/符號）習(xí)題 2-14在一個二進(jìn)制信道中， 信源消息集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(tǒng)=0 后，所提供的關(guān)于傳輸消息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=習(xí)題 2-26一個信源發(fā)出二重符號序列消息（ 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 )值列成如下。求這個信源的熵（聯(lián)合熵H(X1 ， X2) ）。解： P(y|x)=P(x)=P(xy)=根據(jù)公式H (XY)p( xi yj )I ( xi yj )p( xi yj ) log p( xi yj )i , ji , j得，H(X1 ， X2)=習(xí)題 2-302-30 有一個馬爾可夫信源，已知轉(zhuǎn)移概率為 p(s 1|s