渐近均分性定理
渐进均分性在如下定理中形式化。
定理 3.1.1 （AEP） 若\(X_1,X_2,\dots\)是服从p(x)的独立同分布，那么
\[-\frac{1}{n}\text{log}\ p(X_1,X_2,\dots,X_n) \rightarrow H(X)\quad \text{in probability.} \tag{3.2}\]
证明：独立随机变量的函数也是独立随机变量。因此，由于\(X_i\)是i.i.d，所以\(\text{log}\ p(X_i)\)也是。因此，通过弱大数定律，
\begin{align} -\frac{1}{n}\ \text{log}\ p(X_1,X_2,\dots,X_n) &= -\frac{1}{n}\sum_i \text{log}\ p(X_i)\tag{3.3}\\ &\rightarrow -E\ \text{log}\ p(X)\quad\text{in probability}\tag{3.4}\\ & = H(X), \tag{3.5} \end{align}
定理得到证明。
定义 服从于\(p(x)\)的典型集\(A_{\epsilon}^{(n)}\)是序列\(x_1,x_2,\dots,x_n)\in \mathcal{X}^n\)的集合，性质为
\[2^{-n(H(X) + \epsilon)} \le p(x_1,x_2,\dots,x_n)\le 2^{-n(H(X) - \epsilon)}.\tag{3.6}\]
作为AEP的结果，我们可以证明集合\(A_{\epsilon}^{(n)}\)具有如下性质：
定理 3.1.2
- 若\(x_1,x_2,\dots,x_n)\in A_{\epsilon}^{(n)}\)，那么\(H(X) - \epsilon \le -\frac{1}{n}\ \text{log}\ p(x_1,x_2,\dots,x_n) \le H(X) + \epsilon\)。
- \(Pr\{A_{\epsilon}^{(n)}\} \gt 1-\epsilon\)，对于n足够大时。
- \(|A_{\epsilon}^{(n)}| \le 2^{n(H(X) + \epsilon)}\)，其中|A|表示集合A中元素数量。
- \(|A_{\epsilon}^{(n)}| \ge (1-\epsilon)2^{n(H(X) - \epsilon)}\)，对于足够大的n。
因此，典型集概率近乎1，典型集的全部元素几乎等可能，且典型集中元素数量接近\(2^{nH}\)。
证明：性质(1)的证明直接来自\(A_{\epsilon}^{(n)}\)的定义。 第二个性质直接遵从定理3.1.1，由于事件\((X_1,X_2,\dots,X_n) \in A_{\epsilon}^{(n)}\)的概率趋近1，随着\(n\rightarrow \infty\)。因此，对于任意\(\delta \gt 0\)，存在\(n_0\)使得，对于所有\(n\ge n_0\)，有
\[Pr\Big\{\big|-\frac{1}{n}\ \text{log}\ p(X_1,X_2,\dots,X_n) - H(X)\big| \lt \epsilon\Big\} \gt 1 - \delta.\tag{3.7}\]
设置\(\delta = \epsilon\)，我们得到定理的第二部分。\(\delta = \epsilon\)的相等将方便简化稍后的符号。
为证明性质（3），我们记
\begin{align} 1 &= \sum_{x\in\mathcal{X}^n}p(\textbf{x}) \tag{3.8}\\ &\ge \sum_{x\in A_{\epsilon}^{(n)}}p(\textbf{x})\tag{3.9}\\ &\ge \sum_{x\in A_{\epsilon}^{(n)}} 2^{-n(H(X)} + \epsilon)\tag{3.10}\\ = 2^{-n(H(X) + \epsilon)}|A_{\epsilon}^{(n)}|, \tag{3.11} \end{align}
其中，第二个不等式来自（3.6）。因此 \[A_{\epsilon}^{(n)} \le 2^{n(H(X) + \epsilon)}. \tag{3.12}\]
最后，对于足够大的n，\(Pr\{A_{\epsilon}^{(n)}\} \ge 1 -\epsilon\)，那么 \begin{align} 1 - \epsilon &\le Pr\{A_{\epsilon}^{(n)}\} \tag{3.13}\\ &\le \sum_{x\in A_{\epsilon}^{(n)}} 2^{-n(H(X) -\epsilon)}\tag{3.14}\\ &= 2^{-n(H(X) - \epsilon)}|A_{\epsilon}^{(n)}|, \tag{3.15} \end{align}
其中，第二个不等式来自（3.6）。因此
\[|A_{\epsilon}^{(n)}| \ge (1-\epsilon)2^{n(H(X) - \epsilon)}, \tag{3.16}\]
完成\(A_{\epsilon}^{(n)}\)性质的证明。