信息論第五講

2.2.4費(fèi)諾(Fano)不等式我們?cè)柚谇耙呀o出的通信模型，問從收到的Y可以得到關(guān)于X多少信息，從而定義了平均互信息的概念。這實(shí)際上是一個(gè)在給定條件下對(duì)關(guān)心的隨機(jī)變量進(jìn)行估值的問題。在現(xiàn)實(shí)問題中常會(huì)遇到這種現(xiàn)象，例如，我們想知道某種產(chǎn)品的長度X,就用尺子去測(cè)量，得到讀數(shù)Y。不同產(chǎn)品的長度是在一定范圍內(nèi)的隨機(jī)變量，由于測(cè)量誤差我們也測(cè)不出被測(cè)產(chǎn)品的真實(shí)長度，所以，這也是根據(jù)Y來估計(jì)X的問題。我們做過的一個(gè)習(xí)題說，當(dāng)且僅當(dāng)X是Y的單值函數(shù)時(shí)，隨機(jī)變量X的條件熵H(XIY)=0,推而廣之，我們希望條件熵H(XIY)較小時(shí)，能以較低的誤差概率估計(jì)出X。費(fèi)諾不等式量化了這個(gè)想法。設(shè)待估計(jì)的隨機(jī)變量X：xi，x2，，xn具有分布P(x)，我們觀察與X相關(guān)聯(lián)的隨機(jī)變量y它關(guān)于x的條件分布是p(y1x)。由Y計(jì)算函數(shù)g(Y)作為X的估值f=g(Y)，現(xiàn)在要對(duì)X豐X的概率做出限定。定義誤差概率為P二P{乂豐X} (2-49)e注意XTYTX構(gòu)成馬爾可夫鏈。費(fèi)諾不等式表述如下。定理2.11(2-50)(2-51)H(P)+Plog(n-1)>H(XIY)(2-50)(2-51)ee其中n是隨機(jī)變量個(gè)數(shù)。式(2-50)可以減弱為1+Plogn>H(XIY)e證明首先定義一個(gè)誤差隨機(jī)變量廠1如果個(gè)HXE=<o如果X=x然后根據(jù)熵的鏈?zhǔn)椒▌t將H(E,X1Y)以兩種方式展開(2-52)H(E,XIY)=H(XIY)+H(EIX,Y)(2-52)H(E,XIY)=H(EIY)+H(XIE,Y)因?yàn)镋是X和g(Y)的函數(shù)，所以(2-52)中第二項(xiàng)H(EIX，Y)=0；因?yàn)闂l件作用使熵減少，所以(2-53)中第一項(xiàng)H(EIY)JH(E)，又因?yàn)镋是一個(gè)二值隨機(jī)變量，所以H(E)=H(匚)，于是得到：(2-54)H(XIY)<H(P)+H(XIE,Y)(2-54)而根據(jù)熵是統(tǒng)計(jì)平均的概念：H(XIE,Y)二P(E=0)H(XIY,E=0)+P(E=1)H(XIY,E=1)rrE=0意味著沒有估計(jì)誤差，知道Y就完全確定了X,所以H(XIY,E=O)=O。當(dāng)E=1時(shí)，估值X=g(Y)能取X中其它n-1個(gè)值，根據(jù)定理2.11，H(XIY,E=1)<log(n-1)，將這些結(jié)果代入式(2-54),得到H(X丨Y)<H(P)+P(E二0)x0+PH(X丨Y,E二1)ere<H(P)+Plog(n-1)ee費(fèi)諾不等式得證。如果沒有任何關(guān)于Y的知識(shí)，只能在毫無信息的情況下估計(jì)X,對(duì)X的最佳估計(jì)是X=x.，其中p(x.)>p(xj)j,i=1,2,…,n，此時(shí)的誤差概率為i i jP=1-p(x)，而費(fèi)諾不等式變?yōu)镠(Pe)+Pelog(n—1)>H(X)。e i ee2.2.5漸近均分性在通信過程中，信源往往要發(fā)出很長的消息，例如發(fā)出一份中文稿件，相當(dāng)于一個(gè)漢字的序列，如果把單個(gè)漢字看成是一個(gè)隨機(jī)變量的實(shí)現(xiàn)，整個(gè)稿件就是對(duì)隨機(jī)變量序列的一次觀測(cè)。我們注意到，上例中每個(gè)字都來源于同一個(gè)字庫，而且一般地認(rèn)為前后兩個(gè)字互相獨(dú)立，也就是說，這個(gè)隨機(jī)變量序列是獨(dú)立同分布的(i.i.d.)。概率論中的大數(shù)定律指出，對(duì)于獨(dú)立同分布的隨機(jī)變量序列，當(dāng)n很大時(shí)，丄Xnx.近似ni=1i等于期望值EX。漸近均分性與此類似，其正式描述是：定理2.12(AEP)如果xX…X為i.i.d.序列，而且服從P(x)，則依概12n率有-’logP(X.X2,…，X)tH(X) (2-55)n 1 2n所謂依概率趨近H(X)，即對(duì)任意e>0，有r1 )limPI-—logp(X1,X2,…,X)—H(X)l<e=1 (2-56)12nnT8證明因?yàn)閄是獨(dú)立同分布的，所以.P(X1,X2,…,Xn)=^p(X.)，-ilogp(X1,X…,X)=-1Xlogp(X.)。1 2n . n 1 2nn .當(dāng)n*時(shí)，依概率有-1工nlogp(X.)T-Elogp(X)二H(X)n i=1 i這意味著p(X,X,…,X)會(huì)以很高的概率接近于2-nH(x)。1 2n例2.13設(shè)隨機(jī)變量Xe{0,1)，其概率密度為P(1)=P⑼=1/2，現(xiàn)信源發(fā)出隨機(jī)序列，問序列(1,0,1,1,0,1)出現(xiàn)的可能性有多大？11解H(X)=1,所以，依概率—二logp(1,0,1,1,0,1)t1，p(1,0,1,1,0,1)=2-6=—6664位二進(jìn)制序列共有64個(gè)，如果0\1等概出現(xiàn)，則序列(1,0,1,1,0,1)出現(xiàn)的可能性是1/64當(dāng)然是合理的。如果P(1)=p,P(0)=q，則H(X)=-plogp-qlogq，序列出現(xiàn)的概率就成為p(1,0,1,1,0,1)=2-6H(X)。漸近均分定理又叫序列分組定理，因?yàn)槔盟梢园央S機(jī)變量序列的集合分為兩個(gè)子集：典型集和非典型集。根據(jù)對(duì)數(shù)的意義把式(2-55)稍加變換，就得到典型集的的定義：定義2.11滿足如下性質(zhì)的序列(珂，x2,…，xn)的集合叫做p(x)的典型集A(n)：E2-n(H(X)+￡)<p(X],x2,…,xn)<2-n(H(X)-e) (2-57)典型集具有如下性質(zhì)：(1)如果(X],X…,x)eAE)，則1 2nEH(X)-s<-1logp(x1,x2，…,x)<H(X)+sn 12n⑵當(dāng)n充分大時(shí)，有P{A#)}>1-￡E⑶IA(n)|<2n(H(X)+￡)，其中|AI表示集合A中的元素個(gè)數(shù)E⑷當(dāng)n充分大時(shí)，有IA(n)|>(1-e)2n(H(X)-￡)E我們略去這些性質(zhì)的證明，重點(diǎn)說明它們的意義(證明并不困難，有興趣的讀者可以作為練習(xí))。性質(zhì)(1)、(2)說明，對(duì)任意小的￡，只要n足夠大，隨機(jī)變量序列都屬于典型集。性質(zhì)(3)、(4)說明了典型集包含的隨機(jī)變量序列的個(gè)數(shù)，由于￡非常小，所以|AE(n)|T2nH(X) (2-58)E這就是說，從平均意義上講，用nH(X)比特就可以表示序列Xn。2.2.6隨機(jī)過程的熵率漸近均分性表明，在平均意義下使用nH(X)比特足以描述n個(gè)獨(dú)立同分布的隨機(jī)變量序列，如果隨機(jī)變量不獨(dú)立，尤其是平穩(wěn)隨機(jī)過程，情況將會(huì)怎樣？我們?cè)谙旅嬉鲭S機(jī)過程熵率的概念。定義2.12隨機(jī)過程的熵率定義為H(H(X)=limlH(Xi,X…,化)(2-59)熵率反映隨機(jī)變量序列的熵隨n值增長的變化情況。例2.14假定一臺(tái)打字機(jī)可輸出m個(gè)等可能的字母。由此打字機(jī)可產(chǎn)生長度為n的序列mn個(gè)，且等可能出現(xiàn)。因此H(X,X，…,X)=logmn，熵率為1 2nH(X)=logm比特/每字符。例2.15對(duì)獨(dú)立同分布隨機(jī)變量序列，口(X)H(X1,X…,X) nH(X1)口",H(X)=lim 1 2n=lim—=H(X)n n 1這個(gè)結(jié)果正是我們期望的每個(gè)字符的熵率。對(duì)于獨(dú)立但非同分布隨機(jī)變量序列，情況變得復(fù)雜起來，因?yàn)樵谇箪芈蔬^程中，我們遇到H(X1,…,X)=EnH(X.)，和式中的H(Xi)不全相等。有可能出現(xiàn)1工H(X.)的1 n /=1 1 n 1極限不存在的情況，這樣式(2.59)就失去意義。因此，重新定義一個(gè)與(2-59)相關(guān)的量：H'(X)=limH(Xn1Xn_i，Xn_2，…，X1) (2-60)n—g這個(gè)極限一定存在嗎？定理2.13對(duì)于平穩(wěn)隨機(jī)過程，H(XIX］，…,XJ隨n遞減且存在極限。n -1 1證明H(Xn+11Xn，Xn-1，…,"H(X+11Xn，X-1，…,X2)=H=H(X|Xn n-1,…,X1)其中不等號(hào)是由條件作用使熵減少，等號(hào)由平穩(wěn)性得到。上式說明H(XIX，…,X)是隨n遞減的，再由它的非負(fù)性，證明極限H'(X)必存在。nn-1 1那么(2-59)和(2-60)兩個(gè)極限有什么關(guān)系呢？定理2.14對(duì)于平穩(wěn)隨機(jī)過程，有H(X)=H《X) (2-61)1證明簡記—H(X1,X2，…,X)=b，H(XIX「，…XJ=a.n12 nn i i-1 1i由鏈?zhǔn)椒▌t：H(X1,X2，…,X)=工nH(X.IX「，…,X1)1 2 n .=1 i i-1 1用簡記符號(hào)改寫為

nna.i=1 1兩邊取極限lim工nlim工nmglimbnnsa.i=1i根據(jù)定理2.13，等號(hào)右邊趨向于H'(X)，而等號(hào)左邊等于H(X)，定理得證。上述定理的證明不是十分嚴(yán)密，并不影響所得結(jié)論。注意H'(X)與H(X)的物理意義已經(jīng)不同，前者表示在已知過去情況下最新出現(xiàn)隨機(jī)變量的條件熵，后者是n個(gè)隨機(jī)變量的每字符的熵。但是它們的單位都是(熵/每字符)?？紤]到隨機(jī)過程含有時(shí)間跨度的概念，每個(gè)字符的出現(xiàn)將占有一個(gè)時(shí)間段工，如果把上述熵率除以t，我們就得到了單位時(shí)間的熵(也叫時(shí)間熵)，這就是所以叫做熵率的原因。平穩(wěn)馬爾可夫鏈的熵率簡單地等于條件熵，使得計(jì)算起來十分方便,下面的定理就敘述這個(gè)結(jié)果。定理2.15設(shè)｛X｝為平穩(wěn)馬爾可夫鏈，其分布為卩，轉(zhuǎn)移矩陣為p，則熵率(2-62)H(X)=-Er.P..logP..(2-62)ii,j i,ji,j證明對(duì)于平穩(wěn)馬爾可夫鏈，熵率的計(jì)算十分簡單，這時(shí)有,X)=limH(XIX)1 nn-1H(X,X)=limH(XIX)1 nn-1n n-1=H(X2IX1)=-E=H(X2IX1)=-ERP(R.IR,)logP(R.IR.)2 1 iji ji一P.logP.i,j i,j=丄RP.logP.ii,j i,jj,j例2.16有兩狀態(tài)的馬爾可夫鏈，其轉(zhuǎn)移概率為1-aa卩1-卩'求其熵率。解此一階馬爾可夫鏈有兩種狀態(tài)，四個(gè)轉(zhuǎn)移概率?？衫L香農(nóng)線圖如圖。設(shè)兩個(gè)狀態(tài)的CL1-B概率密度函數(shù)為卩，則有：片+巴=1由線圖圖2-5例題2.16附得到氣=片(1")+巴卩，即仲］=和2將上兩個(gè)方程聯(lián)立，解得仿照定理2.15的證明3H(X)=H(X2IX1)?=-P][(l-a)log(l-a)+aloga 卩2[plogp+(1-p)log(l-p)]paOTPH(a)FH(卩)4圖2-6例題例圖2-6例題2.17附圖點(diǎn)到另一個(gè)節(jié)點(diǎn)作隨機(jī)游動(dòng)，表示為｛X｝，Xe｛1,2,…,m｝是圖中的頂點(diǎn)序列。nn設(shè)連接節(jié)點(diǎn)i的各邊權(quán)重之和為W=yW，從X=i移到X=j的轉(zhuǎn)移TOC\o"1-5"\h\zi ji,j n n+1概率應(yīng)該是連接i和j的邊的權(quán)重占與；相連的所有邊權(quán)重的比例，即P= —= 。記yW=W，則圖中所有邊權(quán)重之和yW=2W，所以門yWW i,j：j>ii,j iii,k ik每個(gè)節(jié)點(diǎn)的概率為卩=y—=業(yè)。容易證明，y卩p=卩，因此，本例可以iW2W iii,j jii看作平穩(wěn)馬爾可夫鏈?，F(xiàn)在計(jì)算它的熵率。yy ywywwH(X)=H(XIX)=—卩PlogP=—i4log42l i i,j i,j 2w wwTOC\o"1-5"\h\zi j i ji iywwyww yw w=_ 4log4=_ 4log4+ 4logi-