Sanovの定理

同義語:サノフの定理Sanov's theoremSanov theorem

概要

Sanovの定理(Sanov's theorem)とは、独立同分布の標本の経験分布が分布の集合 $\Gamma$ に入る確率が、$n$ について $\exp(-n\inf_{Q\in\Gamma}D(Q\|P))$ の速さで小さくなることを述べる大偏差の定理である。率は Kullback–Leibler ダイバージェンスで与えられ、標本平均についての Cramér の定理はその像にあたる。有限集合の場合は経験分布で系列を分類する方法の型で証明でき、凸集合の事象を条件にすると経験分布はダイバージェンスの最小点に近づく。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 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 の定理は経験分布そのものの大偏差で、標本平均の場合はその像にあたる。
この記事では、有限の値をとる場合に次を示す。

  • 方法の型(経験分布で系列を分類し数える方法)による定理の完全な証明(thm-sanov-main)。
  • 指数の傾きとの関係と、Cramér の定理の率関数との一致(prop-sanov-gibbs)。
  • 稀な事象を条件にしたときの経験分布の極限(thm-sanov-conditional)。
    Polish 空間の上の主張は最後に述べるが、証明はしない。

型と経験分布

この記事を通して、$\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$

1 つの系列の確率

$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 を使えばよい。

Sanov の定理

$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$ とする。

Sanov の定理(有限集合の場合)

任意の $\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) $$
である。

型の類ごとに足す
  1. $\Pr(L_n\in\Gamma)=\sum_{Q\in\Gamma\cap\mathcal T_n}P^n(T(Q))$ である。cor-sanov-type より各項は $e^{-nD(Q\|P)}\le e^{-nD(\Gamma\|P)}$ 以下で、項の数は lem-sanov-count より $(n+1)^{d-1}$ 以下である。
    1. の対数を $n$ で割る。$\frac{d-1}{n}\log(n+1)\to0$ である。
  2. $Q\in\operatorname{int}\Gamma$ で $D(Q\|P)<\infty$ となるものをとる(なければ主張は自明である)。$Q$ に近づく型の列 $Q_n\in\mathcal T_n$ で $\operatorname{supp}Q_n\subset\operatorname{supp}Q$ となるものを作る。$\operatorname{supp}Q$ の元について $nQ(a)$ の小数部分の和は $\lvert\operatorname{supp}Q\rvert$ より小さく、整数である。これを
    $$ r:=n-\sum_{a\in\operatorname{supp}Q}\lfloor nQ(a)\rfloor $$
    とおくと $0\le r<\lvert\operatorname{supp}Q\rvert$ である。$\operatorname{supp}Q$ の $r$ 個の元 $a$ で $Q_n(a):=(\lfloor nQ(a)\rfloor+1)/n$、残りの元で $Q_n(a):=\lfloor nQ(a)\rfloor/n$ とする。$Q_n\in\mathcal T_n$ で、$\lvert Q_n(a)-Q(a)\rvert\le1/n$ である。
    $Q_n\to Q$ で $Q\in\operatorname{int}\Gamma$ だから、大きな $n$ で $Q_n\in\Gamma$ である。cor-sanov-type より
    $$ \Pr(L_n\in\Gamma)\ge P^n(T(Q_n))\ge(n+1)^{-(d-1)}e^{-nD(Q_n\|P)} $$
    である。$\operatorname{supp}Q_n\subset\operatorname{supp}Q\subset\operatorname{supp}P$ であり、$t\mapsto t\log t$ は $[0,1]$ で連続なので、$D(Q_n\|P)\to D(Q\|P)$ である。よって $\liminf_n\frac1n\log\Pr(L_n\in\Gamma)\ge-D(Q\|P)$ である。$Q$ について下限をとると (3) になる。$\square$

$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$ を固定したまま得られる。

指数の傾きと Cramér の定理

$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$ を 指数関数で傾けた分布 である。

傾けた分布と変分公式
  1. すべての $Q\in\mathcal P$ と $\theta\in\mathbb{R}$ について $D(Q\|P)\ge\theta Q(f)-\Lambda(\theta)$ である。等号は $Q=P_\theta$ のときに限る。
  2. $a$ が $f$ の $\operatorname{supp}P$ での最小値より大きく最大値より小さく、$a\ge P(f)$ であるとする。$\Lambda'(\theta_a)=a$ となる $\theta_a\ge0$ がただ 1 つある。$\Gamma:=\{Q\mid Q(f)\ge a\}$ の上で $D(\cdot\|P)$ は $P_{\theta_a}$ でのみ最小になり、最小値は Cramérの定理(大偏差) の率関数 $I(a)=\sup_\theta(\theta a-\Lambda(\theta))$ に等しい。
ダイバージェンスの差
  1. $D(Q\|P)=\infty$ なら明らかである。そうでなければ $\log(Q/P_\theta)=\log(Q/P)-\theta f+\Lambda(\theta)$ だから
    $$ D(Q\|P_\theta)=D(Q\|P)-\theta Q(f)+\Lambda(\theta) $$
    である。$P_\theta$ と $P$ の台は等しい。左辺は 0 以上で、$0$ になるのは $Q=P_\theta$ のときに限る(Kullback–Leiblerダイバージェンス の定理「非負性(Gibbs の不等式)」)。
  2. $f(X)$ が定数でないことから、$\theta_a$ の存在と一意性、$I(a)=\theta_aa-\Lambda(\theta_a)$ は Cramérの定理(大偏差) の命題「率関数の性質」の 3 である。$a\ge P(f)=\Lambda'(0)$ と $\Lambda'$ の単調性から $\theta_a\ge0$ である。$Q\in\Gamma$ なら、(1) と $\theta_a\ge0$ より
    $$ D(Q\|P)\ge\theta_aQ(f)-\Lambda(\theta_a)\ge\theta_aa-\Lambda(\theta_a)=I(a) $$
    である。$Q=P_{\theta_a}$ のとき $Q(f)=\Lambda'(\theta_a)=a$ であり、2 つの不等号はともに等号になる。等号の場合は (1) より $P_{\theta_a}$ に限る。$\square$

$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$ の元になる。

さいころの平均が 4 以上

$\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^*$ に近い。大きな目が一度だけ極端に出るのではなく、全体の分布が滑らかに傾くことが分かる。

Polish 空間の場合

Polish 空間の上の Sanov の定理

$\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$ である事象である。

補足

歴史と文献

定理の名前は I. N. Sanov の 1957 年の論文による(PW25 §15.5、CS04 第 2 章)。この記事の型の評価は CS04 の Lemma 2.1–2.3 と Theorem 2.1 の流れに沿うが、型の類の大きさの下からの評価は、個数の評価 $(n+1)^{d-1}$ と確率の比較で示した。CS04 は $P$ の台が全体である場合を述べ、ここでは台が全体でない場合も含めた。

関連項目

参考文献

[2]
Imre Csiszár; Paul C. Shields, Information Theory and Statistics: A Tutorial, Foundations and Trends in Communications and Information Theory, 2004, Vol. 1, No. 4, pp. 417–528。§2.1:Lemma 2.1–2.3、Theorem 2.1(pp. 429–432)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する