《信息论第五讲》由会员分享，可在线阅读，更多相关《信息论第五讲（10页珍藏版）》请在金锄头文库上搜索。
1、2.2.4费诺(Fano)不等式我们曾借助于前已给出的通信模型，问从收到的 Y 可以得到关于 X 多少信 息，从而定义了平均互信息的概念。这实际上是一个在给定条件下对关心的随机 变量进行估值的问题。在现实问题中常会遇到这种现象，例如，我们想知道某种 产品的长度X,就用尺子去测量，得到读数Y。不同产品的长度是在一定范围内 的随机变量，由于测量误差我们也测不出被测产品的真实长度，所以，这也是根 据Y来估计X的问题。我们做过的一个习题说，当且仅当X是Y的单值函数时，随机变量X的条 件熵H(XIY)=0,推而广之，我们希望条件熵H(XIY)较小时，能以较低的误差概 率估计出X。费诺不等式量化了这个想法
2、。设待估计的随机变量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
3、, 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
4、= 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
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 )
6、 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)，其概率密度为
7、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)。渐近均分定理又叫序列分组定理，因为利用它可以把随机变量序列的集合分 为两个
8、子集：典型集和非典型集。根据对数的意义把式(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足够大，随机变
9、量序列都属于典 型集。性质(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 个等可
10、能的字母。由此打字机可产生长度为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极限
11、不存在的情况，这样式(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
12、.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个随机变量的每字符的熵。但是它们的单位都是（熵/每字符）。考虑
13、到 随机过程含有时间跨度的概念，每个字符的出现将占有一个时间段，如果把上 述熵率除以，我们就得到了单位时间的熵（也叫时间熵），这就是所以叫做熵 率的原因。平稳马尔可夫链的熵率简单地等于条件熵，使得计算起来十分方便, 下面的定理就叙述这个结果。定理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
14、(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概率
