資源描述：
《熵的可加性與有根概率樹(shù)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、熵的可加性與有根概率樹(shù)信息論課程講座之2熵的可加性與有根概率樹(shù)田寶玉1．熵的可加性lShannon首先提出熵的可加性含義如下：如果一種選擇可以分成兩步連續(xù)的選擇實(shí)現(xiàn)，[1]那么原來(lái)的熵H應(yīng)為H的單獨(dú)值的加權(quán)和?！皢为?dú)值”實(shí)際上是每次選擇的熵值，“權(quán)值”就是每次選擇的概率。例如，某隨機(jī)事件集合有3個(gè)事件，概率分別為：p=1/2，p=1/3，12p=1/6；這3個(gè)事件可以直接產(chǎn)生，也可分兩次產(chǎn)生，即先以1/2的概率產(chǎn)生兩事件中的3一個(gè)，然后在其中某一事件發(fā)生條件下再以2/3和1/3的概率產(chǎn)生兩事件中的一個(gè)。熵的可加性意味著：H(1/2
2、,1/3,1/6)=+HH(1/2,1/2)(1/2)(1/3,2/3)（1）上面等號(hào)右邊的第1項(xiàng)是第1次選擇的熵；由于第2次選擇只有1/2的概率發(fā)生，所以第2項(xiàng)是第2次選擇的熵與權(quán)值1/2的乘積。多步產(chǎn)生的事件也稱復(fù)合事件。[2]l最大熵原理的提出者Jaynes描述熵的可加性如下：設(shè)事件集合概率分別為(pp,L,)，1n我們不直接給出這些概率，而是先將前k個(gè)事件組合成一組看成一個(gè)事件，概率為w=pp++L，第2組有m個(gè)可能性，組合后分配的概率為w=pp++L，……。11k21k++km組合事件的不確定性為H(ww,L,)，給定第
3、1個(gè)組合事件發(fā)生條件下，第2個(gè)事件發(fā)生的1r概率為(p/w,L,pw/)……。熵的可加性意味著：111kH(p,L,p)=H(w,L,w)+wH(p/w,L,p/w)++wH(p/w,LL,pw/)1n1r111k12k++122km（2）通常，熵的可加性的一般形式寫(xiě)成：H(pp,L,pp,pp,L,pp,LL,pp,,)pp11111m221211mnnnnmn（3）=+H(p11,LL,pn)?piH(ppi,,)imi=1其中，mm??pij=ppi1++Lim，in=1,,L（4）jj==11[3][4]（2）與(3)實(shí)質(zhì)
4、是一樣的，可用于熵函數(shù)唯一性的證明。如果p=1,p=10()jk，對(duì)i=1,LL,i-1,in+-1,,1，那么（3）變?yōu)閕kij1熵的可加性與有根概率樹(shù)H(p,Lp,pp,,L,pp,ppLL,)1i-+1ii1iimin1,（5）=+H(p,L,p,p,p,LL,p)pH(pp,,)1i-+1ii11niiim式（5）也是熵的可加性的一種描述方式，而（5）是（4）的特例，而（1）是（5）的特例。l熵的可加性另一種形式[5]教材第25頁(yè)中對(duì)熵的可加性做了如下描述：設(shè)兩個(gè)隨機(jī)變量集合X、Y與的它們的聯(lián)合集XY的熵分別為H(X),H
5、(Y),H(XY)，則H(XY)=H(X)+H(Y
6、X)(2.2.16)實(shí)際上(2.2.16)與（3）式是一致的，只要設(shè)X集合中事件的概率分布為pp,,L，X與Y之1n間的條件概率矩陣為：??p11pp121Lm?÷pppLP=?÷21222m?÷MMM?÷pppLè?n12nnm即可。[5]l熵的可加性可以推廣到多維隨機(jī)變量聯(lián)合集的情況（教材第25頁(yè)）。設(shè)N維隨機(jī)變量集X1X2…Xn，則有H(X1X2…Xn)=H(X1)+H（X2
7、X1）+…+H（XN
8、X1…Xn-1）(2.2.17)當(dāng)X1X2…Xn，統(tǒng)計(jì)獨(dú)立（即Xi獨(dú)立于X1
9、X2…Xi-1）時(shí)，有H(X1X2…Xn)=H(X1)+H（X2）+…+H（XN）(6)稱為熵的強(qiáng)可加性。l熵的可加性可以從多種角度來(lái)理解：（1）復(fù)合事件集合的不確定性為組成該復(fù)合事件的各簡(jiǎn)單事件集合不確定性的和。（2）對(duì)信源輸出直接測(cè)量所得信息量等于分成若干步測(cè)量所得信息量的和。（3）信源的平均不確定性可以分步解除，每步解除的不確定性的和等于信源的熵。2.用有根概率樹(shù)計(jì)算熵[6]有根概率樹(shù)的概念首先見(jiàn)于Massey的著作，利用有根概率樹(shù)計(jì)算信源熵，有如下定[5]理（教材第20頁(yè)）。定理2.2.1離散信源的熵等于所對(duì)應(yīng)的有根概率樹(shù)
10、上所有節(jié)點(diǎn)(包括根節(jié)點(diǎn)，不包括葉)的分支熵用該節(jié)點(diǎn)概率加權(quán)的和，即H(X)=?q(u)H(u)iii(2.2.3)其中，q(ui)為節(jié)點(diǎn)ui的概率，H(ui)為節(jié)點(diǎn)ui的分支熵。有根概率樹(shù)計(jì)算熵的公式(2.2.3)實(shí)際上就是反復(fù)利用熵的可加性的結(jié)果。設(shè)一信源含r2熵的可加性與有根概率樹(shù)個(gè)符號(hào)，符號(hào)集A={aa,L,}，概率分別為pp,,L，對(duì)應(yīng)的有根概率樹(shù)包含k個(gè)內(nèi)部節(jié)點(diǎn)，1r1rr片樹(shù)葉，每片樹(shù)葉對(duì)應(yīng)一個(gè)信源符號(hào)。式(2.2.3)可寫(xiě)成如下形式：kH(p10,L,pr)=+q(u)?q(uii)Hu()（7）i=1其中，，H(u
11、0)為根節(jié)點(diǎn)u0的分支熵，而根節(jié)點(diǎn)u0的概率q(u0)=1。定理的證明現(xiàn)利用數(shù)學(xué)歸納法證明，對(duì)任何非負(fù)整數(shù)k，式(7)成立。當(dāng)k=0時(shí)，所有樹(shù)葉都直接與根相連，根的各分支的概率就是對(duì)應(yīng)信源符號(hào)的概率，信源的熵就等于根的分支熵，等式成立。當(dāng)k=1時(shí)，
