典型集与渐进均分性

Typical Set 和 Asymptotic Equipartition Property 应该是很深刻的性质。

AEP 的概率论基础

• 我们同样从概率论基础谈起。

Markov 不等式

• 对于非负的随机变量 ，有：

• 证明：按定义：

Chebyshev 不等式

• 对于随机变量 ，有：

• 证明：按定义：

随机变量收敛的模式

• 这里简要介绍几种随机变量收敛的模式。考虑随机变量列 ，我们考察其收敛到 的模式 ：

  • 几乎处处收敛：即存在 的子集 使得 ，且： 也称以概率 收敛。

  • 依概率收敛：即：

  另外还有依分布收敛、依 收敛等模式，但本文应该不会用到。这些模式都是对于一般随机变量定义的，并且可以验证它们之间的一些关系，例如几乎处处收敛是强于依概率收敛的。

大数定理

• 大数定理同样有几个版本，最简单的版本如下：

  • 弱大数定理：对于独立随机变量 ，每一个 都是可积的且具备相同的期望 。若 的二阶矩具备统一上界，则 依概率收敛到 。

  这个定理比较简单，证明直接使用 Chebyshev 不等式即可。我们在这里引入大数定理是为了要证明下面的 AEP ，但是 AEP 的叙述本身没有直接要求二阶矩有界。我们也许可以验证这一点，但更方便的方式是使用如下的另一个版本：

  • Khinchin 弱大数定理：对于独立同分布的随机变量 ，每一个 均可积且期望有界，记其为 。则 依概率收敛到 。

  这里我们就不再对二阶矩有要求了。但是 Khinchin 弱大数定理的证明比较复杂，这里不打算深入。另一方面，在弱大数定理中，若改为要求四阶矩有界，可以把结论加强到几乎必然收敛，这就是 Cantelli 强大数定理；在 Khinchin 弱大数定理中，我们可以直接把结论加强到几乎必然收敛，这就是 Kolmogorov 强大数定理，但是证明上会更加复杂。

引入：数据压缩

• 渐进均分性和典型集在直观上说的事情其实是，概率空间中极小的一部分典型样本（处于典型集中）占据了绝大多数的概率，并且这些典型样本各自的概率在数量级上差不多（渐进均分性）。单从这句话引入其实不够具体，为了提供直观，我们从数据压缩的码率¹引入。考虑如下问题：给定离散无记忆信源，其每次产生一个独立同分布的字符 ，我们要对 个字符构成的信息 编码。设 为另一同分布的随机变量，则一个显然的码率上界是 ，然而这个上界太蠢了，它距离理论下界熵率 太远。于是我们考虑引入渐进均分性和典型集，即对那些高概率的典型样本和其它样本分别编码，以逼近熵率。

渐进均分性

• 对于独立同分布的随机变量列 ，记 为另一同分布的随机变量，有 依概率收敛到 。这个定理的证明其实相当容易，直接使用 Khinchin 弱大数定理即可。AEP 的另一个表述是，定义： 则对于任意的 ，当 充分大时， 趋于 ，而 就被称作典型集²。可以看到，典型集中的元素的概率的数量级基本是一致的，并且它们占据了绝大多数概率，即它们“均分”了概率。

典型集

• 由 AEP 中的推导，我们可以期待 处于 级别，而我们的确可以严格的说明这一点。即，对于任意 及充分大的 ，有： 以上定理的证明不难，这里留作习题³。这样典型集中的元素个数就有保证了。考虑典型集中的元素在样本空间中的占比： 绝大多数时候 ，那么取一 使得 ，当 时就有 ，这说明典型集中的元素仅占样本空间极小的一部分。

高概率集

• 大致意思是说任何概率趋于 1 的集合基本包含典型集，过会再写。

解答：数据压缩

• 有了 AEP 和典型集，我们再回到一开始的问题。现在我们考虑以下的编码策略：

  • 对于 中的元素，直接编码。则每个元素的码长小于 。
  • 对于其它元素，同样直接编码。则每个元素的码长小于 。
  • 对于第一类元素，在开头追加 ；对于其余元素，在码前追加 。

  这样我们就得到了无误的编码方式。计算其码率： 其中 是一个任意小的正数。于是我们证明了，如上的编码方式可以任意的逼近码长。

• 另外也可以证明若码率小于熵率，则错误率必然趋于1，暂时不写这个。

---

1. 也就是考虑对信源发送的句子编码，每个文字的平均比特数。注意此时的编码是允许错误的。↩︎

2. 严格的说，是弱典型集。但是这里也涉及不到强典型集，所以就这么记了。↩︎

3. 其实我有一个又臭又长的证明，但是我觉得不会有人想在这看，所以就不放了。↩︎