渐近均分性（AEP）

前两章定义了熵 $H(X)$，它刻画的是一个符号平均有多少信息。但真正压缩或传输的对象通常不是单个符号，而是长度为 $n$ 的序列 $X^n=(X_1,\dots,X_n)$。于是一个更现实的问题出现了：

AEP 给出的答案非常漂亮：对于 i.i.d. 信源，绝大多数概率质量会集中在一个大小约为 $2^{nH(X)}$ 的集合上，这个集合就叫典型集。典型集中的每个序列概率都差不多，约为 $2^{-nH(X)}$。

这件事之所以重要，是因为它把抽象的熵 $H(X)$ 变成了一个极其具体的计数量：

这正是数据压缩能做到每个符号大约 $H(X)$ 比特的根源。

AEP 是一个极限定理，读它之前先分清几种常见收敛方式。设随机变量序列 $\{X_n\}$ 收敛到 $X$。

它们之间有一些包含关系：

• 几乎处处收敛 $\Rightarrow$ 依概率收敛
• 均方收敛 $\Rightarrow$ 依概率收敛

本章课件使用的 AEP 表述首先是依概率收敛。对 i.i.d. 情形，借助强大数定律也可得到更强的几乎处处收敛版本。

为什么需要它

如果你只知道单个符号的熵 $H(X)$，还不知道一个长序列的概率结构。要做压缩，我们需要知道大多数序列的概率大概落在什么量级。AEP 就是在回答这个问题。

它是什么

设 $X_1,X_2,\dots,X_n$ 为独立同分布随机变量，且都服从分布 $p(x)$。则

常把 $X^n=(X_1,\dots,X_n)$ 写成向量形式，则上式可写成

这句话可以直接翻译成中文：

• $-\log p(X^n)$ 是整段序列的自信息
• 除以 $n$ 以后，是每个符号平均贡献的信息量
• 当 $n$ 很大时，它会逼近熵 $H(X)$

证明思路：三步走

AEP 的证明极其简洁，只需三步，每一步都是概率论的基本操作：

怎么用

• 构造典型集
• 估计长序列概率的量级
• 给信源编码定理提供核心直觉和证明骨架

一句直觉

长序列看上去组合数爆炸，但从概率角度看，绝大多数"真正会发生"的序列，其每符号信息量都差不多，基本就是熵。

由 AEP，若某个观测到的序列 $X^n$ 是"典型的"，就有

把两边乘以 $-n$ 并取 2 为底的指数，可得到

更严格地说，对任意 $\epsilon>0$，当 $n$ 足够大时，以高概率有

等价于

这一步非常关键，因为它把"熵"转化成了"长序列概率"的数量级描述。

例子落地

若 $X\sim\mathrm{Bernoulli}(1/2)$，则 $H(X)=1$ bit，因此典型长度为 $n$ 的序列每个的概率大约是

这和真正均匀二进制序列的情况完全一致，因为所有序列本来就等概率。

若 $X\sim\mathrm{Bernoulli}(0.9)$，则 $H(X)=H_2(0.9)\approx 0.469$ bit。于是典型序列个数大约是 $2^{0.469n}$，远小于全部 $2^n$ 个二进制序列。

为什么需要它

仅知道"高概率事件存在"还不够，我们希望把这些序列组织成一个集合，用它做编码、证明和计数，这就得到典型集。

它是什么

关于分布 $p(x)$ 的 $\epsilon$-典型集定义为

等价地，$x^n\in A_\epsilon^{(n)}$ 当且仅当

这里：

• $x^n=(x_1,\dots,x_n)$ 表示一个确定的长度为 $n$ 的序列
• $\mathcal X^n$ 表示所有可能长度为 $n$ 的序列集合
• $\epsilon$ 控制"离熵多近才算典型"

典型集的三个核心性质（逐条证明）

直观理解

全部可能序列有 $|\mathcal X|^n$ 个，而典型集只有大约 $2^{nH(X)}$ 个。由于 $H(X)\le \log|\mathcal X|$，当分布不是均匀时，典型集只占指数级很小的一部分。可偏偏就是这小部分，承载了几乎全部概率质量。

为什么压缩和典型集直接相关

压缩的本质是给高概率对象更短的描述。AEP 说明高概率对象几乎都落在典型集中，而典型集大小约为 $2^{nH(X)}$，所以只需大约 $nH(X)$ bit 就能标号这些序列。

课件中的推论

设 $X^n$ 为服从 $p(x)$ 的 i.i.d. 序列。对任意 $\epsilon>0$，存在一个 1 对 1 编码，使得对充分大的 $n$，平均码长满足

其中 $\ell(X^n)$ 表示序列 $X^n$ 对应的码字长度。

证明思路拆开看

1. 典型集大小至多为 $2^{n(H(X)+\epsilon)}$
2. 因此每个典型序列最多用 $n(H(X)+\epsilon)$ 个 bit 就能编号
3. 非典型序列可以用更长方式单独编码
4. 但非典型序列出现概率很小（$<\epsilon$），因此不会显著拖高平均码长

所以平均每个符号所需比特数可以压到任意接近 $H(X)$。

下面用一枚硬币（正面概率 $p=0.3$）来演示 AEP 的收敛过程。拖动滑块改变序列长度 $n$，观察每符号自信息 $-\frac1n\log p(x^n)$ 如何逼近真实熵 $H(X)\approx 0.881$。

模拟方法：生成长度为 $n$ 的独立样本序列，计算其经验每符号自信息。红色虚线为熵的真实值，蓝色点为当前 $n$ 下的模拟值。

观察可见，当 $n$ 增大时，蓝色点逐步向红色虚线（真实熵 $H(X)\approx 0.881$）靠拢，波动越来越小。这正是大数定律在信息论中的体现。

• 第 5 章数据压缩：典型集告诉我们为什么压缩率极限是 $H(X)$
• 第 7 章信道容量：AEP 的思想会升级成联合典型集，用于证明信道编码定理
• 第 4 章熵率：若信源不再 i.i.d.，单符号熵要换成更一般的熵率

AEP 的真正力量就在这里：它把"概率论中的大数定律"翻译成了"信息论中的长序列结构定律"。