典型系列：長い系列では驚きが平均にそろう

相対エントロピーから情報と物理を組み立てる　第1部 第2章 §1.2.3　★★★ 独立同分布の系列では、1文字あたりの驚きが大数の法則で $H$ に集まる。これが漸近等分配性

1文字あたりの驚き

分布 $p$ から独立に $n$ 個取った系列 $X^n=(X_1,\dots,X_n)$ を考える。値の系列を $x^n=(x_1,\dots,x_n)\in\mathcal X^n$ と書く（右肩の $n$ は冪でなく系列の長さを表す）。独立なので系列の確率は積

$$p^n(x^n)=\prod_{i=1}^np(x_i)$$

になり、系列の驚きは各文字の驚きの和 $-\ln p^n(x^n)=\sum_i(-\ln p(x_i))$ になる。和を $n$ で割った1文字あたりの驚き

$$-\frac1n\ln p^n(X^n)=\frac1n\sum_{i=1}^n\bigl(-\ln p(X_i)\bigr)\tag{1.2.10}$$

は、独立同分布の確率変数 $-\ln p(X_i)$ の標本平均である。その期待値は $H(X)$、分散は

$$\sigma_s^2=\mathrm{Var}\bigl(-\ln p(X)\bigr)=\sum_xp(x)(\ln p(x))^2-H(X)^2\tag{1.2.11}$$

で、$\mathcal X$ が有限なので有限である。標本平均の分散は $\sigma_s^2/n$ になる。

証明

式 (1.2.10) は平均 $H(X)$、分散 $\sigma_s^2/n$ の確率変数なので、Chebyshev の不等式 $\Pr(\lvert Z-\langle Z \rangle \rvert >\epsilon)\le\mathrm{Var}(Z)/\epsilon^2$ をそのまま当てはめればよい。

定理の中身は大数の弱法則そのものである。新しいのは、標本平均を取る量が「各文字の驚き」という分布自身から作った量であることで、そのため結論が系列の確率についての主張になる。式 (1.2.12) の括弧の中を書き直すと、確率が $1$ に近い系列 $x^n$ について

$$\mathrm{e}^{-n(H+\epsilon)}\le p^n(x^n)\le\mathrm{e}^{-n(H-\epsilon)}\tag{1.2.13}$$

が成り立つ。実際に出てくる長い系列は、1文字あたり $\epsilon$ の幅の範囲で、どれもほぼ同じ確率 $\mathrm{e}^{-nH}$ を持つ。確率がほぼ等しく分配されるので、この性質を漸近等分配性（asymptotic equipartition property、AEP）と呼ぶ。

歴史を述べておく。Shannon (1948) は独立な情報源と Markov 情報源についてこの性質を示し（前掲論文の定理 3）、McMillan は定常でエルゴード的な情報源へ広げて「漸近等分配性」の名を与えた（B. McMillan (1953), Annals of Mathematical Statistics 24, 196–219）。Breiman は収束を確率収束からほとんど確実な収束へ強めた（L. Breiman (1957), Annals of Mathematical Statistics 28, 809–811）。この章では独立同分布の場合だけを扱う。

典型集合

2値の場合に具体的に書く。$\mathcal X=\{0,1\}$、$p(1)=p$ とし、系列に含まれる $1$ の個数を $k$ とすると $p^n(x^n)=p^k(1-p)^{n-k}$ なので

$$-\frac1n\ln p^n(x^n)-h_{\mathrm b}(p)=\Bigl(\frac kn-p\Bigr)\ln\frac{1-p}{p}\tag{1.2.14}$$

となる。典型系列とは、$1$ の割合 $k/n$ が $p$ から $\epsilon/\lvert \ln((1-p)/p)\rvert$ 以内にある系列のことである。$p=0.1$、$\epsilon=0.05$ nat では$\ln9\approx2.197$ で割って $\lvert k/n-0.1\rvert \le0.0228$ になる。