资源预览内容
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
第9页 / 共10页
第10页 / 共10页
亲,该文档总共10页全部预览完了,如果喜欢就下载吧!
资源描述
2.2.4费诺(Fano)不等式我们曾借助于前已给出的通信模型,问从收到的 Y 可以得到关于 X 多少信 息,从而定义了平均互信息的概念。这实际上是一个在给定条件下对关心的随机 变量进行估值的问题。在现实问题中常会遇到这种现象,例如,我们想知道某种 产品的长度X,就用尺子去测量,得到读数Y。不同产品的长度是在一定范围内 的随机变量,由于测量误差我们也测不出被测产品的真实长度,所以,这也是根 据Y来估计X的问题。我们做过的一个习题说,当且仅当X是Y的单值函数时,随机变量X的条 件熵H(XIY)=0,推而广之,我们希望条件熵H(XIY)较小时,能以较低的误差概 率估计出X。费诺不等式量化了这个想法。设待估计的随机变量X: xi,x2, ,xn具有分布P(x),我们观察与X相关 联的随机变量y它关于x的条件分布是p(y1 x)。由Y计算函数g(Y)作为X的 估值f = g(Y),现在要对X丰X的概率做出限定。定义误差概率为P 二 P 乂丰 X(2-49)e注意X TY TX构成马尔可夫链。费诺不等式表述如下。定理2.11(2-50)(2-51)H (P ) + P log(n -1) H (X I Y)e e其中n是随机变量个数。式(2-50)可以减弱为1 + P log n H (X I Y)e证明 首先定义一个误差随机变量厂1如果个HXE = o如果X=x然后根据熵的链式法则将H(E, X 1 Y)以两种方式展开(2-52)H (E, X I Y) = H (X I Y) + H (E I X, Y)H (E, X I Y) = H (E I Y) + H (X I E, Y)因为E是X和g(Y )的函数,所以(2-52)中第二项H(E I X,Y) = 0 ;因 为条件作用使熵减少,所以(2-53)中第一项H(E I Y) J H(E),又因为E是一 个二值随机变量,所以H(E) = H(匚),于是得到:(2-54)H (X IY) H (P) + H (X I E, Y)而根据熵是统计平均的概念:H (X I E, Y)二 P (E = 0) H (X I Y, E = 0) + P (E = 1) H (X I Y, E = 1) rrE=0意味着没有估计误差,知道Y就完全确定了 X,所以H(XIY,E=O)=O。当E=1 时,估值X = g (Y)能取X中其它n-1个值,根据定理2.11, H(X I Y,E = 1) log(n -1),将这些结果代入式(2-54),得到H(X 丨 Y) H(P) + P (E 二 0) x0 + PH(X 丨 Y, E 二 1)e r e p(x j) j,i = 1,2,n,此时的误差概率为iijP = 1 - p(x ),而费诺不等式变为 H(Pe) + Pe log(n 1) H(X)。eie e2.2.5 渐近均分性 在通信过程中,信源往往要发出很长的消息,例如发出一份中文稿件,相当 于一个汉字的序列,如果把单个汉字看成是一个随机变量的实现,整个稿件就是 对随机变量序列的一次观测。我们注意到,上例中每个字都来源于同一个字库,而且一般地认为前后两个 字互相独立,也就是说,这个随机变量序列是独立同分布的(i.i.d.)。概率论中 的大数定律指出,对于独立同分布的随机变量序列,当n很大时,丄X n x.近似n i =1 i 等于期望值EX。渐近均分性与此类似,其正式描述是:定理2.12 (AEP)如果x XX 为i.i.d.序列,而且服从P(x),则依概 1 2 n率有-logP(X .X2,,X ) tH(X)(2-55)n12 n所谓依概率趋近H(X),即对任意e 0,有r 1)lim P I - log p (X1, X 2,X ) H(X)le = 1(2-56)12nn T8证明 因为 X 是独立同分布的,所以.P(X 1, X2,Xn) = p(X.),-ilogp(X1,X ,X ) = -1X logp(X.)。12 n.n12 n n.当 n * 时,依概率有-1 工 n log p(X.) T-E log p( X)二 H ( X )ni=1i这意味着p(X , X ,X )会以很高的概率接近于2 -nH(x)。12 n例2.13设随机变量X e 0,1),其概率密度为P(1)= P=1/2,现信源发出 随机序列,问序列(1,0,1,1,0,1)出现的可能性有多大?11解 H(X) = 1,所以,依概率二logp(1,0,1,1,0,1) t 1,p(1,0,1,1,0,1) = 2-6 = 66 64 位二进制序列共有 64个,如果01 等概出现,则序列(1,0,1,1,0,1)出现的可能 性是 1/64 当然是合理的。如果 P(1) = p, P(0) = q,则 H(X) = -plog p - qlogq, 序列出现的概率就成为p(1,0,1,1,0,1) = 2-6H(X)。渐近均分定理又叫序列分组定理,因为利用它可以把随机变量序列的集合分 为两个子集:典型集和非典型集。根据对数的意义把式(2-55)稍加变换,就得 到典型集的的定义:定义2.11满足如下性质的序列(珂,x2,,xn)的集合叫做p(x)的典型 集 A ( n) :E2-n(H(X)+) p(X,x2,xn) 2-n(H(X)-e)(2-57)典型集具有如下性质:(1)如果(X, X ,x ) e AE),则12 n EH (X)-s- 1log p( x1, x2,,x ) 1-EI A(n) | (1 -e)2n(H(X)-)E我们略去这些性质的证明,重点说明它们的意义(证明并不困难,有兴趣的 读者可以作为练习)。性质(1)、(2)说明,对任意小的,只要n足够大,随机变量序列都属于典 型集。性质(3)、(4)说明了典型集包含的随机变量序列的个数,由于非常小, 所以| AE(n) |T 2nH(X )(2-58)E这就是说,从平均意义上讲,用nH(X)比特就可以表示序列Xn。2.2.6 随机过程的熵率渐近均分性表明,在平均意义下使用nH(X)比特足以描述n个独立同分布 的随机变量序列,如果随机变量不独立,尤其是平稳随机过程,情况将会怎样? 我们在下面引出随机过程熵率的概念。定义 2.12 随机过程的熵率定义为H(X)=lim lH( X i, X ,化)(2-59)熵率反映随机变量序列的熵随 n 值增长的变化情况。例 2.14 假定一台打字机可输出 m 个等可能的字母。由此打字机可产生长度为n的序列mn个,且等可能出现。因此 H(X ,X,,X ) = logmn,熵率为12 nH(X) = log m比特/每字符。例 2.15 对独立同分布随机变量序列,口(X)H(X1,X ,X )nH(X1) 口,H (X) = lim12 n = lim = H (X )nn1这个结果正是我们期望的每个字符的熵率。对于独立但非同分布随机变量序 列 , 情 况 变 得 复 杂 起 来 , 因 为 在 求 熵 率 过 程 中 , 我 们 遇 到 H(X1,X ) = E n H(X.),和式中的H(Xi )不全相等。有可能出现1工H(X.)的1n/=11n1极限不存在的情况,这样式(2.59)就失去意义。因此,重新定义一个与(2-59) 相关的量:H(X)= lim H(Xn 1 Xn_i,Xn_2,X1)(2-60)ng这个极限一定存在吗?定理2.13对于平稳随机过程,H(X I X ,,X J随n递减且存在极限。n-11证明 H(Xn+1 1 Xn,Xn-1,,H(X+1 1 Xn,X-1,,X2)= H(X | Xnn -1,X1)其中不等号是由条件作用使熵减少, 等号由平稳性得到。 上式说明H(X I X ,,X )是随n递减的,再由它的非负性,证明极限H(X)必存在。 n n -11那么(2-59)和(2-60)两个极限有什么关系呢?定理2.14 对于平稳随机过程,有H (X) = HX)(2-61)1证明 简记H(X1,X2,,X ) = b,H(X I X,XJ = a.n 1 2n nii -11 i由链式法则:H(X1,X2,,X )=工 n H(X. I X,,X1)12n.=1ii-11用简记符号改写为两边取极限limbnn丄limnn根据定理2.13等号右边趋向于H(X),而等号左边等于H 00,定理得证。上述定理的证明不是十分严密,并不影响所得结论。注意H(X)与H(X)的 物理意义已经不同,前者表示在已知过去情况下最新出现随机变量的条件熵,后 者是n个随机变量的每字符的熵。但是它们的单位都是(熵/每字符)。考虑到 随机过程含有时间跨度的概念,每个字符的出现将占有一个时间段,如果把上 述熵率除以,我们就得到了单位时间的熵(也叫时间熵),这就是所以叫做熵 率的原因。平稳马尔可夫链的熵率简单地等于条件熵,使得计算起来十分方便, 下面的定理就叙述这个结果。定理2.15设X为平稳马尔可夫链,其分布为,转移矩阵为P,则熵率H (X)证明H (X).P. .logP.i i, j i, ji, j对于平稳马尔可夫链,熵率的计算十分简单,IXnH (X) limH (XH(X2|X1).P (i1, Ij,X) limH (X.)logP ( . | .)ij ii, jijlogPijiPi j logPi, j(2-62)这时有IX 1)j例2.16有两状态的马尔可夫链,i, j其转移概率为_ 1P1,求其熵率。解此一阶马尔可夫链有两种状态,四个 转移概率。可绘香农线图如图。a概率密度函数为,则有:设两个状态的21由线图1图2-5例题2.16附得到)2 ,即12将上两个方程联立,解得仿照定理 2.15 的证明3H (X) = H (X 2I X1)= -P(l-a )log(l-a) +a log a卩 2 p log p + (1- p )log(l- p)paOTP H(a) F H(卩)4图 2-6 例题例 2.17 设一个粒子可以在右图上由一个节2.17 附图点到另一个节点作随机游动,表示为X , X e 1,2,m是图中的顶点序列。 nn设连接节点i的各边权重之和为W =y W,从X = i移到X =j的转移ij i , jnn +1概率
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号