渐进均分性(AEP)

渐进均分性(Asymptotic Equipartition Property)

\(\newcommand{\E}{\mathbb{E}}\)在概率论中，我们有大数定理（弱）：对于一列独立同分布的随机变量\(X_1,X_2,\cdots\)，前\(n\)个随机变量的平均值\(\dfrac{1}{n}\sum\limits_{i=1}^{n}X_i\)（依然是一个随机变量）当\(n\to\infty\)时会依概率收敛到\(\E [X_1]\)。也即\(\forall\varepsilon>0,\lim\limits_{n\to\infty}\Pr\left[\left|\dfrac{1}{n}\sum\limits_{i=1}^{n}X_i-\E[X_1]\right|>\varepsilon\right]=0\)。

从信息论的角度如何理解大数定律呢？对于独立同分布的随机变量\(X_1,X_2,\cdots\)，我们只关注它们的分布，并对每个取值的概率取对数，得到的一列随机变量\(\log p(X_1),\log p(X_2),\cdots\)显然也是独立同分布的。那么根据大数定理，\(\dfrac{1}{n}\sum\limits_{i=1}^{n}\log p(X_i)\)将会依概率收敛到\(\E[\log p(X_1)]\)，这恰好是随机变量的熵\(H(X_1)\)（的相反数）！我们试着理解左边那一项有什么含义：\(\sum\limits_{i=1}^{n}\log p(X_i)\)可以写成\(\log \left(p(X_1)p(X_2)\cdots p(X_n)\right)\)，由于\(p(X_i)\)是互相独立的，这等价于\(\log p(X_1,X_2,\cdots,X_n)\)。这是一个随机变量，表示每种序列出现的概率（的对数）。现在大数定律告诉我们，当\(n\)充分大时，\(p(X_1,X_2,\cdots,X_n)\)有极大的概率分布在\(2^{-nH(X_1)}\)附近。这说明，大多数的序列出现的概率实际上是相等的，它们在渐进意义下均分了总概率。在信息论中，我们把这样的性质称为“渐进均分性”。

为了更精确的讨论这种“充分接近”，我们把概率分布在\([2^{-n(H(X_1)+\epsilon)},2^{-n(H(X_1)-\epsilon)}]\)的序列收集进集合\(A_\epsilon^{(n)}\)，把这个集合称为\(\epsilon\)-典型集(Typical Set)。典型集本质上是一个事件（因为它是样本的一个集合），根据弱大数定理的依概率收敛，典型集的概率满足\(\Pr[A_\epsilon^{(n)}]>1-\epsilon\)。

同时，我们对典型集中的序列个数也有一个估计。由于典型集中序列的概率有下界\(2^{-n(H(X_1)+\epsilon)}\)，因此其中的序列个数满足\(1\geq \sum\limits_{x\in A_\epsilon^{(n)}}p(x)\geq |A_\epsilon^{(n)}|2^{-n(H(X_1)+\epsilon)}\)，因此序列个数有上界\(2^{n(H(X_1)+\epsilon)}\)；同理，典型集中序列的概率有上界\(2^{-n(H(X_1)-\epsilon)}\)，因此\(1-\epsilon<\Pr[A_\epsilon^{(n)}]= \sum\limits_{x\in A_\epsilon^{(n)}}p(x)\leq |A_\epsilon^{(n)}|2^{-n(H(X_1)-\epsilon)}\)，因此序列个数有下界\((1-\epsilon)2^{n(H(X_1)-\epsilon)}\)。这说明，有极大的概率典型集中的序列个数就分布在\(2^{nH(X_1)}\)附近。

数据的压缩编码：熵的意义

在定义熵的时候，我们只能大概感受到熵在刻画平均意义下编码一个随机变量所需要的位数。在当时，这种理解其实还并不具有数学基础。通过渐进均分性，我们能够更清晰的看到熵的意义。

对于随机变量\(X\)，我们可以采用下面这样的一种相当简单粗暴的编码方式。这种编码方式绝对不一定是最优的，但它反映出了熵在描述的事实。我们取足够多的相同的\(X\)形成一列独立同分布的随机变量列\(X_1,X_2,\cdots\)。对于足够大的\(n\)，根据渐进均分性，我们知道绝大多数序列都会出现在典型集中。典型集中的序列个数有极大的概率在\(2^{nH(X)}\)左右。而所有可能的序列个数共为\(|\mathcal{X}|^n\)。现在我们要给每个序列一个编码，使得编码尽可能短，但又能和序列间形成双射。我们先对典型集中的序列依次编码，由于总个数为\(2^{nH(X)}\)，所以二进制编码需要至少\(nH(X)\)。为了处理小数向上取整的情况，我们加上1，也就是说极大概率下\(nH(X)+1\)就能完成典型集内的编码。而典型集外的序列无论如何也不超过\(|\mathcal{X}|^n\)个，因此编码所需要的位数为\(n\log |\mathcal{X}|+1\)。为了区分典型集内与典型集外的序列，我们附加上一个标识为。这样，我们就用\(nH(X)+2\)位编码了典型集内的序列，用\(n\log |\mathcal{X}|+2\)编码了典型集外的序列。在这样的编码下，期望意义上一个长度为\(n\)的序列是多少位的呢？\(\E[l(X^n)]=\sum\limits_{x^n}p(x^n)l(x^n)\)\(=(1-\epsilon)(nH(X)+2)+\epsilon(n\log |\mathcal{X}|+2)\)\(=nH(X)+2+\epsilon n(\log|\mathcal{X}|-H(X))\)\(\leq n[H(X)+\dfrac{2}{n}+\epsilon\log |\mathcal{X}|]\)。可见当\(n\)充分大时，存在一个可以充分小的\(\epsilon'\)使得\(\E[l(X^n)]\leq n(H(X)+\epsilon')\)。这也说明如果仅对一个随机变量\(X\)编码，所需要的位数不超过\(H(X)+\epsilon'\)。——熵刻画了给一个随机变量做最优编码所需要的位数的一个上界！