强典型性 | Codeboy's Blog

形式陈述

设 $X$ 取值于有限字母表 $\mathcal X$ ，分布为 $P_X$ 。对序列 $x^n\in\mathcal X^n$ ，令

N(a\mid x^n)=|\{i:x_i=a\}|, \qquad \widehat P_{x^n}(a)=\frac{N(a\mid x^n)}n.

一种常见的 $\varepsilon$ -强典型集定义为

A_{\varepsilon,s}^{(n)} = \left\{ x^n: \begin{array}{l} |\widehat P_{x^n}(a)-P_X(a)|\le \varepsilon P_X(a) \quad\text{对所有 }P_X(a)>0,\\[2mm] N(a\mid x^n)=0 \quad\text{对所有 }P_X(a)=0 \end{array} \right\}.

也有教材使用绝对误差 $|\widehat P-P|\le\varepsilon$ ；采用哪一版必须连同常数界一起说明。

对IID 样本，有限字母表上的大数定律给出

P_X^n(A_{\varepsilon,s}^{(n)})\to1.

对足够小的频率误差，经验熵与真实熵以及单位自信息彼此接近，因此强典型性推出适当参数下的弱典型性。

直觉

强典型性逐个检查每个符号出现得是否“比例正确”。它不仅关心整串概率，还保留经验分布，因此特别适合条件典型性、联合典型性和类型计数。

弱典型性只检查平均自信息。一个标量约束可能无法恢复整个频率向量；强典型性则直接约束这个向量。两者在许多非退化有限源上给出相近的渐近规模，却不是同一个集合。

例子与边界

对 Bernoulli $(p)$ ，强典型性要求 1 的比例接近 $p$ 。若 $p=1/2$ ，全零串不是强典型的；但公平源中每个长度 $n$ 串的概率都是 $2^{-n}$ ，所以在弱自信息定义下所有字符串都弱典型。这是“弱典型不推出强典型”的直接反例。

若某符号概率为零，强典型序列不能出现该符号。无限或连续字母表上逐符号频率定义不再直接适用，通常改用弱典型性、信息密度或量化分区。

推论与应用

每个符号的经验频率几乎必然收敛到真实概率，来自强大数定律；对有限字母表取有限交，得到样本最终落入强典型集。

强典型集的类型计数界支撑联合典型性引理、条件典型性、method of types 与离散无记忆信道的随机编码证明。经验分布还能把交叉熵、KL 散度和序列概率写成类型的函数。

弱典型集按单位自信息定义；两页必须分开引用。只需要 AEP 和有效序列数时弱典型性常更一般；需要逐符号频率与联合类型时强典型性更直接。

参考资料

Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006, Chapters 2 and 11.
Imre Csiszár and János Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd ed., Cambridge University Press, 2011, Chapter 2.
Abbas El Gamal and Young-Han Kim, Network Information Theory, Cambridge University Press, 2011, Appendix 2A.