渐近等分割特性aep 2讲下信源2chapter 3

Chapter3渐近等分割（AsymptoticEquipartitionAEP（2讲下1nn大数定理指出：对于独立同分布（i.i.d.）随机变量1X,2XChapter3渐近等分割（AsymptoticEquipartitionAEP（2讲下1nn大数定理指出：对于独立同分布（i.i.d.）随机变量1X,2XXiAEP指出：对于独立同分布（i.i.d.）随机变量X1X2,，当n足够大时11HXpXXX n p(X,X,) nn足够大时，所有序列分为两类，一类序列发生的概率约为2nH的总概率接近于1，这些序列称为典型序列，其构成的集合称为典型集。另外一类序列构成)2n(H)}Pr{(x,x,x):p(x n n定义（随机变量的收敛）给定一个随机变量序列X1,X2量，1．以概率收敛，若对于每个0Pr{Xn}2．以均方收敛，若E( X03．1收敛（也称为almostsurely，若Pr{limXnX3．1渐近等分割性3.1.1（AEP）若X1,X2i.i.d.~p(x1logp(X,(证明：由弱大数定理：若Z1Z2,X),，即Zn是i.i.d随机变量序列，其均值为nZi（以概率收敛1n1logp(1log ,X ,X)12nnnp(Xii1H(XEp(X即：对于每个0Pr{1logpXX,X)}0(（typicalset）关于p1logp(1log ,X ,X)12nnnp(Xii1H(XEp(X即：对于每个0Pr{1logpXX,X)}0(（typicalset）关于p(x)的典型集是由满足下列条件的序列)2n(H(X)2n(H(X))p(x,(x,x,,, n n2nH()注意：表明典型集中每个序列发生的概率约1nHX)1(xx,logp(x n }2n(H(X)(1)2n(H(X)集中约包含2nHX)典型序列，因此表示一个典型序列可用nH(X）比特表1}，注意大写2Pr{Alogp(X,X,X)12nn3.1.1对于任意的0Pr{1logp(X,X,X)1,可取 nn }3由1p(x2n(H(X))2n(H(X)p(x)xxA(nxA(n2nHX)，Pr{A(n)}2n(H(X))2n(H(X) }xA(n（其中每个序列的概率小于等于2n(HX)1)2nHX)4，Pr{A(n)}2n(H(X))2n(H(X) }xA(n（其中每个序列的概率小于等于2n(HX)1)2nHX)4所以当n足够大n足够小型序列的个数约为2n(HX))而全体序列的个数2n(H(X 2n(H(Xn(logH(X则211例：若p(X0) ,p(X1) ，对于 ,n18，序列000110010011000110333．2AEP2n(H(X)如图3.1和3.2所示，一种编码方法：由于，对于典型序列用n(HX10，即用n(HX2c1个比特描述，前面再加一个前缀0，即A于nlog2比特描述3.2.1Xni.i.d.~p(x。令0nxn编码为二进制串，令l(xn)表示对应于序 的码字的长度。对于n足够大，E1l(Xn)H(X)El(Xn)p(xn)l(xn)p(xn)l(xn)p(xn)l(xnxnA(nn(nxp(xn)(n(H)2)p(xn)(nxnA(nn(nx }(n(H)2) }(nc22(an