Sanovの定理(Sanov's theorem)とは、独立同分布の標本の経験分布が分布の集合 $\Gamma$ に入る確率が、$n$ について $\exp(-n\inf_{Q\in\Gamma}D(Q\|P))$ の速さで小さくなることを述べる大偏差の定理である。率は Kullback–Leibler ダイバージェンスで与えられ、標本平均についての Cramér の定理はその像にあたる。有限集合の場合は経験分布で系列を分類する方法の型で証明でき、凸集合の事象を条件にすると経験分布はダイバージェンスの最小点に近づく。
前提知識: Kullback–Leiblerダイバージェンス, エントロピー, 大数の法則, Cramérの定理(大偏差)
Sanov の定理(Sanov's theorem)は、標本の経験分布が真の分布から離れた分布の集まりに入る確率の、指数の割合を述べる定理である。割合は Kullback–Leiblerダイバージェンス で与えられる。
たとえば、公平なさいころを $n$ 回振って、目の平均が $4$ 以上になったとする。これは起こりにくい事象である。その確率はどれだけ小さいか。また、そのような稀な事象が起きたとき、各目はどんな割合で出ているのか。大数の法則 により、目の出た割合の分布(経験分布)は真の分布に近づくが、Sanov の定理は「別の分布 $Q$ に見える確率」がおよそ $e^{-nD(Q\|P)}$ であることを述べる。稀な事象の中では、$D(Q\|P)$ が最も小さい $Q$ が支配する。
Cramérの定理(大偏差) は標本平均という 1 つの実数の大偏差を扱う。Sanov の定理は経験分布そのものの大偏差で、標本平均の場合はその像にあたる。
この記事では、有限の値をとる場合に次を示す。
この記事を通して、$\mathcal X$ を $d\ge2$ 個の元からなる有限集合とし、$\mathcal P$ を $\mathcal X$ の上の確率分布全体とする。$\mathcal P$ は $\mathbb{R}^{\mathcal X}$ の部分集合として位相を入れる。対数は自然対数とする。$Q\in\mathcal P$ の エントロピー を $H(Q):=-\sum_xQ(x)\log Q(x)$ とする($0\log0=0$)。ダイバージェンス $D(Q\|P)$ は Kullback–Leiblerダイバージェンス の定義のとおりで、$Q$ の台が $P$ の台に含まれないとき $\infty$ である。$\operatorname{supp}Q:=\{x\mid Q(x)>0\}$ とする。
系列 $x=(x_1,\dots,x_n)\in\mathcal X^n$ の 経験分布 を
$$
L_x(a):=\frac{\lvert\{i\mid x_i=a\}\rvert}{n}\qquad(a\in\mathcal X)
$$
と定める。系列の経験分布として現れる分布を $n$-型($n$ 次の型)といい、その全体を $\mathcal T_n\subset\mathcal P$ とする。$Q\in\mathcal T_n$ について、$L_x=Q$ となる系列の全体 $T(Q)$ を 型の類 という。
$Q\in\mathcal P$ が $n$-型であることは、すべての $nQ(a)$ が整数であることと同値である。
方法の型 の要点は、$\mathcal X^n$ の元は指数的に多いが、型の個数は $n$ の多項式でしかないことである。確率の和を調べるには、型の類ごとに分けて、最大の項だけを見ればよい。
$\lvert\mathcal T_n\rvert\le(n+1)^{d-1}$ である。
$Q\in\mathcal T_n$ は $d-1$ 個の元での値 $nQ(a)\in\{0,1,\dots,n\}$ で決まる。残りの 1 つの値は和が $1$ であることから定まる。$\square$
$P\in\mathcal P$、$Q\in\mathcal T_n$、$x\in T(Q)$ とし、$P^n$ を $P$ の $n$ 個の積の分布とする。このとき
$$
P^n(x)=\exp\bigl(-n(H(Q)+D(Q\|P))\bigr)
$$
である($D(Q\|P)=\infty$ のときは右辺を $0$ とする)。とくに $Q^n(x)=e^{-nH(Q)}$ である。
$D(Q\|P)=\infty$ なら、$P(a)=0$ で $Q(a)>0$ となる $a$ が $x$ に現れるので $P^n(x)=0$ である。そうでなければ、文字 $a$ は $x$ の中に $nQ(a)$ 回現れるから
$$
\log P^n(x)=n\sum_{a\in\operatorname{supp}Q}Q(a)\log P(a)=n\sum_{a\in\operatorname{supp}Q}Q(a)\Bigl(\log Q(a)-\log\frac{Q(a)}{P(a)}\Bigr)=-n\bigl(H(Q)+D(Q\|P)\bigr)
$$
である。$\square$
$Q\in\mathcal T_n$ について
$$
(n+1)^{-(d-1)}e^{nH(Q)}\le\lvert T(Q)\rvert\le e^{nH(Q)}
$$
である。
lem-sanov-prob より $Q^n(T(Q))=\lvert T(Q)\rvert e^{-nH(Q)}$ である。これが $1$ 以下であることから上からの評価が出る。
下からの評価には、$Q^n(T(Q))\ge Q^n(T(R))$ がすべての $R\in\mathcal T_n$ で成り立つことを示す。$\operatorname{supp}R\not\subset\operatorname{supp}Q$ なら右辺は $0$ である。$\operatorname{supp}R\subset\operatorname{supp}Q$ とする。$\lvert T(Q)\rvert=n!/\prod_a(nQ(a))!$ だから、$k_a:=nQ(a)$、$l_a:=nR(a)$ とおいて
$$
\frac{Q^n(T(Q))}{Q^n(T(R))}=\prod_{a\in\operatorname{supp}Q}\frac{l_a!}{k_a!}\,Q(a)^{k_a-l_a}
$$
である。整数 $l\ge0$、$k\ge1$ について $l!/k!\ge k^{l-k}$ である($l\ge k$ なら $l!/k!=(k+1)\cdots l\ge k^{l-k}$、$l< k$ なら $k!/l!=(l+1)\cdots k\le k^{k-l}$ による)。$k_a=nQ(a)$ を代入すると
$$
\frac{Q^n(T(Q))}{Q^n(T(R))}\ge\prod_{a\in\operatorname{supp}Q}\bigl(nQ(a)\bigr)^{l_a-k_a}Q(a)^{k_a-l_a}=\prod_{a\in\operatorname{supp}Q}n^{l_a-k_a}=1
$$
である。最後は $\sum_a l_a=\sum_a k_a=n$ による。
$Q^n(T(R))$ を $R\in\mathcal T_n$ について足すと $1$ なので、最大の項について $Q^n(T(Q))\ge1/\lvert\mathcal T_n\rvert\ge(n+1)^{-(d-1)}$ である(lem-sanov-count)。$Q^n(T(Q))=\lvert T(Q)\rvert e^{-nH(Q)}$ と合わせて、下からの評価を得る。$\square$
$P\in\mathcal P$、$Q\in\mathcal T_n$ について
$$
(n+1)^{-(d-1)}e^{-nD(Q\|P)}\le P^n(T(Q))\le e^{-nD(Q\|P)}
$$
である。
実際、$P^n(T(Q))=\lvert T(Q)\rvert\cdot e^{-n(H(Q)+D(Q\|P))}$ に lem-sanov-class を使えばよい。
$X_1,X_2,\dots$ を互いに独立で同じ分布 $P\in\mathcal P$ に従う $\mathcal X$ 値の確率変数とし、$L_n:=L_{(X_1,\dots,X_n)}$ を経験分布とする。$L_n$ は $\mathcal P$ の値をとる確率変数である。$\Gamma\subset\mathcal P$ について $D(\Gamma\|P):=\inf_{Q\in\Gamma}D(Q\|P)$ とおく($\inf\emptyset=\infty$)。$\operatorname{int}\Gamma$ は $\mathcal P$ での内部である。確率が $0$ のときは $\log0=-\infty$ とする。
任意の $\Gamma\subset\mathcal P$ について次が成り立つ。
(1) すべての $n\ge1$ で $\Pr(L_n\in\Gamma)\le(n+1)^{d-1}e^{-nD(\Gamma\|P)}$ である。
(2) $\displaystyle\limsup_{n\to\infty}\frac1n\log\Pr(L_n\in\Gamma)\le-D(\Gamma\|P)$ である。
(3) $\displaystyle\liminf_{n\to\infty}\frac1n\log\Pr(L_n\in\Gamma)\ge-D(\operatorname{int}\Gamma\|P)$ である。
とくに $D(\operatorname{int}\Gamma\|P)=D(\Gamma\|P)$ なら
$$
\lim_{n\to\infty}\frac1n\log\Pr(L_n\in\Gamma)=-D(\Gamma\|P)
$$
である。
$P$ の台が $\mathcal X$ 全体なら $D(\cdot\|P)$ は $\mathcal P$ の上で連続なので、$\Gamma$ が $\operatorname{int}\Gamma$ の閉包に含まれれば極限の式が成り立つ。とくに $\Gamma$ が開集合ならよい。
率を与えるのは $D(Q\|P)$ であって $D(P\|Q)$ ではない。$P$ のもとで $Q$ に見える確率を問うているからである。lem-sanov-prob の計算で、対数の重み $Q(a)$ は型の側から来る。
$\Gamma=\{Q\mid D(Q\|P)>c\}$ とすれば、(1) から $\Pr(D(L_n\|P)>c)\le(n+1)^{d-1}e^{-nc}$ を得る。これと Kullback–Leiblerダイバージェンス の定理「Pinsker の不等式」から、$L_n$ が $P$ に近づく確率の評価が $n$ を固定したまま得られる。
$f\colon\mathcal X\to\mathbb{R}$ について、$Q(f):=\sum_xQ(x)f(x)$ とおく。標本平均は経験分布の線形な関数である。
$$
\frac1n\sum_{i=1}^nf(X_i)=L_n(f)
$$
よって標本平均の大偏差は、半空間 $\{Q\mid Q(f)\ge a\}$ についての Sanov の定理である。$\theta\in\mathbb{R}$ について
$$
\Lambda(\theta):=\log\sum_xP(x)e^{\theta f(x)},\qquad P_\theta(x):=P(x)e^{\theta f(x)-\Lambda(\theta)}
$$
とおく。$P_\theta$ は $P$ を 指数関数で傾けた分布 である。
$P$ の台が $\mathcal X$ 全体で $P(f)< a<\max f$ のとき、$\operatorname{int}\Gamma$ には $\{Q\mid Q(f)>a\}$ が含まれる。そこでの下限は連続性から $I(a)$ に等しい。よって thm-sanov-main は、値が有限個の場合の Cramér の定理
$$
\lim_{n\to\infty}\frac1n\log\Pr\Bigl(\frac1n\sum_{i=1}^nf(X_i)\ge a\Bigr)=-I(a)
$$
を再び与える。Cramérの定理(大偏差) の傾けた分布は、ここでは $D(\cdot\|P)$ を最小にする分布として現れる。
凸集合の上の最小点には、幾何的な不等式がある。
$\Gamma\subset\mathcal P$ を凸集合とし、$Q^*\in\Gamma$ が $D(\cdot\|P)$ の $\Gamma$ での最小点で、$D(Q^*\|P)<\infty$ とする。すべての $Q\in\Gamma$ について
$$
D(Q\|P)\ge D(Q\|Q^*)+D(Q^*\|P)
$$
である。
$D(Q\|P)=\infty$ なら明らかなので、有限とする。$t\in[0,1]$ について $Q_t:=(1-t)Q^*+tQ\in\Gamma$、$\phi(t):=D(Q_t\|P)$ とおく。$\phi$ は有限で、$\phi(t)\ge\phi(0)$ である。
$\operatorname{supp}Q\subset\operatorname{supp}Q^*$ を示す。$Q(a)>0=Q^*(a)$ となる $a$ があるとする。$Q_t(a)=tQ(a)$ で、対応する項 $tQ(a)\log(tQ(a)/P(a))$ を $t$ で割ると $t\to0$ で $-\infty$ に発散する。$Q^*(a)>0$ の項は $t=0$ で微分可能で、$Q^*(a)=Q(a)=0$ の項は $0$ である。よって $(\phi(t)-\phi(0))/t\to-\infty$ となり、$\phi(t)\ge\phi(0)$ に反する。
したがって $\phi$ は $t=0$ で右微分可能である。$\sum_a(Q(a)-Q^*(a))=0$ を使うと
$$
\phi'(0)=\sum_a\bigl(Q(a)-Q^*(a)\bigr)\Bigl(\log\frac{Q^*(a)}{P(a)}+1\Bigr)=\sum_aQ(a)\log\frac{Q^*(a)}{P(a)}-D(Q^*\|P)
$$
である。和は $\operatorname{supp}Q^*$ の上でとる。$\phi'(0)\ge0$ であり、
$$
D(Q\|P)-D(Q\|Q^*)=\sum_aQ(a)\log\frac{Q^*(a)}{P(a)}
$$
だから主張が従う。$\square$
$\Gamma\subset\mathcal P$ を閉じた凸集合とし、$D(\operatorname{int}\Gamma\|P)=D(\Gamma\|P)<\infty$ とする。このとき $D(\cdot\|P)$ の $\Gamma$ での最小点 $Q^*$ はただ 1 つである。$\delta$ を全変動距離とすると、すべての $\varepsilon>0$ について、$n\to\infty$ で
$$
\Pr\bigl(\delta(L_n,Q^*)\ge\varepsilon\bigm|L_n\in\Gamma\bigr)\to0
$$
であり、この確率は指数関数的に小さくなる。さらに、すべての $a\in\mathcal X$ で $\Pr(X_1=a\mid L_n\in\Gamma)\to Q^*(a)$ である。
$D(\cdot\|P)$ は下半連続で $\Gamma$ はコンパクトなので、最小点 $Q^*$ が存在する。$D_*:=D(Q^*\|P)$ とする。別の最小点 $Q$ があれば、lem-sanov-pythagoras より $D_*\ge D(Q\|Q^*)+D_*$ となり、$Q=Q^*$ である。
$\Gamma_\varepsilon:=\{Q\in\Gamma\mid\delta(Q,Q^*)\ge\varepsilon\}$ とする。$Q\in\Gamma_\varepsilon$ なら、lem-sanov-pythagoras と Pinsker の不等式 $D(Q\|Q^*)\ge2\delta(Q,Q^*)^2$ から $D(Q\|P)\ge D_*+2\varepsilon^2$ である。thm-sanov-main の (1) より
$$
\Pr(L_n\in\Gamma_\varepsilon)\le(n+1)^{d-1}e^{-n(D_*+2\varepsilon^2)}
$$
である。同じ定理の (3) と仮定から、大きな $n$ で $\Pr(L_n\in\Gamma)\ge e^{-n(D_*+\varepsilon^2)}$ である。割ると、条件つき確率は $(n+1)^{d-1}e^{-n\varepsilon^2}$ 以下である。
事象 $\{L_n\in\Gamma\}$ は $X_1,\dots,X_n$ の入れかえで変わらないので、$\Pr(X_i=a\mid L_n\in\Gamma)$ は $i$ によらない。よって、$i$ について平均すると
$$
\Pr(X_1=a\mid L_n\in\Gamma)=E\bigl[L_n(a)\bigm|L_n\in\Gamma\bigr]
$$
である。前半と $0\le L_n(a)\le1$ から、右辺は $Q^*(a)$ に近づく。$\square$
この定理は Gibbs の条件づけの原理 とも呼ばれる形の、有限集合の場合である。稀な事象を条件にすると、個々の標本の分布は元の $P$ ではなく、$P$ に最も近い $\Gamma$ の元になる。
$\mathcal X=\{1,\dots,6\}$、$P$ を一様分布、$f(x)=x$、$\Gamma=\{Q\mid Q(f)\ge4\}$ とする。$P(f)=7/2<4$ である。prop-sanov-gibbs により、最小点は $Q^*(x)\propto e^{\theta x}$ の形で、$\theta\approx0.17463$ のとき平均が $4$ になる。
| 目 | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
|---|---|---|---|---|---|---|
| $Q^*$ | $0.1031$ | $0.1227$ | $0.1461$ | $0.1740$ | $0.2072$ | $0.2468$ |
$D(Q^*\|P)\approx0.04325$ である。和の分布を正確に計算すると、$-\frac1n\log\Pr(L_n(f)\ge4)$ は $n=100,\ 500,\ 2000$ で約 $0.0631,\ 0.0487,\ 0.0450$ で、$0.04325$ に近づく。$n=300$ で平均が $4$ 以上という条件のもとでの 1 回目の目の分布は約 $(0.1010,0.1213,0.1455,0.1743,0.2086,0.2493)$ で、$Q^*$ に近い。大きな目が一度だけ極端に出るのではなく、全体の分布が滑らかに傾くことが分かる。
$\mathcal X$ を Polish空間、$P$ を $\mathcal X$ の上の Borel 確率測度、$\mathcal P(\mathcal X)$ を Borel 確率測度全体に弱収束の位相を入れた空間とする。$X_1,X_2,\dots$ を互いに独立で分布 $P$ に従う確率変数とし、$L_n:=\frac1n\sum_{i=1}^n\delta_{X_i}$ とする。$D(Q\|P)$ は、$Q\ll P$ なら $\int\log\frac{dQ}{dP}\,dQ$、そうでなければ $\infty$ とする。$\Gamma\subset\mathcal P(\mathcal X)$ が Borel 集合で
$$
\inf_{Q\in\operatorname{int}\Gamma}D(Q\|P)=\inf_{Q\in\operatorname{cl}\Gamma}D(Q\|P)
$$
を満たすなら、$\frac1n\log\Pr(L_n\in\Gamma)$ はこの値の符号を変えたものに収束する。
この定理はこの記事では証明しない。経験分布が弱位相で大偏差原理を満たすことが BOPR22 Theorem 1.1 にあり、率の形は同じ文献の Lemma 2.3 による。上の極限の式はその上下の評価から従う。条件の形は PW25 §15.5、Theorem 15.13 のあとの注にある。どちらの文献も Dembo–Zeitouni の大偏差の教科書の Theorem 6.2.10 を挙げている。型の個数の議論はそのままでは使えないので、有限の分割で粗くして有限の場合に帰着する。thm-sanov-main の (2) と違って、上からの評価には閉包が要る(下の表の 3 行目)。
| 外す条件・誤った読み方 | 反例 | 何が起こるか |
|---|---|---|
| $X_i$ が互いに独立 | すべての $i$ で $X_i=X_1$、$X_1$ は $\{0,1\}$ の一様分布、$\Gamma=\{Q\mid Q(1)\ge0.6\}$ | $\Pr(L_n\in\Gamma)=\frac12$ で、指数的に小さくならない |
| $D(\operatorname{int}\Gamma\Vert P)=D(\Gamma\Vert P)$ | $P$ は $\{0,1\}$ の一様分布、$\Gamma=\{Q\mid Q(1)\text{ は無理数}\}$ | $D(\Gamma\Vert P)=0$ だが $\Pr(L_n\in\Gamma)=0$ |
| $\mathcal X$ が有限(閉包なしの上の評価) | $\mathcal X=[0,1]$、$P$ は Lebesgue 測度、$\Gamma$ は有限個の点に台をもつ分布の全体 | $\Gamma$ の上で $D\equiv\infty$ だが $\Pr(L_n\in\Gamma)=1$ |
| 確率そのものが $e^{-nD}$ に等しい | $P$ は $\{0,1\}$ の一様分布、$\Gamma=\{P\}$、$n$ は偶数 | $D=0$ だが $\Pr(L_n=P)\sim\sqrt{2/(\pi n)}$。指数の割合だけが定まる |
| 率は $D(P\Vert Q)$ である | $P$ は $\{0,1\}$ の一様分布、$\Gamma=\{\delta_1\}$ | $\Pr(L_n=\delta_1)=2^{-n}$ で率は $D(\delta_1\Vert P)=\log2$。$D(P\Vert\delta_1)=\infty$ |
1 行目は $L_n=\delta_{X_1}$ から分かる。残りは次のとおりである。
2 行目:$L_n(1)$ は有理数なので $\Pr(L_n\in\Gamma)=0$ である。無理数 $q\to\frac12$ をとれば $D\to0$ なので $D(\Gamma\|P)=0$ である。$\operatorname{int}\Gamma=\emptyset$ なので、thm-sanov-main の (3) は何も述べず、定理とは矛盾しない。
3 行目:$L_n$ はいつも有限個の点に台をもつ。そのような $Q$ は $P$ に絶対連続でないので $D(Q\|P)=\infty$ である。有限集合の場合の評価 (1) に当たる不等式は成り立たない。$\Gamma$ の弱位相での閉包は全体なので、thm-sanov-polish の仮定は満たされず、定理とは矛盾しない。
4 行目:$n=2m$ なら $\Pr(L_n=P)=\binom{2m}{m}2^{-2m}$ で、Stirlingの公式 から $\sim1/\sqrt{\pi m}$ である。これは cor-sanov-type の評価の範囲に入る。
5 行目:$L_n=\delta_1$ はすべての $X_i$ が $1$ である事象である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する