典型序列
概述
典型序列（Typical Sequence）是 Shannon 信源编码定理证明中的核心概念：当消息足够长时，绝大多数实际产生的消息都集中在一个远小于所有可能消息的集合中。
关键内容
定义
对于长度为 n 的独立同分布随机变量序列，典型序列是指其经验分布接近真实分布的序列。典型序列集合的大小约为 2^(nH)，远小于所有可能序列的总数 s^n。
在信源编码中的作用
- 只需为典型序列分配码字，非典型序列可以忽略（概率趋于零）
- 这使得平均码长可以任意接近熵率 H
- 是"存在性证明"的关键工具
直觉
假设抛 1000 次公平硬币，所有可能的结果有 2^1000 种。但"典型"的结果——大约 500 次正面、500 次反面——只占其中约 2^(1000×H(0.5)) = 2^1000 种。对于不均匀分布，典型序列集合远小于所有可能序列。
来源
- raw/books/信息论/02_shannon_1948_mathematical_theory_of_communication.md — Shannon (1948) 深度解析
- raw/books/计算机科学/02-shannon-mathematical-theory-of-communication.md — Shannon (1948) 计算机科学视角深度解析