Cramér の定理：標本平均の大偏差と Legendre 変換

相対エントロピーから情報と物理を組み立てる　第1部 第8章 §1.8.3　★★★ 平均を決めた集合への I 射影は指数型の分布で、指数は対数積率母関数の Legendre 変換になる

平均を決めた集合

物理でも統計でも、問いは多くの場合「ある量の標本平均が $a$ 以上になる確率」の形をとる。$f:\mathcal X\to\mathbb{R}$ を1つ決め、$\bar f_n=\frac1n\sum_{i=1}^nf(X_i)$ とおく。$\bar f_n=\sum_ap_{X^n}(a)f(a)=\langle f \rangle _{p_{X^n}}$ なので、「$\bar f_n\ge a$」は「型が $E_a=\{p:\langle f \rangle _p\ge a\}$ に入る」と同じである。$E_a$ は線形の不等式で決まる凸な閉集合なので、Sanov の定理がそのまま使え、残る仕事は $\min_{p\in E_a}D(p\|q)$ の計算になる。

そのための道具として、$q$ のもとでの対数積率母関数

$$\Lambda(\lambda)=\ln\langle \mathrm{e}^{\lambda f(X)} \rangle _q=\ln\sum_xq(x)\,\mathrm{e}^{\lambda f(x)}\qquad(\lambda\in\mathbb{R})\tag{1.8.9}$$

と、$q$ を $\mathrm{e}^{\lambda f}$ で傾けた指数型の分布

$$q_\lambda(x)=q(x)\,\mathrm{e}^{\lambda f(x)-\Lambda(\lambda)}\tag{1.8.10}$$

を用意する。$\Lambda$ は凸で、$\Lambda'(\lambda)=\langle f \rangle _{q_\lambda}$、$\Lambda''(\lambda)=\mathrm{Var}_{q_\lambda}(f)\ge0$ である。$\lambda=0$ では $q_0=q$ で、$\Lambda'(0)=\mu\coloneqq\langle f \rangle _q$、$\Lambda''(0)=\sigma^2\coloneqq\mathrm{Var}_q(f)$ になる。$\lambda$ を $0$ から増やすと $q_\lambda$ は $f$ の大きい記号へ重みを移し、平均 $\Lambda'(\lambda)$ は $f$ の最小値と最大値の間を単調に動く。

証明

式 (1.8.10) から $\ln\frac{p(x)}{q(x)}=\ln\frac{p(x)}{q_\lambda(x)}+\lambda f(x)-\Lambda(\lambda)$。両辺を $p$ で平均する。

この恒等式から、平均が $a$ の分布の中での $D(p\|q)$ の最小がすぐに出る。$\langle f \rangle _p=a$ なら $D(p\|q)\ge\lambda a-\Lambda(\lambda)$ がすべての $\lambda$ で成り立ち（$D(p\|q_\lambda)\ge0$ だから）、等号は $p=q_\lambda$ のときに限る。$\Lambda'(\lambda^*)=a$ となる $\lambda^*$ を選べば $q_{\lambda^*}$ 自身の平均が $a$ なので等号が実現し、

$$\min_{\langle f \rangle _p=a}D(p\|q)=\Lambda^*(a)\coloneqq\sup_{\lambda\in\mathbb{R}}\bigl(\lambda a-\Lambda(\lambda)\bigr)=\lambda^*a-\Lambda(\lambda^*)\tag{1.8.12}$$

を得る。$\Lambda^*$ は $\Lambda$ の Legendre 変換（Legendre–Fenchel 変換）で、レート関数と呼ばれる。最小を与える分布は指数型の分布 $q_{\lambda^*}$ で、平均が $a$ の分布 $p$ すべてについて式 (1.8.11) は$D(p\|q)=D(p\|q_{\lambda^*})+D(q_{\lambda^*}\|q)$ という Pythagoras の等式になる。

証明

上界（Chernoff の評価）：$\lambda\ge0$ について Markov の不等式から$q^n(\bar f_n\ge a)=q^n\bigl(\mathrm{e}^{\lambda\sum_if(X_i)}\ge\mathrm{e}^{n\lambda a}\bigr)\le\mathrm{e}^{-n\lambda a}\langle \mathrm{e}^{\lambda\sum_if(X_i)} \rangle =\mathrm{e}^{-n(\lambda a-\Lambda(\lambda))}$。$a>\mu$ では $\lambda a-\Lambda(\lambda)$ の上限は $\lambda\ge0$ の側でとるので、$\lambda$ について下限をとれば $\mathrm{e}^{-n\Lambda^*(a)}$ になる。

極限：$E_a$ は凸で、$a<f_{\max}$ なので内部の閉包に等しい。Sanov の定理から指数は $\min_{p\in E_a}D(p\|q)$ で、$\Lambda^*$ は $a>\mu$ で増加するので最小は境界 $\langle f \rangle _p=a$ の上にあり、式 (1.8.12) から $\Lambda^*(a)$ に等しい。

上界の証明は Sanov の定理を使わずに1行で済み、しかも多項式の因子がない。この評価は H. Chernoff の名で呼ばれる¹1H. Chernoff (1952), Ann. Math. Statist. 23, 493–507。下の脚注へ閉じる。極限の形の定理は H. Cramér による²2H. Cramér (1938), Actualités Scientifiques et Industrielles 736（Hermann, Paris）。英訳は H. Touchette による arXiv:1802.05988。下の脚注へ閉じる。Cramér の定理は $\mathcal X$ が有限でなくても、$\Lambda(\lambda)$ が $\lambda=0$ の近くで有限なら成り立つ。たとえば $f(X)$ が平均 $\mu$・分散 $\sigma^2$ の Gauss 分布に従うなら、$\Lambda(\lambda)=\mu\lambda+\frac12\sigma^2\lambda^2$、$\Lambda^*(a)=\frac{(a-\mu)^2}{2\sigma^2}$ である。

レート関数の形と中心極限定理

$\Lambda^*$ は凸で、$a=\mu$ で最小値 $0$ をとる。$\mu$ の近くで展開すると、Legendre 変換は2階微分を逆数にするので $\Lambda^{*\prime\prime}(\mu)=1/\Lambda''(0)=1/\sigma^2$、

$$\Lambda^*(a)=\frac{(a-\mu)^2}{2\sigma^2}+\mathcal{O}\bigl((a-\mu)^3\bigr)\tag{1.8.14}$$

となる。2次の項だけを残すと $q^n(\bar f_n\ge a)\approx\mathrm{e}^{-n(a-\mu)^2/(2\sigma^2)}$ で、これは中心極限定理の Gauss 分布の裾と指数の係数で一致する。中心極限定理は $a-\mu$ が $1/\sqrt n$ の大きさのずれを正しく扱うが、$a-\mu$ を $n$ によらず固定した大偏差では、3次以上の項が指数に入るので Gauss 分布の裾を使うことはできない。図 1.8.2 は、さいころの目の平均について2つを比べたものである。

1　H. Chernoff (1952), Ann. Math. Statist. 23, 493–507。

2　H. Cramér (1938), Actualités Scientifiques et Industrielles 736（Hermann, Paris）。英訳は H. Touchette による arXiv:1802.05988。