型：経験分布と真の分布を比べる

相対エントロピーから情報と物理を組み立てる　第1部 第8章 §1.8.1　★★★ 系列を経験分布（型）でまとめると、確率は $\mathrm{e}^{-n(H+D)}$ と書ける。章全体の計算はこの式から出る

大数の法則は、硬貨を $n$ 回投げれば表の割合が $1/2$ に近づくと言う。中心極限定理は、そのずれが $1/\sqrt n$ の大きさで Gauss 分布に従うと言う。どちらも「よく起きること」の記述である。この章では逆に、表の割合が $0.7$ を超えるような「めったに起きないこと」の確率を問う。その確率は $n$ とともに指数関数的に小さくなり、指数の係数（減り方の速さ）が相対エントロピー $D(p\,\|\,q)$ になる。これがこの章の結論で、大偏差（large deviation）の理論と呼ばれる。

この巻の章の型に沿って言えば、この章で比べる2つの分布は、観測した系列の経験分布 $p$ と、系列が従うと仮定する真の分布 $q$ である。当てる性質は $D$ の非負性・凸性と、指数型の分布族に対する Pythagoras の恒等式の3つである。出てくるものは次の4つになる。第一に、経験分布が $p$ になる確率は $\mathrm{e}^{-nD(p\|q)}$ で、これを集合に広げたものが Sanov の定理である（1.8.1節・1.8.2節）。第二に、標本平均の大偏差の指数は対数積率母関数の Legendre 変換で、これが Cramér の定理である（1.8.3節）。第三に、めったに起きないことが起きたと知ったとき、1個の標本の分布は指数型に傾いた分布（統計力学の Gibbs 分布と同じ形）になる。これが条件付き極限定理で、微視的カノニカル分布からカノニカル分布が出る理由はこの定理で説明できる（1.8.4節）。第四に、2つの仮説を見分ける検定の第2種の誤りは $\mathrm{e}^{-nD(p_0\|p_1)}$ で減り、これが Stein の補題である（1.8.5節）。

前の章までの結果を次の形で使う。相対エントロピーの定義・非負性・凸性は 第1部第3章、データ処理不等式は 第1部第4章、典型系列は 第1部第2章、Fisher 情報 $J(\theta)$ と $D(p_\theta\,\|\,p_{\theta+\delta})\approx\frac12J(\theta)\delta^2$ は 第1部第7章 で示した。この章でも対数は自然対数で、情報量の単位は nat である。

記号を1つ決めておく。2つの正の数列 $a_n$, $b_n$ について、$\frac1n\ln\frac{a_n}{b_n}\to0$（$n\to\infty$）のとき $a_n\doteq b_n$ と書き、「指数の係数で一致する」と読む。$a_n\doteq\mathrm{e}^{-nc}$ は「$a_n$ はおおよそ $\mathrm{e}^{-nc}$ の速さで $0$ に近づく」を意味し、$n^{10}$ のような多項式の因子の違いは無視される。

経験分布と型のクラス

有限の集合 $\mathcal X$（大きさ $\lvert \mathcal X\rvert$）に値をとる確率変数 $X_1,\dots,X_n$ が、互いに独立に同じ分布 $q$ に従うとする。観測した系列を $x^n=(x_1,\dots,x_n)$ と書くと、その確率は $q^n(x^n)=\prod_{i=1}^nq(x_i)$ である。

たとえば $\mathcal X=\{\text{表},\text{裏}\}$、$n=10$ で表が3回出た系列の型は $p=(0.3,0.7)$ で、$T_{10}(p)$ はそういう系列 $\binom{10}{3}=120$ 本の集まりである。型は系列の「順番を忘れて回数だけを残したもの」で、独立同分布の系列の確率は回数だけで決まるので、型だけで計算が済む。型の個数は少ない。各記号の回数は $0$ から $n$ までの $n+1$ 通りなので、

$$\lvert \mathcal P_n\rvert \le(n+1)^{\lvert \mathcal X\rvert }\tag{1.8.2}$$

が成り立つ。系列の本数 $\lvert \mathcal X\rvert ^n$ が $n$ について指数関数的に増えるのに対して、型の個数は多項式でしか増えない。この差が以下の議論のすべての出発点になる。

型で書いた系列の確率

式 (1.8.3) の2つの項は別々の意味を持つ。$H(p)$ は型 $p$ の系列が何本あるか（$\mathrm{e}^{nH(p)}$ 本）を数え、$D(p\|q)$ は真の分布 $q$ から見てその型がどれだけ「ありそうにないか」を測る。型のクラス全体の確率では本数の因子 $\mathrm{e}^{nH(p)}$ と1本の確率の因子 $\mathrm{e}^{-nH(p)}$ が打ち消し合い、$D$ だけが残る。$D(p\|q)=0$ となる型は $p=q$ だけなので、$q$ から離れた型のクラスの確率は指数関数的に小さくなる。これが大数の法則の「指数関数的に強い」版で、第1部第2章 の典型系列の議論を、型ごとに細かく分けたものになっている。

図 1.8.1　公平な硬貨（$q=(0.5,0.5)$）で表の割合が $0.7$ の型のクラスの確率の指数。丸印は $\binom{n}{0.7n}2^{-n}$ から計算した厳密な値で、点線の $D(p\|q)$ に $\mathcal{O}(\ln n/n)$ の差で近づく。