熵的可加性与有根概率树

1、 信息论课程讲座Z2爛的可加性与有根概率树田宝玉爛的可加性IShannon首先提出爛的可加性含义如F：如果一种选择可以分成两步连续的选择实现，那么原来的爛H应为H的单独值的加权和。“单独值”实际上是每次选择的爛值，“权值”就是每次选择的概率。例如，某随机事件集合有3个事件，概率分别为：p严1/2,必=1/3,卩3=1/6;这3个事件可以直接产生，也可分两次产生，即先以1/2的概率产生两事件中的一个，然后在其中某一事件发生条件卜再以2/3和1/3的概率产生两事件中的一个。爛的可加性意味着：H（l/2,l/3,l/6）=H（l/2,l/2）+（l/2）H（l/3,2/3）（1）上面等号右边的第1项

2、是第1次选择的爛：由丁第2次选择只有1/2的概率发生，所以第2项是第2次选择的爛与权值1/2的乘积。多步产生的事件也称复合事件。I最人爛原理的提出者Jaynes描述爛的可加性如卜佃：设事件集合概率分别为（必丄，几），我们不直接给出这些概率，而是先将前k个事件组合成一组看成一个事件，概率为w】=pi+L+以,第2组有m个可能性,组合后分配的概率为v2=pk+l+L+pk+m,o组合事件的不确定性为H（州丄，叫），给定第1个组合事件发生条件卜S第2个事件发生的概率为（卩/呵丄,pjwjo爛的可加性意味着:(2)H（p,p“）=H（W,L，叫）+吗/7（门仙丄.以/明）+叫/（以+/叫丄,pk+m/

3、w2）+L通常，爛的可加性的一般形式写成：(3)H（PiPmL，PP加,P2P2I，L，P2%，LPnPntL，仇）=H（p丄也）+卅（几丄仏）i=i其中，(4)mm7=1（2）与（3）实质是一样的，可用于爛函数唯一性的证明卩同。如果心=1仍=0（川灯，对心1丄j-lj+LL那么（3）变为H5丄Pl，口Pil，L,P%，门+丄丄几)(5)=H(a丄,Pi,pp,L,pn)+piH(p/rL%)式(5)也是爛的可加性的一种描述方式，而(5)是(4)的特例，而(1)是(5)的特例。I爛的可加性另一种形式教材第25页中对爛的可加性做了如卜描述:设两个随机变虽集合X、Y与的它们的联合集XY的矯分别为H

4、(X),H(Y),H(XY),则H(XY)=H(X)+H(Y|X)(2.2.16)实际上(2.216)与(3)式是一致的，只耍设X集合中事件的概率分布为L,pX与YZ河的条件概率矩阵为：PllPnLPgPlP12LPlmMMMPnPn2LPnm)即可。I爛的可加性可以推广到多维随机变最联合集的情况(教材第25页)。设N维随机变虽集XlX2.Xn,则有H(XiX2.Xn)=H(Xi)+H(X2IX1)+.+H(XN|Xi.Xn-i)(2.2.17)当XxXr-Xu,统计独立(即Xi独立于XxXr-Xx-x)时,有H(X1XI-Xj=H(Xx)+H(X2)+-+H(XF)(6)称为爛的强可加性。I

5、爛的可加性可以从多种角度来理解：复合事件集合的不确定性为组成该复合事件的各简单事件集合不确定性的和。对信源输岀直接测最所得信息最等丁分成若干步测最所得信息最的和。信源的平均不确定性可以分步解除，每步解除的不确定性的和等丁信源的爛。用有根概率树计算爛有根概率树的概念首先见于Massey的著作，利用有根概率树计算信源爛，有如卜定理(教材第20页)。定理2.2.1离散信源的矯等于所对应的有根概率树上所有节点(包括根节点，不包括叶)的分支矯用该节点概率加权的和，即H(X)=ZqgJHg)(2.2.3)其中，q(“)为节点0的概率，H(J为节点0的分支蠣。有根概率树计算嫡的公式(2.23)实际上就是反复

6、利用爛的可加性的结果。设一信源含r个符号，符号集A=arL卫，概率分别为刃丄/对应的有根概率树包含k个内部节点,r片树叶，每片树叶对应一个信源符号。式(2.2.3)可写成如卜形式：kH(L小)=g(心十工？仏)/(%)(7)r=l其中，H(&)为根节点&的分支爛，而根节点&的概率q(&)二1。定理的证明现利用数学归纳法证明，对任何非负整数k,式(7)成立。当k=0时，所有树叶都直接与根相连，根的各分支的概率就是対应信源符号的概率，信源的爛就等于根的分支爛，等式成立。当k=l时，树中的唯一一个内部节点(设为山)由若干片树叶作为其子节点，由丁爛的值与符号顺序无关，不妨设山的子节点为后m个符号,所对

7、应的概率分别为Pf,L,p,那么节点坷的概率为g)=j+L+p,分支爛为HM=H(pr_m+l/q(u),L,pr/q(u)o根据炳的可加性(5),信源的爛=H(pLPf、q(iJ+qg)H(Pf+JqyL，巴/q(J)=H(Pi，Lpr_m,?(“)+q(uJH(“J由于符号o,L,j和节点坷直接与根相连,所以H(p,LPr，q(uJ)就是根节点的爛，故当当k=l时，式(7)成立。假设k=n时，(7)式成立。现考虑k=n+l的情况。设概率树中阶数最高的一个内部节点为“曲，那么其子节点由若干片(设为s片)树叶构成，设为(丄,所对应的概率分别为几丄,p,节点|的概率为q(%J=p+L+pr,分支

8、爛为H(1也)=H(pjqgjL、pjqgj。根据爛的可加性(5)式，信源的爛H(Pi，L,pr,L也丄,p)；H(pLPm，P(”+J，/+i，L，必)+(仇/q(%),L，化/讥)(9)=H(p“Lm)+q(i也)H(%Jb”巴+=H(w0)+J2PgH(气)+)H(Mn+I)=H(u0)+刀p(i(JH(气)J=!(=1其中,a：炳的可加性;b：/(pl/,p(2),p,+i，L,几)是含有n个内部节点的爛，根据假设，(7)成立。这就证明了，当1;=11+1时，(7)式也成立。#举例用有根概率树和爛的可加性计算信息爛，有时可以简化运算例1计算H(l/2,1/4J/&1/8)。解用概率树求

9、爛：77(1/2,1/4,1/8,1/8)=(1+1/2+1/4)77(1/2)=7/4比特用爛的可加性求爛：H(1/2J/4.1/&1/8)=H(l/2,l/4,l/4)+(l/4)H(l/2,l/2)=H(l/2,l/2)+(l/2)H(l/2,1/2)+(1/4)77(1/2,1/2)=(1+1/2+1/4)77(1/2)=7/4比特注：用有根概率树和爛的可加性计算信息爛没有本质的不同，只是过程有些不同。例2：(教材第60页)3.2有一个二元无记忆信源,发0的概率为p,且pi，对信源进行编玛得到一个新信源S”=归丄，$曲,編码符号与原始序列的对应关系为：000.0000.01二元序列10

10、1001(门个)新信源符号(2)求H(S)=limH(Slt).T8解：由题意町得新信源各符号的概率分布为:0/7?-1i=n(1)根据爛的可加性,有H(SJ,(l-p)p=p)=H(1-p,p)+pH(lp,(lp)p.L,(1-p)p,pi)=H(p)+pHn_i(后面n个符号合并成一组)因此得到递推公式：H=H(p)+pH_(10)其中，H、=H(p)(11)反复利用(1),有pHn_x=pHp)+p-Hn_2p2H“=p2H(P)+pH“卩心比=p2H(p)+pn-lH上而各式(不包括(11)相加，得H“=(l+p+L+严)H(p)=H(p)1-卩(2)当“Too时，limH.=limH,由(9)得，H(S)=T8T8参考文献：1.Shannon.AMathematicalTheoryofCommunica