Ch2例题与证明一.docx

♦推导求条件熵为什么要用联合概率?先取一个 yj ，在已知 y j 条件下， X 的条件熵jjH(X/y )为：jH(X / y )=工 p(x / y )I(x / y )=p(x / y )log p(x / y )* * * * * * * • *j i j i j i j 2 i ji =1 i =1jH(X/y )在 Yj上式为仅知某一个 yj 时 X 的条件熵，它随着 yj 的变 化而变化，仍然是一个随机变量已知所有的儿时X仍然存在的不确定度，应该是进一步把集合上取数学期望，H(X / Y) = ^p(y )H(X / y )jjj=1=—区艺 p(y )p(x /y )log p(x /y )j i j 2 i jj=1 i=1=—区另 p (x y )log p (x / y )i j 2 i jj=1 i=1•条件熵是一个确定值，表示信宿在收到Y后, 信源 X 仍然存在的不确定度这是由于传输失 真造成的；• H(X /Y) 称为信道疑义度，也称损失熵；• 条件熵 H(Y / X) 为噪声熵［例2.1.4条件熵］已知X, Ye {0,1} ,XY构成的联合 概率为：p(00)=p(11)=1/8,p(01)=p(10)=3/8,计算条 件熵 H(X/Y)。

解： 根据条件熵公式：mnH(X / Y)=—审 p(xy )log p(x / y )i j 2 i j j=1 i=1p(x y )p (x / y ) = i ji j ~~P(yTj2首先求p(y/八p(y)，有j i j31p(0) = p(y = 0)=p(xy = 0C)+pxy =10) = + = c i - “ “11同理可求得211p(i)=p( y = 1)=万2 2从而有：p0/o)=吟 0/ y广 0)=鬻=需)=18=:=pi/D13p(1/0)=p(0/i)=4，H(X /Y) = —p(00)log p(0/0)——p(01)log p(0/1)—p(10)log p(1/0)2 2 2—p(11)log p(1/1)2(1 1 3 3\=—log — log x2=0.406 ( bit/symbol)24丿(8 24 8 24丿最大离散熵定理H (X ) < log n2证明：先证明一个常用不等式：In x0)用图形表示为：1令 f(x)=ln x -x-1)，则］f'(x) = _ — 1 ,可见当 x=1 时，x-1f(x)=0,它是f(x)的极值。

且/''(x) = < 0 ,故此极值x2为极大值所以有：f(x)< f(1)=0，当且仅当x=1时取等号这时 f(x)=ln x-(x-l) <0 => In x < (x-1)证法一：H(X)-log2n - p(x )logi2i-1工 p (x )log ni2i -1工p (卩吗i-11np (x )i令 x — ()，利用 ln x < x - 1, x > 0,且 log x = ln x log enp ( x ) 2 2iH (x) - log n < y p(x )[ 1 - 1]log e2 . , i np (x ) 2匸1 i=y [] - p(x )]log ni=i=0H (X) < log( pi 、iilog (红) < (乞-1)log e2 p p 2ii证法二：现令x =qi 为两个概率），则有i， 两边取统计平均值求得：y p. log 纟

故这一定理又被称为离散信源最大熵定理♦ 可加性的证明H (XY)= —工工 p(xy )log p(xy )• • • •i j 2 i j=—工工 p(xy )log [p(x )p(y / x )]• • c • • •i j 2 i j i=—XXp(x )p(y /x )log p(x ) + 工工p(xy )log p(y /x )• • • c • •i j i 2 i i j 2 j ii j i j工p(jy / x ) + H (Y / X) ji=—X p(x )log p(x )i 2 ii工 p(y / x ) = 1jij=H (X) + H (Y / X)利用:p(x y ) = p(x )p(y /x )i j i j i♦条件熵不大于信源熵（无条件熵）的证明证明：H (X / Y)二—工工 p (x y )log p (x / y )i j 2 i j工 p (x / y )log p (x / y )• • c • •i j 2 i ji工 p (x / y )log p (x )i j 2 i. • —iij二—工p(y )jj<—工p(y )jj2i=—X X p (y ) p (x / y )呃 p (x ) Xi j= — p(x ) log p(x )i 2 ii= H(X)其中,Xp(y )p(x /y ) =Xp(x yj i j i j上凸性的证明熵函数H（U）为P. = P（u）的上凸函数。

ii证明一：在证明本定理以前先介绍凸函数的概念1 ）先介绍凸集合：若集合C u Rn（n维欧氏空间），有P e C，q e C， 且对任意实数九:0 f ［九 P + (1 -九)q］ 则称f(•)为下凸函数或凹函数(U)其含义为：凸集 合中函数的线性组合不小于凸集合中线性组合的函 数若不等号相反，即疋(P + (1 -九)f (q) < f ［九 P + (1 -九)q］则称f (•)为上凸(n)o若将上述“ > ”、“< ”改为“>”、“<”则 分别称为严格凸和严格凹上述凹凸函数可以用下列形象直观图形来表示：M (p) + (1-九)f (q)>f Hp +(1—九)q]在［a,b］上定义的下凸(U)函数在［a,b］上定义的上凸（）函数（3）由上述凸函数性质，我们只需证明熵函数满足下 列不等式。

即熵函数为上凸函数H[po = 0p' + (1-0)p" ] >0H(p') + (1-0)H(p")i ' '(对照上凸函数性质，即f吕H,九o0 ) 其中0<0 < 1,而p0 =0p' + (I-0)p"因此只需证：i i iH [0p' + (1 -0) p"]-0H (p') - (1 -0) H (p")i i i i=-工[0p' + (1 -0)p"]log p0 +0》p' log p' + (1 -0)工 p" log p"i i i i i i ii i ip"i(Jensen 不等式 P.25)=-0 工 p' log p- - (1 -0 )》p" log^i p ' i> -0 log工p - (1-0)log 工p" pi i i>-0 logZ p' p0.° P"1 L-—0ii —I i i=-0 log 工 p0 - (1 -0 )log 工i=-0 logl —(1—0)logl=0证明中，我们引用了著名的 Jensen 不等式其含 义为：若f(x)是随机变量X ( xeX )的凸函数，则有:E[f (x)] > f [E(x)] —— f(x)下凸时E[f (x)] < f [E(x)] —— f(x)上凸时 上式证明中要注意： log x 为上凸函数。

设有一个多元函数或矢 量函数f (x ,x , ,x ) = f (X),1 2 n对任一小于1的正数a (0 af (X) + (1 — a)f (Y) 则称f为严格上凸函数 p( y )]n证明二：设P，Q为两组归一的概率矢量P = [P(x ), p(x ), , p(x )], Q = [p(y ), p(y ),1 2 n 1 2且0 < p(x ) < 1,…0 < p(y ) < 1 ii艺 p(x )工 p(y ) =1ii则 H (a P + (1—a )Q)[ap(x ) + (1—a)p(y )]log [ap(x) + (1—a)p(y )]i i 2 i i可以证明 0 0,1 -a > 0,p(x ) > 0,p(y ) > 0iiap(x ) + (1 -a)p(y ) > 0ii如果ap(x ) + (1 -a)p(y ) > 1ii则p(y ) > 1 ap(xi) > 1, p(x )丰 1,不可能 i T^ai而当p(y ) = 1-切(二)i ~~ap(x ) + (1 -a)p(y ) = 1ii故有0 aH(P)i 2 i i各p(x ), p(y )不完全相等，有ii-a工 p(x )log [ap(x ) + (1 -a)p(y )] > aH(P)i 2 i ii=1同理:—(1—a)x p(y )log [ap(x) + (1 -a)p(y)] > (1 -a)H(Q)i=1两式相加整理i 2 i iH[aP+(1-a)Q]>aH(P)+(1-a)H(Q)*严格上凸函数在定义域内的极大值必为最大值，用 上凸性求最大熵时，只需求导并取极值即可。

给定信源［X,p(x )］，求H(X)在"p(x) = 1限制下的条iii=1件极值令：一、 H(X) + 九 p(x ) 。