漸近等分割特性aep 2講下信源2chapter 3

Chapter3漸近等分割（AsymptoticEquipartitionAEP（2講下1nn大數(shù)定理指出：對(duì)于獨(dú)立同分布（i.i.d.）隨機(jī)變量1X,2XChapter3漸近等分割（AsymptoticEquipartitionAEP（2講下1nn大數(shù)定理指出：對(duì)于獨(dú)立同分布（i.i.d.）隨機(jī)變量1X,2XXiAEP指出：對(duì)于獨(dú)立同分布（i.i.d.）隨機(jī)變量X1X2,，當(dāng)n足夠大時(shí)11HXpXXX n p(X,X,) nn足夠大時(shí)，所有序列分為兩類，一類序列發(fā)生的概率約為2nH的總概率接近于1，這些序列稱為典型序列，其構(gòu)成的集合稱為典型集。另外一類序列構(gòu)成)2n(H)}Pr{(x,x,x):p(x n n定義（隨機(jī)變量的收斂）給定一個(gè)隨機(jī)變量序列X1,X2量，1．以概率收斂，若對(duì)于每個(gè)0Pr{Xn}2．以均方收斂，若E( X03．1收斂（也稱為almostsurely，若Pr{limXnX3．1漸近等分割性3.1.1（AEP）若X1,X2i.i.d.~p(x1logp(X,(證明：由弱大數(shù)定理：若Z1Z2,X),，即Zn是i.i.d隨機(jī)變量序列，其均值為nZi（以概率收斂1n1logp(1log ,X ,X)12nnnp(Xii1H(XEp(X即：對(duì)于每個(gè)0Pr{1logpXX,X)}0(（typicalset）關(guān)于p1logp(1log ,X ,X)12nnnp(Xii1H(XEp(X即：對(duì)于每個(gè)0Pr{1logpXX,X)}0(（typicalset）關(guān)于p(x)的典型集是由滿足下列條件的序列)2n(H(X)2n(H(X))p(x,(x,x,,, n n2nH()注意：表明典型集中每個(gè)序列發(fā)生的概率約1nHX)1(xx,logp(x n }2n(H(X)(1)2n(H(X)集中約包含2nHX)典型序列，因此表示一個(gè)典型序列可用nH(X）比特表1}，注意大寫2Pr{Alogp(X,X,X)12nn3.1.1對(duì)于任意的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（其中每個(gè)序列的概率小于等于2n(HX)1)2nHX)4，Pr{A(n)}2n(H(X))2n(H(X) }xA(n（其中每個(gè)序列的概率小于等于2n(HX)1)2nHX)4所以當(dāng)n足夠大n足夠小型序列的個(gè)數(shù)約為2n(HX))而全體序列的個(gè)數(shù)2n(H(X 2n(H(Xn(logH(X則211例：若p(X0) ,p(X1) ，對(duì)于 ,n18，序列000110010011000110333．2AEP2n(H(X)如圖3.1和3.2所示，一種編碼方法：由于，對(duì)于典型序列用n(HX10，即用n(HX2c1個(gè)比特描述，前面再加一個(gè)前綴0，即A于nlog2比特描述3.2.1Xni.i.d.~p(x。令0nxn編碼為二進(jìn)制串，令l(xn)表示對(duì)應(yīng)于序 的碼字的長(zhǎng)度。對(duì)于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