信息论（13）：渐进均分性AEP与典型集

Asymptotic Equipartition Property，渐近均分性。

想象一下来自同一来源的一长串信息，就像一条符号构成的河流，日复一日地从我们身边流过。

如果你观察足够长的时间，就会发生神奇的事情：这条河流开始呈现出某些典型的模式，并非所有序列出现的概率都相同，但几乎所有的概率都汇聚到一个集合中，在这个集合中，每个序列的信息含量都惊人地相似。

事实上，每个典型序列的概率都接近于$ 2^{-n H} $，其中 H 是源的熵。因此，当 n 增大时，典型序列的数量大约为 $ 2^{nH} $，并且它们几乎等概率。

因此得名：渐近的，对于较大的 n ；概率均分的，它们共享几乎相等的概率。

取一个长度为 n 的序列，例如 n=10：正反正正正反正反反正。

计数：正面 = 6，反面 = 4。

经验分布 = $ \hat{p}(H) = 6/10, \ \hat{p}(T) = 4/10 $。

因此，即使真实分布是 (1/2, 1/2)，实际序列的比例也可能略有不同。

对于较大的 n，大数定律表明：经验分布 $ \hat{p} $ 将以很高的概率接近真实值 p 。“接近”意味着，对于任何很小的 $ \varepsilon > 0 $，有：

$ |\hat{p}(H) - 1/2| < \varepsilon $

当 $ n \to \infty $ 时，概率趋近于 1。因此，$ \hat{p}(H) $ 介于 $ 0.5-\varepsilon $ 和 $ 0.5+\varepsilon $ 之间的序列被称为典型序列，对于该 $ \varepsilon $。

为什么不要求正好 n/2 个正面朝上？因为要求正好 n/2 个正面朝上过于严格，它会排除那些只有轻微偏差的序列，例如 1000 次抛硬币中出现 499 次正面朝上，即使它们在实际应用中仍然属于正常范围。

而且，对于较大的 n 值，正好 n/2 个正面朝上的概率非常小。但是，如果我们允许一个较小的容差 ε，那么对于较大的 n 值，属于这个更宽泛集合的总概率几乎为 1。这个更宽泛的集合 = 典型集合 $ \varepsilon^n $。

典型集合的大小为多少呢？

恰好有 k 个正面的序列数 = $ \binom{n}{k} $。

对于 k = n/2 （恰好），大小为 $ \approx \frac{2^n}{\sqrt{\pi n/2}} $（斯特林分布）。

对于 k 在 $ n(1/2 \pm \varepsilon) $ 范围内的情况，我们对该范围内的 $ \binom{n}{k} $ 求和。

一个已知的事实（二项式集中性）：几乎所有 2^n 个序列的 k 都接近 n/2 。事实上，该范围内的数值约为 $ \approx 2^{n H(1/2)} = 2^n $（忽略多项式因子）。

因此，对于任何出现 k 次正面的特定序列，

概率 = $ (1/2)^k (1/2)^{n-k} = (1/2)^n = 2^{-n} $。

因此，在典型的集合中：每个序列的概率为 $ 2^{-n} $。序列的数量 ≈ 2^n 。

总概率 ≈ $ 2^n \cdot 2^{-n} = 1 $。

因此，概率均分：每个典型序列的概率都大致相同，约为 $ \approx 2^{-n H} $，其中 H=1 。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！