信息论进阶 I · AEP、有限码本与熵率

1. AEP：对什么随机变量使用大数定律

设 \(X_1,X_2,\ldots\) 独立同分布，取值于有限字母表 \(\mathcal X\)，分布为 \(p\)。只在正概率的支持上定义自信息

因为独立性给出乘积概率，

这就是 IID 情形的渐近均分性（AEP）。几乎必然收敛也推出依概率收敛。本课主要使用后者：任意固定 \(\varepsilon>0\)，

有限字母表使自信息在正概率支持上可积。推广到可数离散字母表时，需要明确 \(H(X)\lt \infty\)；不能把“取离散值”当成有限熵。零概率字母不会被该信源抽到，不把 \(0\log0\) 当作未处理的数值异常。

定理没有指定统一的有限长度。“取足够大的 \(n\)”依赖信源和带宽。它也没有说长序列的概率相差一个固定常数倍。

2. 典型集：质量界与数量界是两步

定义弱典型集

每个成员满足

令 \(\delta_n=P(A_{n,\varepsilon}^{c})\)。对集合内概率求和，分别使用下界与上界，得到

所以

这是有限 \(n\) 的界；AEP 另外保证固定正带宽下 \(\delta_n\to0\)。当集合为空时，下界只能是零，不能对它取有限对数。

“均分”应读成每符号对数概率靠近同一个值。同在带内的两条序列，概率比仍可能达到

这个允许范围会随 \(n\) 指数增长。固定 \(\varepsilon\) 的数量界，只把 \(n^{-1}\log_2|A|\) 夹在 \(H\pm\varepsilon\) 附近；不能从这两条界直接宣称其极限恰好是 \(H\)。要得到精确指数，需要在正确次序下令带宽趋零，或另行选择满足尾概率趋零的带宽序列。

公平硬币是必要的检查点：每条序列概率都为 \(2^{-n}\)，自信息率恒等于 1。即使 \(\varepsilon=0\)，典型集也是全部 \(2^n\) 条序列。典型不一定稀疏。

3. 二项类型：把有限样本完整算出来

若一条二元序列有 \(k\) 个 1，则

令 \(q=k/n\)。当 \(0\lt p\lt 1\)，每符号自信息与熵的差有一个特别清楚的表达式：

对 \(p=0.9,n=100,\varepsilon=0.1\)，典型条件等价于

因此恰好选择 \(k=87,\ldots,93\)。把这七个类型完整相加：

与此同时 \(100H_2(0.9)\approx46.8995593589\)。三个数字没有矛盾：46.90 是熵的中心尺度，52.89 是这个有限带的数量对数，75.90% 是它实际覆盖的概率。用 53 比特给带内成员编号，也只保证恢复这些成员。

全 1 序列的每符号自信息是 \(-\log_2 0.9\approx0.152003093445\)，低于本带下界，所以冠军不在带内。扩大带宽超过 \(H_2(0.9)+\log_2 0.9\) 后，冠军就进入了。不能把“冠军永不典型”写成无条件结论。

4. 有限长度：带宽越窄，等待可能越久

对 Bernoulli 信源，自信息的方差可以直接由两点分布算出：

独立性使 \(\operatorname{Var}(Z_n)=V/n\)。当 \(\varepsilon>0\)，Chebyshev 不等式给出

右边可能超过 1，这时界没有提供有用的压缩保证；实验显示原始右端，不把它伪装成精确尾概率。完整二项求和通常更有信息。若 \(\varepsilon=0\)，不能除以它；公平硬币和确定性信源的零方差例外可以直接算。

选择 \(\varepsilon_n=n^{-1/4}\) 时，

于是非空典型集的数量对数满足

从而趋向 \(H\)。这里同时控制了带宽和尾部，不是把固定带宽的结论偷换为零带宽。

弱典型与经验频率典型要分清。弱典型只约束一个对数平均；强典型通常约束各字母的经验频率。偏置二元信源的上式把二者联系起来，但公平二元信源的弱典型条件根本不限制频率。在更大字母表中，一个线性约束也不能代替所有频率约束。

5. 固定码长：最优字典不必是典型集

固定长度编码器与解码器是两个确定映射

本课允许解码错误，并以整块为单位计数：

能被正确恢复的集合 \(B=\{x^n:g(f(x^n))=x^n\}\) 至多含 \(2^\ell\) 个成员。否则两个可恢复成员共享同一码字，解码器无法同时输出两个不同答案。

反过来，任取至多 \(2^\ell\) 个成员，用不同码字编号；把其余序列映到已有某个码字，即可正确恢复这个集合。因此，设各条序列的概率降序排列为 \(p_{(1)},p_{(2)},\ldots\)，则

这解释了实验的算法：按单条概率排序类型，逐类分配码字；最后一类可能只能容纳其中一部分。并列时任选相同数量的序列，覆盖概率相同。字典构造只证明存在，不代表存储这个巨大字典很便宜。

对 \(p=0.9,n=100,\ell=47\)，完整类型排序给出最优覆盖率约 \(0.685843914944\)，故即使最优固定码本也有约 \(31.42\%\) 的块错误。不能用 \(47\approx nH\) 推出有限长度几乎无误。

另一个编码约定会少一个码字。若要求所有失败都必须被检测，并专门输出擦除符号，通常要预留一个码字，此时字典容量为 \(2^\ell-1\)。本实验使用上面允许不可检测错误的定义。两种定义不能混用；参见 Polyanskiy–Wu 书稿第 11.1 节、Remark 11.1。

6. 信源编码定理：可达与逆向都保留尾项

设 IID 有限字母表信源熵为 \(H\)。固定 \(R>H\)，选 \(\varepsilon>0\) 使 \(H+\varepsilon\lt R\)。用 \(\ell_n=\lceil nR\rceil\) 比特给典型集编号，因为

只在非典型集合上可能出错，所以 \(P_e\leq\delta_n\to0\)。这证明高于熵的固定码率可达到趋零块错误。

反过来，固定 \(R\lt H\)，取 \(0\lt \varepsilon\lt H-R\)。任意 \(\ell_n=\lfloor nR\rfloor\) 比特码本的可恢复集合 \(B_n\) 满足

因此块错误率趋向 1。非典型尾部不能丢掉；它也可能属于可恢复字典。定理在严格大于或小于 \(H\) 时给结论，边界 \(R=H\) 需要更细分析。

“趋零错误”与“每条正概率序列都绝不出错”是不同要求。满支持二元信源有 \(2^n\) 条可能序列，所以严格零错误固定长度至少需要 \(n\) 比特。可变长度前缀编码则是另一个问题：对一个有限分布可做到

（退化单点支持允许空码字时另行直接处理）。这属于平均长度保证，不能用来声称每条消息都只有 \(nH+1\) 比特。

7. 有记忆信源：先定义熵率，再谈典型路径

设过程平稳且取有限字母表，令

条件越多，条件熵不增；再用平稳性移位，

所以 \(a_m\downarrow h\geq0\)。熵的链式法则与 Cesàro 平均给出

这个 \(h\) 是熵率。以上只需平稳和有限字母表，不需要遍历。推广到可数情形时，要明确至少 \(H(X_1)\lt \infty\) 等适用条件。

但 \(H(X_1^n)/n\) 是期望的归一化量，尚未说明随机的 \(-n^{-1}\log P(X_1^n)\) 是否集中到它。后一结论需要额外条件。有限字母表的 Shannon–McMillan–Breiman 定理说：若过程平稳且遍历，则

遍历的意思是移位不变事件只有概率 0 或 1。它不是“看起来随机”或“相关性每一步都消失”的同义词。SMB 的一般证明比 IID 大数定律更深；本课下面给出 Markov 情形的证明路线和缺少遍历性的反例，不把短路径枚举当成一般证明。可参阅 Polyanskiy–Wu 第 12.2–12.3 节。

8. Markov 熵率：周期链也能每符号零信息

本节使用行随机转移矩阵

分布写成行向量，更新为 \(\mu_{t+1}=\mu_tQ\)。上一讲用列向量时对应矩阵为 \(Q^{\mathsf T}\)，箭头意义不变。

当 \(a+b>0\)，唯一平稳分布为

若 \(a=b=0\)，每个状态吸收，任意初始分布都平稳，不能除以零或声称唯一。平稳起始时，由 Markov 性，

例如 \(a=0.1,b=0.2\)，有 \(\pi=(2/3,1/3)\)、\(h\approx0.553306427355\)；\(n=8\) 时整块熵约 \(4.79144082554\) 比特。指定非平稳初始分布后，实验用每时刻实际分布求条件熵，不套这个平稳起始的等式。

平稳不可约有限链的路径概率可分解为

首项趋零，转移频率的遍历平均使第二项趋向 \(-\sum_{ij}\pi_iQ_{ij}\log_2Q_{ij}\)。这里允许周期链；零概率转移不出现在实际路径上。

取 \(a=b=1\)，从平稳分布 \((1/2,1/2)\) 出发，只有两条交替路径，每条概率 \(1/2\)。所有 \(n\) 都有 \(H(X_1^n)=1\)，因此 \(h=0\)。知道第一位后，后面完全确定。这一平稳过程在移位意义下遍历，却不混合：偶数步总返回原状态，相关性不会随间隔消失。它与上一讲“周期阻止分布混合”的结论完全相容。

9. 平稳但不遍历：一次选信源，与每步选信源

先抛一次隐变量 \(Z\)，以概率 \(w\) 选择 Bernoulli\((p_A)\)，否则选择 Bernoulli\((p_B)\)，然后整条无限序列都使用选定的硬币。混合仍然平稳，其长度 \(n\) 概率是

条件于 \(Z\) 后有 IID 结构，所以

互信息恒等式给出

从而熵率确实是 \(\bar h\)。然而当 \(0\lt w\lt 1\)、两个参数不同，长期频率能区分所选信源；这个区分事件在移位下不变且有非平凡概率，因此过程不遍历。

若两个分量的熵不同，随机自信息率分别趋向 \(H_2(p_A)\) 或 \(H_2(p_B)\)，不必趋向中间的平均值。直观上，选了 A 的样本最终具有 A 的频率，另一分量对该典型路径的似然相对指数变小；常数混合权重贡献的 \(-\log_2w/n\) 趋零。端点的一个直接计算见第 11 节。

实验默认 \(p_A=0.1,p_B=0.5,w=0.5\)。平均熵率约 \(0.734497796795\)，但两个分量中心约为 0.469 与 1。长度 100 时，平均值左右 0.1 的带仅覆盖约 \(3.61\%\)；不能用“平稳所以 AEP”预测它趋近 100%。

如果每一步重新独立选择隐变量，则观测变成 IID Bernoulli\((wp_A+(1-w)p_B)\)，熵率改为

这是不同的实验。还应注意：非遍历不必导致随机信息率有多个不同数值，例如 \(p_B=1-p_A\) 时两个分量的熵相同。缺少条件意味着不能直接套定理，不意味着结论必然失败。

10. 交叉熵与压缩：期望恒等式不认证一条文本

真实长度 \(n\) 分布为 \(P\)，概率模型为 \(Q\)。若 \(P\) 的支持包含在 \(Q\) 的支持中，则

所以期望交叉熵至少是真实块熵。如果某条正概率路径被模型赋予零概率，交叉熵和 KL 都为正无穷；实验明确显示该支持缺口。它不把无穷作为零值跳过。

对单条观察 \(x^n\)，经验损失 \(-n^{-1}\log_2Q(x^n)\) 可能低于真实熵率，也可能高于它。即使 \(Q=P\)，抽到高概率序列仍会得到偏低的单次损失。把模型变大、训练更久，不自动证明在新数据上更接近真实分布。

在自回归模型中，

以比特/token 计的平均损失 \(L\) 对应困惑度 \(2^L\)；以 nat/token 计时则是 \(e^L\)。不同 tokenizer 的每 token 单位不同，不能直接按困惑度排名。比较字节效率，应使用相同原始文本、可逆编码约定，并核对总比特数除以原始字节数。

概率损失也不是已经生成的压缩文件大小：解码端是否共享模型、词表和上下文？是否计入首部、结束标记与编码器有限精度？真实文件还需把这些成本说清楚。可以比较同一小文件的原始字节数、实际压缩字节数和模型总损失，但这项有限文件实验不能证明自然语言的真实熵率。

Shannon 1951 年关于约一比特/字母的讨论，针对特定英语字母与空格约定、文学英语及人类长程预测实验，不是跨语言或现代 token 的通用常数。阅读原始实验语境：Prediction and Entropy of Printed English。

11. 四道完整练习：先算有限对象，再使用定理

练习一：典型集为空，最优一码长仍有意义吗？

取 \(n=2,p=3/4,\varepsilon=0.1\)。求三个类型的单序列概率、自信息率；再求 \(\ell=1\) 的最优固定长度覆盖率。

练习二：把渐近尺度拆成三个数字

对 \(p=0.9,n=100,\varepsilon=0.1\)，求典型类型区间；解释典型质量、典型基数对数和 \(nH\) 为什么不能互换。

练习三：每一位都公平，为什么熵率为零？

令 \(X_1\) 是公平二元变量，之后总取 \(X_{t+1}=1-X_t\)。求边际熵、块熵、熵率，并判断平稳、遍历与混合。

练习四：平均熵率存在，样本却不朝平均值集中

以各 \(1/2\) 概率，开始时选择“永远输出 0”或“独立公平硬币”。选择后不再更换。求熵率和两类路径的自信息率极限。

12. 通向后续课程：把概率模型与编码约束一起带走

AEP 提供的是把高概率事件组织成可计数集合的方法。联合与条件典型集会把它推广到有边信息、信道和多用户问题；信息谱方法则直接研究归一化对数似然的分布，在缺少 IID 或遍历假设时保留可能的多个极限尺度。本课的混合信源已经说明为什么需要这种推广。

有限块长问题还需要误差目标、码长取整以及信息方差等更细数据。本课的完整二项排序给出一个可复核的起点，不能据此声称已经实现一般信源最优编码器。Markov 枚举仅覆盖二态、短路径模型；它验证链式法则和概率账本，不替代一般遍历理论。

读一个压缩或语言建模结果时，依次写下：随机对象是什么、概率模型是什么、单位是什么、允许什么错误、有限成本如何计入。这五件事确定以后，再决定应使用熵、熵率、交叉熵，还是实际文件长度。

补充阅读：Stanford Data Compression 的 AEP 讲义 提供 IID 典型集与近乎无损压缩的入门视角；本页保留其有限带宽和有限错误项，并用完整类型与路径实验补足具体数值。