信息论与编码：弱典型性与强典型性

1、1.Weak AEP考虑信源leftX_k:kge 1right，其中X_k独同分布，服从，X表般性的变量，即任何的X_k都与X同分布。Weak AEP ：displaystyle -frac1nlog 依概率收敛于H(X)，即对于任意epsilon ，对于够的n，textPrleft(left|-frac1nlog p(boldsymbolX) - H(X)right| le epsilonright) 1 - epsilon由弱数定律可证。弱典型集（weakly typical set）：关于概率分布的弱典型集W_Xepsilonn是由所有满：left|-frac1nlog p(bolds

2、ymbolx) - H(X)right| le epsilon的序列boldsymbolx构成的集合，其中boldsymbolx = (x_1, cdots, x_n)。displaystyle -frac1nlog p(boldsymbolx) = -frac1nsum_k=1nlog p(x_k) 作序列boldsymbolx的经验熵（empiricalentropy）。Weak AEP ：对于任意的epsilon ：1. 若boldsymbolx in W_Xepsilonn，则2-n(H(X)+epsilon) le p(boldsymbolx) le 2-n(H(X)-epsilon

3、)2. 对于够的n，textPrleftboldsymbolX in W_Xepsilonnright 1 - epsilon3. 对于够的n，(1 - epsilon)2n(H(X)-epsilon) le left|W_Xepsilonnright| le 2n(H(X)+epsilon)性质1由弱典型集的定义可得，性质2由Weak AEP 可得，性质3通过将性质1乘上left|W_Xepsilonnright|得到left|W_Xepsilonnright|2-n(H(X)+epsilon) le textPrleftboldsymbolX in W_Xepsilonnright lel

4、eft|W_Xepsilonnright|2-n(H(X)-epsilon)，结合性质2可得。弱典型性的解释：随机变量X服从分布，独地由得到序列boldsymbolX = (X_1, cdots, X_n)，boldsymbolX的概率接近2-nH(X)（即boldsymbolX属于弱典型集）的可能性常，且弱典型集的常接近2nH(X)。fracleft|W_Xepsilonnright|left|mathcalXright|n approx frac2nH(X)2nlog left|mathcalXright|=2n(H(X) - logleft|mathcalXright|)若H(X) lo

5、g left|mathcalXright|，则n rightarrow infty时，上式趋于0。也就是说，只要H(X) ，存在种编码案，使得对于够的n，left|R - H(X)right| epsilon，P_e ，找到满displaystyle delta + frac12log frac11 - delta =epsilon的delta，令mathcalA = W_Xdeltan即可。2. Converse Part若某种编码案满R ，则当n够时，错误概率P_e收敛到1。证明：令0 epsilon xi，构造W_Xepsilonn，W_Xepsilon表W_Xepsilonn的补集，则

6、对于够的n：beginalign* textPr(boldsymbolX in mathcalA) &= textPr(boldsymbolX in mathcalA cap W_Xepsilonn) + textPr(boldsymbolX in mathcalA cap W_Xepsilon) &le left|mathcalAright|timesmax_boldsymbolx inW_XepsilonntextPr(boldsymbolx)+textPr(boldsymbolX in W_Xepsilon) &le 2nRtimes2-n(H(X)-epsilon)+epsilon &

7、le 2n(epsilon - xi)+epsilon endalign*所以displaystyle lim_n rightarrow inftytextPr(boldsymbolX in mathcalA) le epsilon，从displaystyle lim_n rightarrowinftytextPr(boldsymbolX in mathcalA) = 03. Strong AEP强典型集（Strong Typical Set）：关于概率分布的强典型集T_Xdeltan是由所有满：sum_x in mathcalXleft|frac1nN(x;boldsymbolx)-p(x)

8、right| ，使得当delta rightarrow 时，eta rightarrow ，并且：1. 若boldsymbolx in T_Xdeltan，则2-n(H(X)+eta) le p(boldsymbolx) le 2-n(H(X)-eta)2. 对于够的n，textPr(boldsymbolX in T_Xdeltan) 1 - delta3. 对于够的n，(1 - delta)2n(H(X)-eta) le left|T_Xdeltanright| le 2n(H(X)+eta)证明：性质1：beginalign* log p(boldsymbolx) &= sum_xN(x;

9、boldsymbolx)log p(x) &= sum_xleft(N(x;boldsymbolx) - np(x)+np(x)right)logp(x) &= nleftsum_xleft(fracN(x;boldsymbolx)n - p(x)right)log p(x) +sum_xp(x)log p(x)right &= -nleftsum_xleft(fracN(x;boldsymbolx)n - p(x)right)left(-log p(x) right)+H(X)right endalign*由于beginalign* left|sum_xleft(fracN(x;boldsy

10、mbolx)n - p(x)right)left(-log p(x) right)right| &le sum_xleft|fracN(x;boldsymbolx)n - p(x)right|left(-log p(x) right) &le delta cdot max_x(-log p(x) &= eta endalign*其中displaystyle eta = delta cdot max_x(-log p(x) ，当delta rightarrow 时，eta rightarrow 。因此-n(H(X)+eta) le log p(x) le -n(H(X)-eta)从2-n(H(X

11、)+eta) le p(boldsymbolx) le 2-n(H(X)-eta)性质2：beginalign* textPr(boldsymbolX in T_Xdeltan) &=textPrleft(sum_xleft|fracN(x;boldsymbolx)n - p(x)right| le deltaright) &= 1 - textPrleft(sum_xleft|fracN(x;boldsymbolx)n - p(x)right| delta right) &ge 1 -textPrleft(left|fracN(x;boldsymbolx)n - p(x)right|frac

12、deltaleft|mathcalXright|text for some xright) & 1 - delta endalign*其中displaystyle textPrleft(left|fracN(x;boldsymbolx)n - p(x)right|fracdeltaleft|mathcalXright|text for some xright) ：textPrleft(left|frac1nsum_k=1nB_k(x) - p(x)right| fracdeltaleft|mathcalXright|right) fracdeltaleft|mathcalXright|text for some xright) = &textPrleft(left|frac1nsum_k=1nB_k(x) - p(x)right|fracdeltaleft|mathcalXright|text for some xright) = &textPrleft(bigcup_xleft|frac1nsum_k=1nB_k(x) - p(x)right|fracdeltaleft|mathcalXright|right) le &sum_xtextPrleft(left|frac