总结

AEP。 “几乎所有的事件都同样令人惊讶。”具体地，若，\(X_1,X_2,\dots)是服从p(x)的i.i.d，那么

\[-\frac{1}{n}\text{log}\ p(X_1,X_2,\dots,X_n)\rightarrow H(X)\quad\text{in probability.}\tag{3.28}\]

定义。 典型集\(A_{\epsilon}^{(n)}\)是序列\(x_1,x_2,\dots,x_n\)的集合，其满足

\[2^{-n(H(X) + \epsilon)} \le p(x_1,x_2,\dots,x_n)\le 2^{-n(H(X) -\epsilon)}.\tag{3.29}\]

典型集的特性

1. 若\((x_1,x_2,\dots,x_n)\in A_{\epsilon}^{(n)}\)，那么\(p(x_1,x_2,\dots,x_n) = 2^{-n(H\pm\epsilon)}\)。
2. \(Pr\{A_{\epsilon}^{(n)}\} \gt 1 - \epsilon\)，对于足够大的n。
3. \(|A_{\epsilon}^{(n)} \le 2^{n(H(X) + \epsilon)}\)，其中|A|表示集合A中元素的数量。

定义。 \(a_n \dot{=} b_n\)意味着\(\frac{1}{n}\ \text{log}\ \frac{a_n}{b_n} \rightarrow 0\)，随着\(n\rightarrow\infty\)。

最小可能集 设\(X_1,X_2,\dots,X_n\)为服从p(x)的i.i.d，且对于\(\delta \lt \frac{1}{2}\)，\(B_{\delta}^{(n)}\subset \mathcal{X}^n\)为最小集，使得\(Pr\{B_{\delta}^{(n)}\}\ge 1 - \delta\)。那么

\[|B_{\delta}^{(n)} \dot{=} 2^{nH}.\tag{3.30}\]