信息论（13）：渐进均分性AEP与典型集
<p>Asymptotic Equipartition Property，渐近均分性。</p><p>想象一下来自同一来源的一长串信息，就像一条符号构成的河流，日复一日地从我们身边流过。</p>
<p>如果你观察足够长的时间，就会发生神奇的事情：这条河流开始呈现出某些典型的模式，并非所有序列出现的概率都相同，但几乎所有的概率都汇聚到一个集合中，在这个集合中，每个序列的信息含量都惊人地相似。</p>
<p>事实上，每个典型序列的概率都接近于$ 2^{-n H} $，其中 H 是源的熵。因此，当 n 增大时，<em>典型序列</em>的数量大约为 $ 2^{nH} $，并且它们几乎等概率。</p>
<p>因此得名：渐近的，对于较大的 n ；概率均分的，它们共享几乎相等的概率。</p>
<p>取一个长度为 n 的序列，例如 n=10：正反正正正反正反反正。</p>
<p>计数：正面 = 6，反面 = 4。</p>
<p>经验分布 = $ \hat{p}(H) = 6/10, \ \hat{p}(T) = 4/10 $。</p>
<p>因此，即使真实分布是 (1/2, 1/2)，实际序列的比例也可能略有不同。</p>
<p>对于较大的 n，大数定律表明：经验分布 $ \hat{p} $ 将以很高的概率接近真实值 p 。“接近”意味着，对于任何很小的 $ \varepsilon > 0 $，有：</p>
<p>$ |\hat{p}(H) - 1/2| < \varepsilon $</p>
<p>当 $ n \to \infty $ 时，概率趋近于 1。因此，$ \hat{p}(H) $ 介于 $ 0.5-\varepsilon $ 和 $ 0.5+\varepsilon $ 之间的序列被称为<strong>典型</strong>序列，对于该 $ \varepsilon $。</p>
<p>为什么不要求正好 n/2 个正面朝上？因为要求正好 n/2 个正面朝上过于严格，它会排除那些只有轻微偏差的序列，例如 1000 次抛硬币中出现 499 次正面朝上，即使它们在实际应用中仍然属于正常范围。</p>
<p>而且，对于较大的 n 值，正好 n/2 个正面朝上的概率非常小。但是，如果我们允许一个较小的容差 ε，那么对于较大的 n 值，属于这个更宽泛集合的总概率几乎为 1。这个更宽泛的集合 = 典型集合 $ \varepsilon^n $。</p>
<p>典型集合的大小为多少呢？</p>
<p>恰好有k 个正面的序列数 = $ \binom{n}{k} $。</p>
<p>对于k = n/2 （恰好），大小为 $ \approx \frac{2^n}{\sqrt{\pi n/2}} $（斯特林分布）。</p>
<p>对于k 在 $ n(1/2 \pm \varepsilon) $ 范围内的情况，我们对该范围内的 $ \binom{n}{k} $ 求和。</p>
<p>一个已知的事实（二项式集中性）：几乎所有 2^n 个序列的 k 都接近 n/2 。事实上，该范围内的数值约为 $ \approx 2^{n H(1/2)} = 2^n $（忽略多项式因子）。</p>
<p>因此，对于任何出现 k 次正面的特定序列，</p>
<p>概率 = $ (1/2)^k (1/2)^{n-k} = (1/2)^n = 2^{-n} $。</p>
<p>因此，在典型的集合中：每个序列的概率为 $ 2^{-n} $。序列的数量 ≈2^n 。</p>
<p>总概率 ≈ $ 2^n \cdot 2^{-n} = 1 $。</p>
<p>因此，概率均分：每个典型序列的概率都大致相同，约为 $ \approx 2^{-n H} $，其中 H=1 。</p><br>来源：程序园用户自行投稿发布，如果侵权，请联系站长删除<br>免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 谢谢楼主提供！ 谢谢分享，试用一下 分享、互助 让互联网精神温暖你我 鼓励转贴优秀软件安全工具和文档！ 感谢发布原创作品，程序园因你更精彩 感谢分享，学习下。 感谢分享，下载保存了，貌似很强大 过来提前占个楼 感谢发布原创作品，程序园因你更精彩 过来提前占个楼 谢谢分享，试用一下 收藏一下 不知道什么时候能用到 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 东西不错很实用谢谢分享 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 过来提前占个楼 过来提前占个楼 谢谢楼主提供！ 用心讨论，共获提升！
页:
[1]
2