弱典型集 | Codeboy's Blog

形式陈述

本页只讨论弱典型集。设 $X_1,\ldots,X_n$ 是有限或可数字母表上的 IID 离散源，单字母熵 $H(X)<\infty$ ，并以 $2$ 为对数底。对 $\varepsilon>0$ ，定义长度 $n$ 的序列集合

A_{\varepsilon,w}^{(n)} =\left\{x^n: \left|-\frac1n\log_2P_X^n(x^n)-H(X)\right|<\varepsilon \right\}.

AEP给出概率集中：

P_X^n\!\left(A_{\varepsilon,w}^{(n)}\right)\longrightarrow1.

定义本身还给每条弱典型序列的概率夹逼

2^{-n(H(X)+\varepsilon)} <P_X^n(x^n) <2^{-n(H(X)-\varepsilon)}.

因此

|A_{\varepsilon,w}^{(n)}| \le2^{n(H(X)+\varepsilon)}.

若典型集概率至少为 $1-\delta$ ，则反向有

|A_{\varepsilon,w}^{(n)}| \ge(1-\delta)2^{n(H(X)-\varepsilon)}.

固定 $\varepsilon$ 后让 $n\to\infty$ ，再让 $\varepsilon\downarrow0$ ，才得到基数指数率 $H(X)$ ；有限 $n$ 下不能把两个不等式写成精确等号。

直觉

弱典型集把大多数概率质量收集到一批单串概率处于同一指数尺度的长序列中。若每串大约占 $2^{-nH}$ 的概率、这些串合计又接近概率一，那么所需串数自然约为 $2^{nH}$ 。这是一条“质量 × 单项大小 = 项数”的计数机制。

弱典型只检查单位自信息这一个标量，不按定义检查整个经验分布。需要逐符号频率、联合类型或条件类型时，应明确使用强典型性。

AEP 直接证明典型集概率趋一。对典型集内的单串概率下界求和并使用总概率至多为一，得到基数上界；用单串概率上界去承载至少 $1-\delta$ 的总质量，得到基数下界。两步都保留 $\varepsilon$ 与 $\delta$ ，所以不产生有限块长的自动保证。

例子与边界

取 Bernoulli $(1/4)$ 源。若 $x^n$ 含 1 的比例为 $\widehat p$ ，则

-\frac1n\log_2P(x^n)-h_2(1/4) =(\widehat p-1/4)\log_2 3.

令 $n=100$ 、 $\varepsilon=0.08$ 。因为 $0.05\log_2 3\approx0.07925<0.08$ ，弱典型集恰包含 1 的个数 $k=20,21,\ldots,30$ 的序列。其概率和与基数可直接复算为

\sum_{k=20}^{30}\binom{100}{k} \left(\frac14\right)^k\left(\frac34\right)^{100-k} \approx0.79668,

\sum_{k=20}^{30}\binom{100}{k} =49\,755\,999\,860\,134\,509\,157\,976\,634, \qquad \log_2|A_{0.08,w}^{(100)}|\approx85.36.

同一频率窗口在 $n=1000$ 时概率约为 $0.999772$ ，而 $\log_2|A|\approx876.91$ ；这些数落在 $n(H\pm\varepsilon)$ 的理论指数夹逼内。它们展示的是随块长发生的质量集中和指数规模，而不是把一组数字简单替换进定义。

公平比特源的每条长度 $n$ 字符串都恰有概率 $2^{-n}$ 、单位自信息 $1=H(X)$ 。所以对任意 $\varepsilon>0$ ，包括全零串在内的所有字符串都弱典型；全零串的经验频率却远离 $(1/2,1/2)$ ，不是强典型串。

连续源的单点概率为零，不能继续用离散典型串的基数计数；密度版本改以区域体积与微分熵描述。非 IID 源则需要相应的平稳遍历或信息稳定性假设，不能只代入单字母熵。

推论与应用

弱典型集给无失真固定率源编码一个直接构造：为典型块编号，非典型块宣告错误；当速率 $R>H(X)$ 时，足够大的块长可容纳典型集且错误概率趋零。逆向计数说明显著少于 $2^{nH}$ 个索引无法覆盖趋近一的概率质量。

信道编码常需要联合或条件典型性。若证明依赖逐符号类型，必须切换到强典型性；若使用一般字母表或有限块长，则通常改用信息密度和非渐近界。基本典型集定理本身不承诺具体 $n$ 、时延、复杂度或错误概率。

参考资料

Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006, Chapters 3 and 11.
Robert M. Gray, Entropy and Information Theory, 2nd ed., Springer, 2011, Chapters 3–4.
Abbas El Gamal and Young-Han Kim, Network Information Theory, Cambridge University Press, 2011, Appendix 2A.