第3章 典型序列（Typical Sequences）
一、导读
3.1 本章学习目标
通过本章的学习，你将能够：
理解典型序列的定义与性质：掌握典型集的概念，理解为什么典型序列在长序列中占据主导地位
掌握渐近等分性（AEP）定理：理解大数定律如何导致典型集的形成，掌握AEP的数学表述和证明
理解典型集的大小估计：掌握为什么典型集的大小约为 $2^{nH(X)}$，以及这个结果的深刻含义
掌握联合典型序列的概念：理解两个序列" jointly typical"的含义，这是信道编码定理的基础
能够应用典型性进行概率估计：理解为什么典型序列的概率近似为 $2^{-nH(X)}$
理解典型集与数据压缩的关系：掌握为什么只需要对典型序列编码就能实现高效压缩
掌握典型性检验的方法：能够设计算法判断一个序列是否属于典型集
理解弱典型性与强典型性的区别：了解两种典型性定义的差异及其适用场景
3.2 为什么本章如此重要
典型序列是信息论中最深刻也最美妙的概念之一。它架起了概率论与信息论之间的桥梁，是理解信源编码定理和信道编码定理的关键。
理论重要性：
渐近等分性（AEP）是大数定律在信息论中的体现。它告诉我们，当序列长度 $n$ 很大时，几乎所有可能的序列都属于一个相对很小的集合——典型集。这个集合的大小只有 $2^{nH(X)}$，而总的可能序列数是 $|\mathcal{X}|^n$。由于 $H(X) \leq \log |\mathcal{X}|$，典型集通常只占全部序列空间的极小部分。
这一发现是革命性的：它意味着我们不需要为所有可能的序列编码，只需要为典型序列编码即可。这正是数据压缩的理论基础。
实践重要性：
虽然实际的压缩算法（如LZ77、LZW）并不显式地使用典型序列的概念，但它们的性能极限由典型集的大小决定。理解典型性有助于我们理解为什么某些数据可以高度压缩（低熵，典型集小），而某些数据几乎不可压缩（高熵，典型集大）。
在网络信息论中，联合典型性是理解多用户通信的核心。接收端通过检查接收到的序列与哪个发送序列是联合典型的来解码消息，这种方法称为"联合典型性译码"。
方法论重要性：
典型性的论证方法（typicality argument）是信息论证明的标准技术。通过将序列空间划分为典型集和非典型集，我们可以忽略概率极小的非典型情况，从而简化分析。这种技术在信道编码定理、率失真理论、网络信息论的证明中反复出现。
3.3 核心问题引导
在学习本章之前，请思考以下问题：
抛硬币1000次，得到全正面的概率是多少？ 这个事件的概率极小，但它与得到"大约500次正面"的事件有什么本质区别？
为什么英文文本可以被压缩？ 从典型序列的角度看，这是因为大多数可能的字母序列都不是"典型的"英文文本。
如果我有 $n$ 个独立同分布的随机变量，它们的联合概率分布会有什么特性？ 当 $n$ 很大时，绝大多数概率质量会集中在哪些序列上？
典型集的大小与熵有什么关系？ 为什么典型集的大小约为 $2^{nH(X)}$ 而不是其他值？
"典型"是什么意思？ 一个序列要成为典型序列，需要满足什么条件？这个条件与概率还是频率有关？
联合典型性如何用于解码？ 在通信系统中，接收端如何利用联合典型性来判断发送的是哪个消息？
弱典型性和强典型性有什么区别？ 为什么在某些情况下需要更强的典型性定义？
典型序列的概念如何推广到连续随机变量？ 微分熵与典型集大小有什么关系？
二、核心概念详解
3.1 渐近等分性（AEP）
3.1.1 大数定律回顾
在引入典型序列之前，让我们回顾大数定律（Law of Large Numbers, LLN）。
弱大数定律：设 $X_1, X_2, \ldots$ 是独立同分布（i.i.d.）的随机变量，均值为 $\mu$。则对于任意 $\epsilon > 0$：
$$\lim_{n \to \infty} P\left(\left|\frac{1}{n}\sum_{i=1}^n X_i - \mu\right| > \epsilon\right) = 0$$
强大数定律：在相同条件下：
$$P\left(\lim_{n \to \infty} \frac{1}{n}\sum_{i=1}^n X_i = \mu\right) = 1$$
大数定律告诉我们，样本均值会收敛到期望值。类似地，经验分布会收敛到真实分布。
3.1.2 AEP定理的陈述
定理（渐近等分性，AEP）：设 $X_1, X_2, \ldots$ 是i.i.d.随机变量，服从分布 $p(x)$，熵为 $H(X)$。定义典型集 $A_\epsilon^{(n)}$ 为满足以下条件的序列 $(x_1, \ldots, x_n)$ 的集合：
$$\left|-\frac{1}{n}\log_2 p(x_1, \ldots, x_n) - H(X)\right| < \epsilon$$
其中 $p(x_1, \ldots, x_n) = \prod_{i=1}^n p(x_i)$（由于独立性）。
则对于任意 $\epsilon > 0$，当 $n$ 足够大时：
高概率：$P((X_1, \ldots, X_n) \in A_\epsilon^{(n)}) > 1 - \epsilon$
大小上界：$|A_\epsilon^{(n)}| \leq 2^{n(H(X) + \epsilon)}$
大小下界：对于足够大的 $n$，$|A_\epsilon^{(n)}| \geq (1 - \epsilon) 2^{n(H(X) - \epsilon)}$
直观理解：
AEP告诉我们三个关键事实：
典型序列几乎必然出现：当我们观察一个很长的随机序列时，它几乎肯定是典型的。非典型序列虽然数量巨大，但它们的总概率可以忽略不计。
典型序列的数量相对较少：虽然典型集包含大量序列，但与整个序列空间 $|\mathcal{X}|^n$ 相比，它的大小只是 $2^{nH(X)}$。由于 $H(X) \leq \log |\mathcal{X}|$，这是一个指数级的缩减。
典型序列的概率大致相等：每个典型序列的概率约为 $2^{-nH(X)}$。这就是"等分性"（equipartition）的含义——概率质量几乎均匀地分布在典型集上。
名称来源：
"渐近等分性"这个名字来自统计力学。在统计力学中，等分定理指出，在热平衡状态下，系统的微观状态几乎是等概率的。AEP是信息论中的类似结果：在长序列极限下，典型序列几乎是等概率的。
3.1.3 AEP的证明
证明：
定义随机变量 $Y_i = -\log_2 p(X_i)$。由于 $X_i$ 是i.i.d.的，$Y_i$ 也是i.i.d.的。
计算 $Y_i$ 的期望：
$$\mathbb{E}[Y_i] = \mathbb{E}[-\log_2 p(X)] = -\sum_x p(x) \log_2 p(x) = H(X)$$
根据弱大数定律：
$$\frac{1}{n}\sum_{i=1}^n Y_i = -\frac{1}{n}\sum_{i=1}^n \log_2 p(X_i) = -\frac{1}{n}\log_2 p(X_1, \ldots, X_n) \to H(X)$$
依概率收敛。这正是典型集定义中的条件，因此性质1成立。
对于性质2，典型集中的每个序列满足：
$$-\frac{1}{n}\log_2 p(x^n) < H(X) + \epsilon$$
即 $p(x^n) > 2^{-n(H(X) + \epsilon)}$。由于所有典型序列的概率之和不超过1：
$$1 \geq \sum_{x^n \in A_\epsilon^{(n)}} p(x^n) > |A_\epsilon^{(n)}| \cdot 2^{-n(H(X) + \epsilon)}$$
因此 $|A_\epsilon^{(n)}| < 2^{n(H(X) + \epsilon)}$。
对于性质3，对于足够大的 $n$，典型集的概率至少为 $1-\epsilon$。同时，每个典型序列满足 $p(x^n) < 2^{-n(H(X) - \epsilon)}$。因此：
$$1 - \epsilon < \sum_{x^n \in A_\epsilon^{(n)}} p(x^n) < |A_\epsilon^{(n)}| \cdot 2^{-n(H(X) - \epsilon)}$$
因此 $|A_\epsilon^{(n)}| > (1-\epsilon) 2^{n(H(X) - \epsilon)}$。
证毕。
代码示例3-1：AEP数值验证
import numpy as np
import matplotlib.pyplot as plt
from itertools import product
def verify_aep():
"""
数值验证渐近等分性
"""
# 二元信源：P(X=0) = p, P(X=1) = 1-p
p = 0.7
H = -p * np.log2(p) - (1-p) * np.log2(1-p)
print(f"二元信源: P(X=0)={p}, P(X=1)={1-p}")
print(f"熵 H(X) = {H:.4f} bits")
print("=" * 60)
# 测试不同的序列长度
for n in [5, 10, 15, 20]:
print(f"\n序列长度 n = {n}")
print("-" * 40)
# 生成所有可能的序列
all_sequences = list(product([0, 1], repeat=n))
total_sequences = len(all_sequences)
# 计算每个序列的概率
seq_probs = []
for seq in all_sequences:
k = sum(seq) # 1的个数
prob = (p ** (n - k)) * ((1-p) ** k)
seq_probs.append(prob)
# 计算 -1/n log p(x^n)
normalized_info = [-np.log2(prob + 1e-30) / n for prob in seq_probs]
# 典型集（epsilon = 0.1）
epsilon = 0.1
typical_set = [i for i, ni in enumerate(normalized_info)
if abs(ni - H) < epsilon]
typical_size = len(typical_set)
typical_prob = sum(seq_probs[i] for i in typical_set)
print(f" 总序列数: {total_sequences}")
print(f" 典型集大小: {typical_size} ({typical_size/total_sequences*100:.2f}%)")
print(f" 典型集概率: {typical_prob:.6f}")
print(f" 理论下界: {(1-epsilon) * 2**(n*(H-epsilon)):.2f}")
print(f" 理论上界: {2**(n*(H+epsilon)):.2f}")
# 验证典型序列的概率范围
if typical_size > 0:
typical_probs = [seq_probs[i] for i in typical_set]
print(f" 典型序列概率范围: [{min(typical_probs):.2e}, {max(typical_probs):.2e}]")
print(f" 理论范围: [{2**(-n*(H+epsilon)):.2e}, {2**(-n*(H-epsilon)):.2e}]")
verify_aep()输出示例：
二元信源: P(X=0)=0.7, P(X=1)=0.3
熵 H(X) = 0.8813 bits
============================================================
序列长度 n = 10
----------------------------------------
总序列数: 1024
典型集大小: 220 (21.48%)
典型集概率: 0.929838
理论下界: 63.51
理论上界: 341.29
典型序列概率范围: [1.63e-04, 3.43e-04]
理论范围: [1.51e-04, 3.72e-04]3.2 典型集的性质
3.2.1 典型序列的特征
一个序列 $x^n = (x_1, \ldots, x_n)$ 是典型的，当且仅当它的"每符号自信息"接近熵：
$$\left|-\frac{1}{n}\log_2 p(x^n) - H(X)\right| < \epsilon$$
对于i.i.d.信源，这等价于：
$$\left|-\frac{1}{n}\sum_{i=1}^n \log_2 p(x_i) - H(X)\right| < \epsilon$$
另一种等价定义（基于经验分布）：
定义序列 $x^n$ 的经验分布（type）为：
$$\hat{p}(a) = \frac{N(a|x^n)}{n}$$
其中 $N(a|x^n)$ 是符号 $a$ 在序列中出现的次数。
则典型集也可以定义为经验分布接近真实分布的序列集合：
$$A_\epsilon^{(n)} = \left\{x^n : \left|\hat{p}(a) - p(a)\right| < \epsilon \cdot p(a), \forall a \in \mathcal{X}\right\}$$
这两种定义在 $n$ 足够大时是等价的。
3.2.2 典型集的大小
典型集的大小满足：
$$(1-\epsilon) 2^{n(H(X)-\epsilon)} \leq |A_\epsilon^{(n)}| \leq 2^{n(H(X)+\epsilon)}$$
这意味着典型集的大小约为 $2^{nH(X)}$。
对比：
- 整个序列空间的大小：$|\mathcal{X}|^n = 2^{n \log_2 |\mathcal{X}|}$
- 典型集的大小：$\approx 2^{nH(X)}$
由于 $H(X) \leq \log_2 |\mathcal{X}|$，典型集通常是序列空间的指数级小子集。
例子：
考虑公平硬币（$H(X)=1$）抛掷 $n=100$ 次：
- 总序列数：$2^{100} \approx 10^{30}$
- 典型集大小：$\approx 2^{100} = 2^{100}$（因为 $H(X)=1=\log_2 2$，此时典型集几乎等于全集）
考虑偏斜硬币（$P(H)=0.9$，$H(X) \approx 0.47$）抛掷 $n=100$ 次：
- 总序列数：$2^{100} \approx 10^{30}$
- 典型集大小：$\approx 2^{47} \approx 10^{14}$
典型集只占全集的 $2^{-53} \approx 10^{-16}$，但却包含了超过99%的概率质量！
3.2.3 典型序列的概率
每个典型序列的概率满足：
$$2^{-n(H(X)+\epsilon)} < p(x^n) < 2^{-n(H(X)-\epsilon)}$$
即典型序列的概率大致为 $2^{-nH(X)}$。
重要推论：典型序列几乎是等概率的。这就是"等分性"的含义。
代码示例3-2：典型集大小与熵的关系
import numpy as np
import matplotlib.pyplot as plt
def typical_set_size_vs_entropy():
"""
研究典型集大小如何随熵变化
"""
n = 20 # 序列长度
# 二元信源，改变p来改变熵
p_values = np.linspace(0.01, 0.99, 50)
results = []
for p in p_values:
H = -p * np.log2(p) - (1-p) * np.log2(1-p)
# 理论典型集大小
typical_size_approx = 2**(n * H)
# 总序列数
total_size = 2**n
# 比例
ratio = typical_size_approx / total_size
results.append({
'p': p,
'H': H,
'typical_size': typical_size_approx,
'ratio': ratio
})
# 可视化
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 5))
# 图1：熵 vs p
H_values = [r['H'] for r in results]
ax1.plot(p_values, H_values, 'b-', linewidth=2)
ax1.set_xlabel('P(X=0)', fontsize=12)
ax1.set_ylabel('熵 H(X) (bits)', fontsize=12)
ax1.set_title('二元信源的熵', fontsize=14)
ax1.grid(True, alpha=0.3)
# 图2：典型集比例 vs 熵
ratios = [r['ratio'] for r in results]
H_values_plot = [r['H'] for r in results]
ax2.semilogy(H_values_plot, ratios, 'r-', linewidth=2)
ax2.set_xlabel('熵 H(X) (bits)', fontsize=12)
ax2.set_ylabel('典型集 / 全集 (对数尺度)', fontsize=12)
ax2.set_title(f'典型集相对大小 (n={n})', fontsize=14)
ax2.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('typical_set_size.png', dpi=150)
plt.show()
# 打印一些具体数值
print("典型集大小分析 (n=20)")
print("=" * 60)
for p in [0.1, 0.3, 0.5, 0.7, 0.9]:
H = -p * np.log2(p) - (1-p) * np.log2(1-p)
typical = 2**(20 * H)
total = 2**20
print(f"p={p}: H={H:.4f}, 典型集≈{typical:.0f}, 全集={total}, 比例={typical/total:.6f}")
typical_set_size_vs_entropy()3.3 联合典型序列
3.3.1 联合典型性的定义
定义：设 $(X,Y)$ 服从联合分布 $p(x,y)$。序列对 $(x^n, y^n) = ((x_1, y_1), \ldots, (x_n, y_n))$ 称为联合典型的，如果：
$x^n$ 关于 $p(x)$ 是典型的
$y^n$ 关于 $p(y)$ 是典型的
$(x^n, y^n)$ 关于 $p(x,y)$ 是典型的，即：
$$\left|-\frac{1}{n}\log_2 p(x^n, y^n) - H(X,Y)\right| < \epsilon$$
联合典型集记为 $A_\epsilon^{(n)}(X,Y)$。
直观理解：
联合典型性不仅要求每个序列单独看起来"正常"，还要求它们之间的关系符合联合分布。例如，如果 $X$ 和 $Y$ 高度相关，那么联合典型的序列对应该表现出这种相关性。
3.3.2 联合典型集的大小
类似于单边典型集，联合典型集的大小约为：
$$|A_\epsilon^{(n)}(X,Y)| \approx 2^{nH(X,Y)}$$
每个联合典型序列对的概率约为 $2^{-nH(X,Y)}$。
3.3.3 条件典型性
定义：给定 $x^n$，序列 $y^n$ 称为条件典型的（相对于 $p(y|x)$），如果 $(x^n, y^n)$ 是联合典型的。
条件典型集的大小约为 $2^{nH(Y|X)}$。
重要性质：如果 $x^n$ 是典型的，那么从条件分布 $p(y^n|x^n) = \prod_{i=1}^n p(y_i|x_i)$ 生成的 $y^n$ 以高概率是条件典型的。
3.3.4 联合典型性引理
引理：设 $(X^n, Y^n)$ 是i.i.d.服从 $p(x,y)$。则：
$P((X^n, Y^n) \in A_\epsilon^{(n)}) \to 1$（联合典型序列以高概率出现）
设 $\tilde{X}^n$ 和 $\tilde{Y}^n$ 是独立的，分别服从 $p(x^n)$ 和 $p(y^n)$。则：
$$P((\tilde{X}^n, \tilde{Y}^n) \in A_\epsilon^{(n)}) \leq 2^{-n(I(X;Y) - 3\epsilon)}$$
直观理解：
性质2非常深刻：如果两个序列是独立生成的，它们是联合典型的概率指数级小，指数是互信息 $I(X;Y)$。如果 $X$ 和 $Y$ 独立（$I(X;Y)=0$），这个概率只是多项式级小；但如果它们相关，概率就指数级小。
这个引理是信道编码定理证明的核心：接收端通过检查哪个候选消息与接收序列联合典型来解码，错误消息与接收序列联合典型的概率指数级小。
代码示例3-3：联合典型性演示
import numpy as np
from itertools import product
def joint_typicality_demo():
"""
演示联合典型性
"""
# 二元对称信道模型
# X是输入，Y是输出
# P(Y=X) = 0.9, P(Y≠X) = 0.1
p_x = 0.5 # P(X=0) = P(X=1) = 0.5
p_y_given_x = np.array([
[0.9, 0.1], # X=0
[0.1, 0.9] # X=1
])
# 联合分布
joint = np.zeros((2, 2))
for x in range(2):
for y in range(2):
joint[x, y] = p_x * p_y_given_x[x, y]
# 边缘分布
marginal_x = joint.sum(axis=1)
marginal_y = joint.sum(axis=0)
# 熵
def entropy_dist(p):
p = p[p > 0]
return -np.sum(p * np.log2(p))
H_X = entropy_dist(marginal_x)
H_Y = entropy_dist(marginal_y)
# 联合熵
flat_joint = joint.flatten()
flat_joint = flat_joint[flat_joint > 0]
H_XY = -np.sum(flat_joint * np.log2(flat_joint))
# 互信息
I_XY = H_X + H_Y - H_XY
print("联合典型性演示")
print("=" * 60)
print(f"H(X) = {H_X:.4f}")
print(f"H(Y) = {H_Y:.4f}")
print(f"H(X,Y) = {H_XY:.4f}")
print(f"I(X;Y) = {I_XY:.4f}")
# 序列长度
n = 10
epsilon = 0.15
# 生成一些序列对并检查典型性
np.random.seed(42)
print(f"\n检查序列对 (n={n}, ε={epsilon})")
print("-" * 60)
# 情况1：真正相关的序列对（从联合分布生成）
x_seq = np.random.choice([0, 1], size=n, p=[0.5, 0.5])
y_seq = np.array([np.random.choice([0, 1], p=p_y_given_x[x]) for x in x_seq])
# 计算经验统计量
def check_typicality(seq, dist, epsilon):
"""检查序列是否关于给定分布典型"""
n = len(seq)
unique, counts = np.unique(seq, return_counts=True)
empirical = np.zeros(len(dist))
for u, c in zip(unique, counts):
empirical[int(u)] = c / n
# 检查每个符号的频率
for i in range(len(dist)):
if abs(empirical[i] - dist[i]) > epsilon * dist[i]:
return False
return True
x_typical = check_typicality(x_seq, marginal_x, epsilon)
y_typical = check_typicality(y_seq, marginal_y, epsilon)
# 联合典型性
xy_pairs = list(zip(x_seq, y_seq))
unique_pairs, counts = np.unique(xy_pairs, axis=0, return_counts=True)
empirical_joint = np.zeros((2, 2))
for pair, count in zip(unique_pairs, counts):
empirical_joint[int(pair[0]), int(pair[1])] = count / n
joint_typical = True
for i in range(2):
for j in range(2):
if abs(empirical_joint[i, j] - joint[i, j]) > epsilon * joint[i, j]:
joint_typical = False
print(f"相关序列对:")
print(f" X: {x_seq}")
print(f" Y: {y_seq}")
print(f" X典型? {x_typical}")
print(f" Y典型? {y_typical}")
print(f" 联合典型? {joint_typical}")
# 情况2：独立序列对
x_indep = np.random.choice([0, 1], size=n, p=[0.5, 0.5])
y_indep = np.random.choice([0, 1], size=n, p=[0.5, 0.5])
x_typical_2 = check_typicality(x_indep, marginal_x, epsilon)
y_typical_2 = check_typicality(y_indep, marginal_y, epsilon)
xy_pairs_2 = list(zip(x_indep, y_indep))
unique_pairs_2, counts_2 = np.unique(xy_pairs_2, axis=0, return_counts=True)
empirical_joint_2 = np.zeros((2, 2))
for pair, count in zip(unique_pairs_2, counts_2):
empirical_joint_2[int(pair[0]), int(pair[1])] = count / n
joint_typical_2 = True
for i in range(2):
for j in range(2):
if abs(empirical_joint_2[i, j] - joint[i, j]) > epsilon * joint[i, j]:
joint_typical_2 = False
print(f"\n独立序列对:")
print(f" X: {x_indep}")
print(f" Y: {y_indep}")
print(f" X典型? {x_typical_2}")
print(f" Y典型? {y_typical_2}")
print(f" 联合典型? {joint_typical_2}")
# 蒙特卡洛估计联合典型概率
print(f"\n蒙特卡洛估计（10000次试验）")
print("-" * 60)
n_trials = 10000
joint_typical_count = 0
indep_joint_typical_count = 0
for _ in range(n_trials):
# 相关序列对
x = np.random.choice([0, 1], size=n, p=[0.5, 0.5])
y = np.array([np.random.choice([0, 1], p=p_y_given_x[xi]) for xi in x])
# 简化的典型性检查（基于计数）
n_00 = np.sum((x == 0) & (y == 0))
n_01 = np.sum((x == 0) & (y == 1))
n_10 = np.sum((x == 1) & (y == 0))
n_11 = np.sum((x == 1) & (y == 1))
emp_joint = np.array([[n_00, n_01], [n_10, n_11]]) / n
is_joint_typical = True
for i in range(2):
for jj in range(2):
if abs(emp_joint[i, jj] - joint[i, jj]) > epsilon * joint[i, jj]:
is_joint_typical = False
if is_joint_typical:
joint_typical_count += 1
# 独立序列对
x_ind = np.random.choice([0, 1], size=n, p=[0.5, 0.5])
y_ind = np.random.choice([0, 1], size=n, p=[0.5, 0.5])
n_00 = np.sum((x_ind == 0) & (y_ind == 0))
n_01 = np.sum((x_ind == 0) & (y_ind == 1))
n_10 = np.sum((x_ind == 1) & (y_ind == 0))
n_11 = np.sum((x_ind == 1) & (y_ind == 1))
emp_joint = np.array([[n_00, n_01], [n_10, n_11]]) / n
is_joint_typical = True
for i in range(2):
for jj in range(2):
if abs(emp_joint[i, jj] - joint[i, jj]) > epsilon * joint[i, jj]:
is_joint_typical = False
if is_joint_typical:
indep_joint_typical_count += 1
print(f"相关序列对联合典型概率: {joint_typical_count/n_trials:.4f}")
print(f"独立序列对联合典型概率: {indep_joint_typical_count/n_trials:.4f}")
print(f"理论界限（独立）: ≤ 2^(-{n*(I_XY - 3*epsilon):.2f}) = {2**(-n*(I_XY - 3*epsilon)):.6f}")
joint_typicality_demo()3.4 弱典型性与强典型性
3.4.1 弱典型性
前面讨论的典型性定义实际上是弱典型性（weak typicality），也称为熵典型性（entropy typicality）。它基于每符号自信息的平均值：
$$\left|-\frac{1}{n}\log_2 p(x^n) - H(X)\right| < \epsilon$$
弱典型性只关心序列的整体概率，不关心每个符号的具体频率。
3.4.2 强典型性
强典型性（strong typicality），也称为频率典型性（frequency typicality），要求每个符号的经验频率都接近其真实概率：
$$\left|\frac{N(a|x^n)}{n} - p(a)\right| < \epsilon, \quad \forall a \in \mathcal{X}$$
其中 $N(a|x^n)$ 是符号 $a$ 在序列 $x^n$ 中出现的次数。
3.4.3 两者的关系
- 强典型 ⇒ 弱典型：如果一个序列是强典型的，它一定是弱典型的（对于足够大的 $n$）
- 弱典型 ⇏ 强典型：弱典型序列不一定是强典型的
例子：
考虑 $p = [0.5, 0.25, 0.25]$ 的信源。一个序列可能有正确的平均自信息（弱典型），但符号 'a' 的频率偏离0.5（不是强典型）。
为什么需要强典型性：
在某些证明中（特别是涉及字母表大小增长的场景），弱典型性不够强，需要使用强典型性。强典型性提供了更精细的控制，但分析也更复杂。
在本书的大部分内容中，弱典型性已经足够，因此我们主要使用弱典型性。
三、程序员的视角
3.1 在数据压缩中的应用
典型序列的概念直接解释了数据压缩的可能性：
核心思想：只需要为典型序列分配唯一的码字，非典型序列可以忽略或分配特殊码字。
压缩方案：
枚举所有典型序列（约 $2^{nH(X)}$ 个）
为每个典型序列分配一个 $nH(X)$ 比特的索引
如果遇到非典型序列，输出特殊标记加原始序列
平均码长：
- 典型序列（概率 $1-\epsilon$）：$nH(X)$ 比特
- 非典型序列（概率 $\epsilon$）：$n \log |\mathcal{X}| + O(1)$ 比特
- 平均：约 $nH(X) + \epsilon n \log |\mathcal{X}|$ 比特
当 $\epsilon$ 很小时，平均每符号码长接近 $H(X)$ 比特，这正是信源编码定理的保证。
实际应用：
虽然实际压缩算法（如Huffman编码、算术编码、LZ系列）不显式使用典型集，但它们的性能极限由典型集大小决定。理解典型性有助于我们理解：
- 为什么某些数据可压缩（低熵，典型集小）
- 为什么压缩有极限（不能低于熵）
- 为什么块编码比逐符号编码更高效（更接近典型集的理论极限）
3.2 在信道编码中的应用
联合典型性是理解信道编码定理的关键：
解码策略（联合典型性译码）：
接收端收到序列 $y^n$
寻找消息 $m$，使得编码序列 $x^n(m)$ 与 $y^n$ 联合典型
如果找到唯一的这样的 $m$，输出它；否则报错
错误分析：
- 正确消息与接收序列以高概率联合典型
- 错误消息与接收序列联合典型的概率 $\leq 2^{-n(I(X;Y)-\epsilon)}$
- 如果有 $2^{nR}$ 个消息，错误概率 $\leq 2^{nR} \cdot 2^{-n(I(X;Y)-\epsilon)} = 2^{-n(I(X;Y)-R-\epsilon)}$
- 当 $R < I(X;Y)$ 时，错误概率指数级趋于零
这正是信道编码定理的核心论证。
3.3 常见陷阱
有限块长效应：AEP是渐近结果（$n \to \infty$）。在实际系统中，$n$ 是有限的，典型集的定义可能需要调整。
非i.i.d.信源：AEP的标准形式假设i.i.d.信源。对于有记忆的信源（如马尔可夫信源），需要推广AEP。
连续随机变量：对于连续信源，典型集的概念需要修改，因为单个序列的概率为零。这时使用微分熵和典型体积。
典型性检验的计算复杂度：精确检查典型性需要计算序列概率，对于长序列可能计算量大。实践中使用近似方法。
3.4 与其他层级的联系
- 与大数定律：AEP本质上是大数定律应用于自信息随机变量
- 与类型法（Method of Types）：类型法是组合数学工具，提供了分析典型集的另一种视角
- 与遍历理论：对于平稳遍历过程，有更一般的AEP（Shannon-McMillan-Breiman定理）
- 与算法信息论：柯尔莫哥洛夫复杂度提供了另一种"典型性"的定义
四、代码实战
4.1 典型集分析器
import numpy as np
from collections import Counter
from itertools import product
class TypicalSetAnalyzer:
"""典型集分析器"""
def __init__(self, distribution, alphabet=None):
"""
初始化
参数:
distribution: 概率分布列表或字典
alphabet: 符号表（可选）
"""
if isinstance(distribution, dict):
self.alphabet = list(distribution.keys())
self.probs = np.array(list(distribution.values()))
else:
self.probs = np.array(distribution)
self.alphabet = alphabet or list(range(len(distribution)))
self.probs = self.probs / self.probs.sum() # 归一化
# 计算熵
mask = self.probs > 0
self.entropy = -np.sum(self.probs[mask] * np.log2(self.probs[mask]))
def generate_all_sequences(self, n):
"""生成所有长度为n的序列"""
return list(product(self.alphabet, repeat=n))
def sequence_probability(self, seq):
"""计算序列的概率（i.i.d.假设）"""
counter = Counter(seq)
prob = 1.0
for symbol in self.alphabet:
prob *= self.probs[self.alphabet.index(symbol)] ** counter.get(symbol, 0)
return prob
def is_typical(self, seq, epsilon):
"""检查序列是否典型"""
n = len(seq)
log_prob = np.log2(self.sequence_probability(seq) + 1e-30)
normalized_info = -log_prob / n
return abs(normalized_info - self.entropy) < epsilon
def analyze_typical_set(self, n, epsilon=0.1):
"""
分析典型集
参数:
n: 序列长度
epsilon: 典型性阈值
返回:
典型集分析的字典
"""
all_seqs = self.generate_all_sequences(n)
total = len(all_seqs)
typical_seqs = [seq for seq in all_seqs if self.is_typical(seq, epsilon)]
typical_size = len(typical_seqs)
typical_prob = sum(self.sequence_probability(seq) for seq in typical_seqs)
# 理论预测
theoretical_size = 2**(n * self.entropy)
theoretical_lower = (1 - epsilon) * 2**(n * (self.entropy - epsilon))
theoretical_upper = 2**(n * (self.entropy + epsilon))
return {
'n': n,
'epsilon': epsilon,
'total_sequences': total,
'typical_size': typical_size,
'typical_probability': typical_prob,
'theoretical_size': theoretical_size,
'theoretical_lower': theoretical_lower,
'theoretical_upper': theoretical_upper,
'ratio': typical_size / total if total > 0 else 0
}
# 使用示例
if __name__ == "__main__":
# 二元信源
analyzer = TypicalSetAnalyzer([0.7, 0.3])
print("二元信源典型集分析")
print("=" * 60)
print(f"分布: P(0)=0.7, P(1)=0.3")
print(f"熵: {analyzer.entropy:.4f} bits")
print()
for n in [5, 10, 15]:
result = analyzer.analyze_typical_set(n, epsilon=0.15)
print(f"n = {n}")
print(f" 总序列数: {result['total_sequences']}")
print(f" 典型集大小: {result['typical_size']} ({result['ratio']*100:.2f}%)")
print(f" 典型集概率: {result['typical_probability']:.6f}")
print(f" 理论预测: {result['theoretical_size']:.1f}")
print(f" 理论范围: [{result['theoretical_lower']:.1f}, {result['theoretical_upper']:.1f}]")
print()4.2 联合典型性检验器
import numpy as np
class JointTypicalityTester:
"""联合典型性检验器"""
def __init__(self, joint_distribution):
"""
初始化
参数:
joint_distribution: 二维数组，表示联合分布 P(X,Y)
"""
self.joint = np.array(joint_distribution)
self.marginal_x = self.joint.sum(axis=1)
self.marginal_y = self.joint.sum(axis=0)
# 计算熵
self.H_X = self._entropy(self.marginal_x)
self.H_Y = self._entropy(self.marginal_y)
self.H_XY = self._entropy(self.joint.flatten())
self.I_XY = self.H_X + self.H_Y - self.H_XY
def _entropy(self, dist):
dist = np.array(dist).flatten()
dist = dist[dist > 0]
return -np.sum(dist * np.log2(dist))
def is_jointly_typical(self, x_seq, y_seq, epsilon):
"""
检查序列对是否联合典型
参数:
x_seq: X序列
y_seq: Y序列
epsilon: 阈值
返回:
布尔值
"""
n = len(x_seq)
assert len(y_seq) == n
# 计算经验联合分布
joint_counts = np.zeros_like(self.joint)
for x, y in zip(x_seq, y_seq):
joint_counts[x, y] += 1
empirical_joint = joint_counts / n
# 检查联合典型性
for i in range(self.joint.shape[0]):
for j in range(self.joint.shape[1]):
if self.joint[i, j] > 0:
if abs(empirical_joint[i, j] - self.joint[i, j]) > epsilon * self.joint[i, j]:
return False
return True
def estimate_joint_typical_probability(self, n, epsilon, n_trials=10000, independent=False):
"""
估计联合典型概率
参数:
n: 序列长度
epsilon: 阈值
n_trials: 试验次数
independent: 是否使用独立序列对
返回:
联合典型概率估计
"""
count = 0
for _ in range(n_trials):
if independent:
# 独立生成X和Y
x_seq = np.random.choice(len(self.marginal_x), size=n, p=self.marginal_x)
y_seq = np.random.choice(len(self.marginal_y), size=n, p=self.marginal_y)
else:
# 从联合分布生成
indices = np.random.choice(
self.joint.size,
size=n,
p=self.joint.flatten()
)
x_seq = indices // self.joint.shape[1]
y_seq = indices % self.joint.shape[1]
if self.is_jointly_typical(x_seq, y_seq, epsilon):
count += 1
return count / n_trials
# 使用示例
if __name__ == "__main__":
# 二元对称信道
joint = np.array([
[0.45, 0.05],
[0.05, 0.45]
])
tester = JointTypicalityTester(joint)
print("联合典型性检验")
print("=" * 60)
print(f"H(X) = {tester.H_X:.4f}")
print(f"H(Y) = {tester.H_Y:.4f}")
print(f"H(X,Y) = {tester.H_XY:.4f}")
print(f"I(X;Y) = {tester.I_XY:.4f}")
print()
n = 20
epsilon = 0.15
p_related = tester.estimate_joint_typical_probability(n, epsilon, independent=False)
p_independent = tester.estimate_joint_typical_probability(n, epsilon, independent=True)
print(f"n = {n}, ε = {epsilon}")
print(f"相关序列对联合典型概率: {p_related:.4f}")
print(f"独立序列对联合典型概率: {p_independent:.4f}")
print(f"理论界限（独立）: ≤ 2^(-{n*(tester.I_XY - 3*epsilon):.2f})")4.3 典型序列编码器（概念演示）
import numpy as np
class TypicalSequenceEncoder:
"""
基于典型序列的编码器（概念演示）
注意：这不是实用的压缩算法，仅用于演示典型序列编码的思想
"""
def __init__(self, distribution, block_size=8):
self.distribution = distribution
self.block_size = block_size
self.typical_set = self._build_typical_set(epsilon=0.1)
self.codebook = {seq: idx for idx, seq in enumerate(self.typical_set)}
def _build_typical_set(self, epsilon):
"""构建典型集"""
from itertools import product
alphabet = list(range(len(self.distribution)))
all_seqs = list(product(alphabet, repeat=self.block_size))
# 计算熵
probs = np.array(self.distribution)
mask = probs > 0
H = -np.sum(probs[mask] * np.log2(probs[mask]))
typical = []
for seq in all_seqs:
# 计算序列概率
prob = 1.0
for symbol in seq:
prob *= probs[symbol]
normalized_info = -np.log2(prob) / self.block_size
if abs(normalized_info - H) < epsilon:
typical.append(seq)
return typical
def encode(self, data):
"""
编码数据
参数:
data: 整数列表
返回:
编码后的比特流（整数列表）
"""
encoded = []
n = len(data)
for i in range(0, n, self.block_size):
block = tuple(data[i:i+self.block_size])
# 填充短块
if len(block) < self.block_size:
block = block + (0,) * (self.block_size - len(block))
if block in self.codebook:
# 典型序列：输出索引
idx = self.codebook[block]
# 用固定比特数表示索引
n_bits = int(np.ceil(np.log2(len(self.typical_set))))
bits = [(idx >> b) & 1 for b in range(n_bits)]
encoded.extend(bits)
else:
# 非典型序列：输出转义码 + 原始数据
encoded.extend([1] * 10) # 转义码（假设）
for symbol in block:
encoded.extend([(symbol >> b) & 1 for b in range(4)])
return encoded
def compression_ratio(self):
"""计算理论压缩比"""
probs = np.array(self.distribution)
mask = probs > 0
H = -np.sum(probs[mask] * np.log2(probs[mask]))
original_bits = self.block_size * np.ceil(np.log2(len(self.distribution)))
compressed_bits = np.ceil(np.log2(len(self.typical_set)))
return compressed_bits / original_bits if original_bits > 0 else 1
# 使用示例
if __name__ == "__main__":
# 偏斜分布
dist = [0.7, 0.2, 0.05, 0.05]
encoder = TypicalSequenceEncoder(dist, block_size=8)
print("典型序列编码器")
print("=" * 60)
print(f"分布: {dist}")
print(f"块大小: {encoder.block_size}")
print(f"典型集大小: {len(encoder.typical_set)}")
print(f"总可能序列数: {4**8}")
print(f"压缩比: {encoder.compression_ratio():.4f}")
# 编码示例数据
data = [0, 0, 1, 0, 2, 0, 0, 1, 0, 0, 0, 0, 3, 0, 1, 0]
encoded = encoder.encode(data)
print(f"\n原始数据: {data}")
print(f"编码后: {encoded[:20]}... (共{len(encoded)}比特)")五、深入思考
5.1 历史背景
典型序列的概念由香农在其1948年的开创性论文中隐含地使用，但明确的表述和系统化是由后来的研究者完成的。渐近等分性（AEP）这个术语来自统计力学，反映了信息论与统计物理的深刻联系。
联合典型性译码方法由Cover在1970年代明确提出，成为网络信息论证明的标准工具。这种方法的优势在于其概念清晰性和通用性，尽管在实际系统中可能不是最优的译码策略。
类型法（Method of Types）是由Csiszár和Körner发展的另一种分析典型序列的方法，它在组合优化和大偏差理论中有广泛应用。
5.2 前沿方向
有限块长信息论：经典AEP是渐近结果，但实际系统工作在有限块长下。近年来，研究者致力于推导有限块长下的精确界限，这对于5G通信等应用至关重要。
非渐近典型性：对于非平稳或非遍历信源，经典的AEP不再适用。研究者正在开发更一般的典型性概念，适用于更广泛的信源模型。
量子典型性：在量子信息论中，典型子空间（typical subspace）是经典典型集的量子推广，在量子数据压缩和量子信道编码中起核心作用。
深度学习与典型性：最近的研究探讨了神经网络学习的数据表示与典型性之间的关系。一些工作表明，深度网络的隐层表示趋向于形成某种"典型"结构。
5.3 延伸阅读
Cover & Thomas《信息论基础》第3章
Csiszár & Körner《Information Theory: Coding Theorems for Discrete Memoryless Systems》第2章
Yeung《Information Theory and Network Coding》第3章
Dembo & Zeitouni《Large Deviations Techniques and Applications》
六、实验笔记
实验1：典型集大小的经验测量
目标：通过数值实验验证AEP关于典型集大小的预测。
步骤：
选择一个离散信源（如二元信源，$P(0)=0.7$）
对于不同的序列长度 $n \in \{5, 10, 15, 20, 25\}$：
- 生成所有可能的序列
- 计算每个序列的概率
- 确定典型集（$\epsilon=0.1$）
- 记录典型集大小和概率
绘制典型集大小随 $n$ 的变化，与理论预测 $2^{nH(X)}$ 比较
预期结果：
- 典型集概率随 $n$ 增加趋近于1
- 典型集大小的对数与 $n$ 成线性关系，斜率接近 $H(X)$
思考题：
- 为什么对于较小的 $n$，典型集概率可能较低？
- 实际典型集大小与理论预测的差距如何随 $n$ 变化？
实验2：联合典型性与互信息
目标：验证联合典型性引理，观察互信息如何影响独立序列对的联合典型概率。
步骤：
设计多个不同的联合分布 $p(x,y)$，覆盖不同的互信息值
对于每个分布：
- 计算理论互信息 $I(X;Y)$
- 通过蒙特卡洛模拟估计独立序列对的联合典型概率
- 比较估计值与理论界限 $2^{-nI(X;Y)}$
绘制联合典型概率 vs 互信息的关系
预期结果：
- 联合典型概率随互信息增加指数级下降
- 模拟结果应与理论界限吻合（允许常数因子差异）
扩展：
- 改变序列长度 $n$，观察指数衰减的速率
- 尝试不同的典型性阈值 $\epsilon$，分析其对结果的影响
七、本章小结
本章引入了典型序列这一信息论的核心概念，它是连接概率论与信息论的桥梁。
渐近等分性（AEP）告诉我们，长序列几乎必然属于一个相对很小的集合——典型集。这个集合的大小约为 $2^{nH(X)}$，每个典型序列的概率约为 $2^{-nH(X)}$。这一结果是信源编码定理的基础：我们只需要为典型序列编码，从而实现接近熵的压缩率。
联合典型性扩展了典型性的概念到多个随机变量。两个序列是联合典型的，不仅要求它们各自典型，还要求它们之间的关系符合联合分布。联合典型性引理表明，独立生成的序列对是联合典型的概率指数级小，指数是互信息。这一结果是信道编码定理和网络信息论证明的核心工具。
弱典型性与强典型性提供了两种不同强度的典型性定义。弱典型性基于平均自信息，强典型性基于经验频率。强典型性蕴含弱典型性，但反之不然。在大多数应用中，弱典型性已经足够。
从程序员的角度看，典型序列的概念解释了数据压缩的可能性和极限。虽然实际压缩算法不显式使用典型集，但它们的性能受限于典型集的大小。理解典型性有助于我们设计更高效的编码方案，并理解为什么某些数据可以高度压缩而某些不能。
典型性的论证方法是信息论证明的标准技术：将序列空间划分为典型集和非典型集，利用非典型集概率很小的事实简化分析。这种技巧在后续章节中将反复出现。
八、习题
习题3.1（基本计算）：考虑一个三元信源，$p = [0.5, 0.3, 0.2]$。
- (a) 计算熵 $H(X)$
- (b) 对于 $n=10$，列出所有可能的序列中概率最大的5个序列
- (c) 这些序列是典型的吗？（取 $\epsilon=0.1$）
习题3.2（AEP验证）：设 $X$ 是二元随机变量，$P(X=0)=0.8$。
- (a) 计算 $H(X)$
- (b) 对于 $n=20$，估算典型集的大小
- (c) 典型集占整个序列空间的比例是多少？
习题3.3（联合典型性）：设 $(X,Y)$ 的联合分布为：
$$p(x,y) = \begin{pmatrix} 0.4 & 0.1 \\ 0.1 & 0.4 \end{pmatrix}$$
- (a) 计算 $H(X)$、$H(Y)$、$H(X,Y)$、$I(X;Y)$
- (b) 对于 $n=10$，估算联合典型集的大小
- (c) 独立生成的序列对是联合典型的概率上界是多少？
习题3.4（编程题）：实现一个函数，输入是一个序列和概率分布，输出是该序列是否典型（使用弱典型性定义）。测试你的函数在不同长度的序列上的表现。
习题3.5（类型法）：对于长度为 $n$ 的序列，定义其"类型"为经验分布。证明类型的数量不超过 $(n+1)^{|\mathcal{X}|}$。
习题3.6（挑战题）：证明对于强典型序列，当 $n$ 足够大时，它也是弱典型序列。提示：使用连续性论证。
习题3.7（应用题）：假设你要设计一个图像压缩系统，将8×8像素块（每个像素8比特）编码。如果自然图像的熵约为4比特/像素，典型集的大小约为多少？你需要多少比特来表示每个典型块？
习题3.8（马尔可夫信源）：对于一个两状态马尔可夫信源，转移矩阵为：
$$P = \begin{pmatrix} 0.9 & 0.1 \\ 0.2 & 0.8 \end{pmatrix}$$
- (a) 计算平稳分布
- (b) 计算马尔可夫信源的熵率
- (c) AEP是否仍然适用？典型集大小约为多少？
习题3.9（连续信源）：对于高斯随机变量 $X \sim \mathcal{N}(0, \sigma^2)$，微分熵为 $h(X) = \frac{1}{2}\log_2(2\pi e \sigma^2)$。类比离散情况，"典型体积"约为多少？
习题3.10（开放性问题）：研究典型序列概念在以下任一领域的应用，撰写一篇500字左右的短文：
- (a) 生物信息学（DNA序列的模式识别）
- (b) 自然语言处理（语言模型的困惑度）
- (c) 异常检测（非典型序列的识别）
- (d) 密码学（伪随机数生成的质量评估）
重点讨论典型性如何帮助解决该领域的实际问题。