本页目录

信息论进阶 I · AEP 与典型集

对标：Cover & Thomas EIT §3、§4.1–4.3 ｜前置：本科信息论 I–III、mt-02 研究生信息论的第一件武器是 AEP（渐近均分性）：长序列的概率世界"塌缩"成一个几乎均匀的典型集。它是信息论一切编码定理的证明引擎——本科"熵 = 压缩极限"的口头支票，本页用典型集正式兑付，并推广到熵率（有记忆信源）。

1. AEP：大数定律的信息论化身

典型集大小 2^nH — 图 1.1渐近均分性（AEP）：长序列的概率几乎全压在 \(2^{nH}\) 个"典型序列"上（远少于全部 \(2^n\) 个）——信源编码的根。

定理（AEP） \(X_1, \dots, X_n\) i.i.d. \(\sim p\)：

\[ -\frac{1}{n}\log p(X_1, \dots, X_n) \;\xrightarrow{P}\; H(X) \]

【证明】 \(-\frac1n\log p(X^n) = \frac1n\sum_i\big[-\log p(X_i)\big]\)——i.i.d. 随机变量（均值恰为 \(H\)）的样本平均，弱大数定律（mt-02）一行。\(\blacksquare\)

读法：长序列的概率集中在 \(2^{-nH}\) 一个量级上——"发生的序列几乎都是等可能的"。由此定义：

典型集 \(A_\varepsilon^{(n)} = \big\{x^n: 2^{-n(H+\varepsilon)} \leq p(x^n) \leq 2^{-n(H-\varepsilon)}\big\}\)。

性质三条【证明】：① \(P(A_\varepsilon^{(n)}) \to 1\)（AEP 的直译）；② \(|A_\varepsilon^{(n)}| \leq 2^{n(H+\varepsilon)}\)（每个成员概率 \(\geq 2^{-n(H+\varepsilon)}\)、总概率 \(\leq 1\)——计数即除法）；③ \(|A_\varepsilon^{(n)}| \geq (1-\varepsilon)2^{n(H-\varepsilon)}\)（大 \(n\)；同法反向）。\(\blacksquare\)

世界观：\(|\mathcal{X}|^n\) 个可能序列中，只有 \(2^{nH}\) 个"实际会发生"（占比 \(2^{-n(\log|\mathcal{X}| - H)}\)——指数级稀疏），且它们近似等概率。"高维概率集中在薄壳上"（hdp-01 §3）的信息论平行版：大数世界的多样性由熵精确计价。

2. 信源编码定理（典型集版证明）

定理 i.i.d. 信源可以 \(n(H + \varepsilon)\) 比特/块无损编码（错误率 \(\to 0\)）；低于 \(H\) 则不可。 【证明】 （正向）只给典型集编号：性质②说 \(n(H+\varepsilon) + 1\) 比特够用；非典型序列任意处理——出错概率 \(\leq P((A_\varepsilon^{(n)})^c) \to 0\)（性质①）。（逆向）任何 \(2^{nR}\)（\(R < H\)）个码字的集合，与典型集的交集至多 \(2^{nR}\) 个成员、总概率 \(\leq 2^{nR}\cdot2^{-n(H-\varepsilon)} \to 0\)——可靠编码覆盖不住典型集。\(\blacksquare\) （对比本科信息论 I 的 Kraft/Shannon 码证明：那是逐符号的构造性路线（多付最多 1 比特/符号），本页是分块渐近路线——精确到 \(H\)、但只是存在性：两条路线互补，后者的"随机分块 + 典型性"手法是下一页信道定理的预演。）

3. 熵率：有记忆信源

真实信源（语言！）不独立。熵率：

\[ H(\mathcal{X}) = \lim_{n\to\infty}\frac{1}{n}H(X_1, \dots, X_n) = \lim_{n\to\infty} H(X_n \mid X_{n-1}, \dots, X_1) \]

【证明（两定义等价）】 条件熵序列 \(H(X_n\mid X^{n-1})\) 单调不增（信息不增，本科 I）且非负 ⇒ 有极限；链式法则把 \(\frac1nH(X^n)\) 写成其 Cesàro 平均——收敛列的 Cesàro 平均同极限（数分 I 的老引理）。\(\blacksquare\)

平稳遍历信源的 AEP（Shannon–McMillan–Breiman）【引用】：\(-\frac1n\log p(X^n) \to H(\mathcal{X})\) a.s.——AEP 推广到有记忆世界（证明需遍历定理，Durrett §7）。压缩极限 = 熵率照旧成立。

Markov 信源的熵率【证明】：平稳 Markov 链：\(H(\mathcal{X}) = H(X_2\mid X_1) = -\sum_i \pi_i\sum_j P_{ij}\log P_{ij}\)（条件熵定义式在平稳分布下取平均——随机过程线的 \(\pi\) 在此就业）。

🔗 LLM 对账：语言的熵率 ≈ 每字符 1 比特级（Shannon 的著名实验【引用】）；语言模型的交叉熵/困惑度就是对熵率的上界估计（本科信息论 III"压缩即智能"的研究生版语言）——模型越强、估计越贴近真实熵率；"LLM 压缩互联网"的理论天花板就是 SMB 定理里的那个 \(H(\mathcal{X})\)。

4. 练习与要点

例 1（典型集数感） 有偏硬币 \(p = 0.9\)，\(n = 100\)：\(H \approx 0.469\) ⇒ 典型集约 \(2^{47}\) 个序列——占全部 \(2^{100}\) 的 \(2^{-53}\)（十万亿亿分之一），却占概率的几乎全部；且最可能的单个序列（全 1）不在典型集里（\(-\frac1n\log p = 0.152 \neq H\)）——"最典型 ≠ 最可能"：典型集是"大数的众生相"，不是"冠军"。这个反直觉是 AEP 理解的试金石。

例 2（熵率计算） 二状态 Markov 链 \(P = \begin{pmatrix}0.9 & 0.1\\ 0.5 & 0.5\end{pmatrix}\)：\(\pi = (\frac56, \frac16)\)，\(H(\mathcal{X}) = \frac56 h(0.1) + \frac16 h(0.5) \approx 0.558\) 比特/步——对比独立同边缘的 \(H(\pi) \approx 0.65\)：记忆压低熵率（可预测性 = 可压缩性）。

例 3（SMB 的实践影子） 用 gzip 压缩自己一年的日报文本估计熵率：压缩比 ≈ 熵率/8 比特——粗糙但方向正确的"个人语言熵"测量；换用 LLM 的困惑度会得到更紧的上界（两代压缩器的代差可测）。\(\blacksquare\)

下一页：本科欠下最大的一张票——信道编码定理的证明：随机编码 + 联合典型性，Shannon 最惊人的论证。