Steinの方法

同義語:Stein's methodスタインの方法

概要

Steinの方法(Stein's method)とは、確率変数 $W$ の分布と正規分布・Poisson 分布などとの距離を、恒等式 $E[f'(Z)]=E[Zf(Z)]$ による標準正規分布 $Z$ の特徴づけと、Stein 方程式 $f'(w)-wf(w)=h(w)-E[h(Z)]$ の解を使って評価する方法である。誤差を $E[f_h'(W)-Wf_h(W)]$ の計算に置き換え、$W$ の構造だけで評価する。独立で平均 $0$、分散の和が $1$、3 次モーメントが有限な $\xi_i$ の和 $W$ について、Wasserstein 距離は $3\sum E\lvert\xi_i\rvert^3$ 以下になる。Poisson 近似では Chen–Stein の方法と呼ばれる。

$$\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}} $$

前提知識: 正規分布, 中心極限定理, Wasserstein距離

Stein の方法(Stein's method)は、確率変数 $W$ の分布が正規分布や Poisson 分布などの目標の分布にどれだけ近いかを、誤差の大きさまで込めて 評価する方法である。出発点は、標準正規分布 $Z\sim N(0,1)$ が恒等式
$$ E[f'(Z)]=E[Zf(Z)] $$
で特徴づけられることである(Stein の補題)。$W$ についてこの両辺の差 $E[f'(W)-Wf(W)]$ が小さければ、$W$ の分布は $N(0,1)$ に近いと期待できる。この期待を正確にするのが Stein 方程式
$$ f'(w)-wf(w)=h(w)-E[h(Z)] $$
である。試験関数 $h$ ごとにこれを解き、その解 $f_h$ を $W$ に代入すると、$E[h(W)]-E[h(Z)]=E[f_h'(W)-Wf_h(W)]$ となり、分布の差の評価が $W$ だけの期待値の計算に置き換わる。
この記事では、Stein の補題と Stein 方程式の解の評価を証明し、それを使って、独立な確率変数の和 $W=\sum_i\xi_i$(各 $\xi_i$ は平均 $0$、分散の和は $1$、3 次モーメントは有限)について
$$ d_{\mathrm W}(W,Z)\le 3\sum_{i=1}^nE\lvert\xi_i\rvert^3 $$
を証明する(thm-stm-main)。最後に、Poisson 分布への近似(Chen–Stein の方法)の特徴づけと主定理の主張を述べる。

分布の距離

以下、確率変数はすべて実数値で、同じ確率空間の上にあるとは限らない。距離は分布だけで決まる。

試験関数による距離

試験関数の族 $\mathcal H$ に対し
$$ d_{\mathcal H}(W,Z)=\sup_{h\in\mathcal H}\bigl\lvert E[h(W)]-E[h(Z)]\bigr\rvert $$
とおく。次の 3 つを使う。

  1. Wasserstein 距離 $d_{\mathrm W}$:$\mathcal H$ は $\lvert h(x)-h(y)\rvert\le\lvert x-y\rvert$ を満たす関数(Lipschitz 定数 $1$ 以下)の全体。$E\lvert W\rvert,E\lvert Z\rvert<\infty$ のときに使う。
  2. Kolmogorov 距離 $d_{\mathrm K}$:$\mathcal H=\{1_{(-\infty,x]}:x\in\mathbb R\}$。分布関数の差の上限 $\sup_x\lvert P(W\le x)-P(Z\le x)\rvert$ である。
  3. 全変動距離 $d_{\mathrm{TV}}$:$\mathcal H=\{1_A:A\text{ は Borel 集合}\}$。

$d_{\mathrm W}$ は 1 次の Wasserstein距離 $W_1$ に等しい(Kantorovich–Rubinstein の双対性)。$d_{\mathrm{TV}}$ は文献によって 2 倍の規約がある。整数値の $W,Z$ について、この記事の規約では $d_{\mathrm{TV}}(W,Z)=\frac12\sum_k\lvert P(W=k)-P(Z=k)\rvert$ であり、$\sum_k\lvert P(W=k)-P(Z=k)\rvert$ を全変動距離と呼ぶ文献もある。この記事の規約は Ros11 の §1.1.1 と同じである。
Stein の方法は滑らかな試験関数と相性がよいので、まず $d_{\mathrm W}$ を評価し、次の比較で $d_{\mathrm K}$ に移ることが多い。

Wasserstein 距離から Kolmogorov 距離へ

$Z$ が Lebesgue 測度について密度をもち、その密度が定数 $C$ 以下であるとする。$E\lvert W\rvert,E\lvert Z\rvert<\infty$ なら
$$ d_{\mathrm K}(W,Z)\le\sqrt{2C\,d_{\mathrm W}(W,Z)} $$
である。とくに $Z\sim N(0,1)$ なら $C=1/\sqrt{2\pi}$ で、$d_{\mathrm K}(W,Z)\le(2/\pi)^{1/4}\sqrt{d_{\mathrm W}(W,Z)}$ である。

傾きをつけた階段関数で挟む

$\delta=d_{\mathrm W}(W,Z)>0$ としてよい($\delta=0$ なら Lipschitz 関数で階段関数を近似して分布関数が一致する)。$x$ と $\varepsilon>0$ を固定し、$h$ を $(-\infty,x]$ で $1$、$[x+\varepsilon,\infty)$ で $0$、その間で 1 次関数とする。

評価を開く

$\varepsilon h$ は Lipschitz 定数 $1$ をもつから $\lvert E[h(W)]-E[h(Z)]\rvert\le\delta/\varepsilon$ である。$1_{(-\infty,x]}\le h$ と、$h-1_{(-\infty,x]}$ が区間 $(x,x+\varepsilon)$ の上の 1 次関数で積分が $\varepsilon/2$ であることから$$P(W\le x)\le E[h(W)]\le E[h(Z)]+\frac\delta\varepsilon\le P(Z\le x)+\frac{C\varepsilon}2+\frac\delta\varepsilon .$$$x$ の左に同じ形の関数を置けば、逆向きの $P(W\le x)\ge P(Z\le x)-C\varepsilon/2-\delta/\varepsilon$ も得られる。


$\varepsilon=\sqrt{2\delta/C}$ とすると誤差は $\sqrt{2C\delta}$ になる。$C=1/\sqrt{2\pi}$ のとき $\sqrt{2C}=(2/\pi)^{1/4}$ である。$\square$

Stein の補題

Stein の補題

$Z\sim N(0,1)$ とする。

  1. $f\colon\mathbb R\to\mathbb R$ が絶対連続で $E\lvert f'(Z)\rvert<\infty$ なら、$E\lvert Zf(Z)\rvert<\infty$ かつ $E[f'(Z)]=E[Zf(Z)]$ である。
  2. 逆に、$E\lvert W\rvert<\infty$ を満たす確率変数 $W$ が、$f$ と $f'$ がともに有界な $C^1$ 級関数 $f$ のすべてについて $E[f'(W)]=E[Wf(W)]$ を満たすなら、$W\sim N(0,1)$ である。
部分積分と特性関数の微分方程式

$\varphi(x)=e^{-x^2/2}/\sqrt{2\pi}$ を標準正規分布の密度とする。$\varphi'(x)=-x\varphi(x)$ だから、$x>0$ で $\varphi(x)=\int_x^\infty y\varphi(y)\,dy$、$x<0$ で $\varphi(x)=-\int_{-\infty}^xy\varphi(y)\,dy$ である。

  1. これを $E[f'(Z)]=\int f'(x)\varphi(x)\,dx$ に代入し、正の部分と負の部分で積分の順序を入れ替える。
    $$ \int_0^\infty f'(x)\int_x^\infty y\varphi(y)\,dy\,dx=\int_0^\infty y\varphi(y)\bigl(f(y)-f(0)\bigr)\,dy, $$
    $$ -\int_{-\infty}^0 f'(x)\int_{-\infty}^x y\varphi(y)\,dy\,dx=\int_{-\infty}^0 y\varphi(y)\bigl(f(y)-f(0)\bigr)\,dy . $$
    同じ計算を $\lvert f'\rvert$ で行うと、二重積分が $E\lvert f'(Z)\rvert<\infty$ で抑えられるので、Fubiniの定理 が使える。さらに $\lvert y(f(y)-f(0))\rvert\le\lvert y\rvert\int_{[0,y]}\lvert f'\rvert$ の積分も同じ量で抑えられ、$E\lvert Zf(Z)\rvert\le E\lvert f'(Z)\rvert+\lvert f(0)\rvert E\lvert Z\rvert<\infty$ である。足し合わせて $E[f'(Z)]=E[Z(f(Z)-f(0))]=E[Zf(Z)]$ を得る($E[Z]=0$)。
  2. $\psi(t)=E[e^{itW}]$ とおく。$E\lvert W\rvert<\infty$ だから、優収束定理により $\psi$ は微分可能で $\psi'(t)=iE[We^{itW}]$ である。$t$ を固定し、仮定を $f(w)=\sin(tw)$ と $f(w)=\cos(tw)$ に当てると
    $$ E[W\sin(tW)]=tE[\cos(tW)],\qquad E[W\cos(tW)]=-tE[\sin(tW)] $$
    となる。ゆえに $E[We^{itW}]=-tE[\sin(tW)]+itE[\cos(tW)]=it\psi(t)$ で、$\psi'(t)=-t\psi(t)$ である。$\frac{d}{dt}\bigl(e^{t^2/2}\psi(t)\bigr)=0$ と $\psi(0)=1$ から $\psi(t)=e^{-t^2/2}$ となり、これは $N(0,1)$ の特性関数である。特性関数は分布を決める(特性関数(確率論) の系「特性関数は分布を決める」)ので $W\sim N(0,1)$ である。$\square$

2 の逆向きの主張は、どんな $f$ の族に対しても成り立つわけではない。たとえば $f(w)=w$ だけなら、恒等式は $E[W^2]=1$ を言うにすぎない(ex-stm-table の表)。

Stein 方程式とその解

試験関数 $h$ に対して、$f$ を未知関数とする 1 階の線形微分方程式
$$ f'(w)-wf(w)=h(w)-E[h(Z)]\qquad(Z\sim N(0,1)) $$
を Stein 方程式 という。$\varphi$ を掛けると左辺は $(f\varphi)'$ になるので、解は積分で書ける。

Stein 方程式の解

$h$ が連続で $E\lvert h(Z)\rvert<\infty$ のとき、$\tilde h=h-E[h(Z)]$ とおくと
$$ f_h(w)=\frac1{\varphi(w)}\int_{-\infty}^w\tilde h(x)\varphi(x)\,dx=-\frac1{\varphi(w)}\int_w^\infty\tilde h(x)\varphi(x)\,dx $$
は Stein 方程式の $C^1$ 級の解である。ほかの解は $f_h+c/\varphi$($c$ は定数)であり、$c\ne0$ なら有界でない。さらに、$E[h(W)]$ と $E[f_h'(W)-Wf_h(W)]$ が有限な任意の確率変数 $W$ について
$$ E[h(W)]-E[h(Z)]=E\bigl[f_h'(W)-Wf_h(W)\bigr] $$
である。

積分因子

2 つの表示が等しいのは $\int_{\mathbb R}\tilde h\varphi=0$ による。$(f_h\varphi)'=\tilde h\varphi$ と $\varphi'=-w\varphi$ から $f_h'\varphi-wf_h\varphi=\tilde h\varphi$ で、$\varphi>0$ で割れば方程式を得る。斉次方程式 $f'=wf$ の解は $c/\varphi=c\sqrt{2\pi}e^{w^2/2}$ である。最後の等式は、方程式の $w$ に $W$ を代入して期待値をとったものである。$\square$

この等式の右辺は $W$ の分布だけを使い、$Z$ はもう現れない。評価の鍵は、$h$ が Lipschitz のとき $f_h$ とその導関数が $h$ によらず一様に抑えられることである。

解の評価

$h$ が Lipschitz 定数 $L$ をもつとする。このとき $f_h$ について

  1. $\lvert f_h(w)\rvert\le L$(すべての $w$)、
  2. $f_h'$ は Lipschitz 定数 $2L$ をもつ
    が成り立つ。

Ros11 Lemma 2.5 では 1 は $2L$ の形で述べられ、$\sup\lvert f_h'\rvert\le\sqrt{2/\pi}\,L$ も述べられている。以下の証明では、$\Phi$ を標準正規分布の分布関数、$\bar\Phi=1-\Phi$ とし、次の 2 つの積分を使う(右辺を微分すると被積分関数に戻り、端での極限は $0$ である)。
$$ \int_{-\infty}^w\Phi(x)\,dx=w\Phi(w)+\varphi(w),\qquad \int_w^\infty\bar\Phi(x)\,dx=\varphi(w)-w\bar\Phi(w). $$
どちらも正の関数の積分なので正である。

解を h' で書き直す

$h$ は Lipschitz だから絶対連続で、ほとんどいたるところ $\lvert h'\rvert\le L$ である。
$$ U(w)=\int_{-\infty}^wh'(x)\Phi(x)\,dx,\qquad V(w)=\int_w^\infty h'(x)\bar\Phi(x)\,dx $$
とおく。上の積分公式からどちらも絶対収束し、$\lvert U(w)\rvert\le L(w\Phi+\varphi)$、$\lvert V(w)\rvert\le L(\varphi-w\bar\Phi)$ である($\Phi,\bar\Phi,\varphi$ は $w$ での値)。
$\tilde h$ と $f_h$ の表示。 $h(w)-h(z)=\int_z^wh'$ を $z$ について $\varphi(z)\,dz$ で積分し、Fubini の定理で順序を入れ替えると $\tilde h=U-V$ を得る。

$f_h$ の表示の計算を開く

$\tilde h=U-V$ を $\int_{-\infty}^w\tilde h\varphi$ に代入する。$\int_{-\infty}^w\varphi(x)U(x)\,dx=\int_{-\infty}^wh'(y)\Phi(y)\bigl(\Phi(w)-\Phi(y)\bigr)dy$、$\int_{-\infty}^w\varphi(x)V(x)\,dx=\int_{-\infty}^wh'(y)\bar\Phi(y)\Phi(y)\,dy+\Phi(w)V(w)$ である。差をとると $\Phi(w)-\Phi(y)-\bar\Phi(y)=-\bar\Phi(w)$ により $\int_{-\infty}^w\tilde h\varphi=-\bar\Phi(w)U(w)-\Phi(w)V(w)$ となる。


こうして
$$ f_h=-\frac{\bar\Phi\,U+\Phi\,V}{\varphi} $$
を得る。
1 の証明。
$$ \lvert f_h\rvert\le\frac L\varphi\bigl(\bar\Phi(w\Phi+\varphi)+\Phi(\varphi-w\bar\Phi)\bigr)=\frac L\varphi\cdot\varphi(\bar\Phi+\Phi)=L . $$
2 の証明。 $f_h''$ を $U,V$ で書き、係数の符号を調べて同じ積分公式を当てる。
計算を開く

$U'=h'\Phi$、$V'=-h'\bar\Phi$(ほとんどいたるところ)である。方程式から $f_h'=\tilde h+wf_h=U-V+wf_h$ であり、右辺は局所絶対連続である。微分すると、ほとんどいたるところ $f_h''=h'+f_h+wf_h'=h'+(1+w^2)f_h+w(U-V)$ である。$f_h$ の表示を代入して整理すると$$f_h''=h'-\Bigl(\frac{(1+w^2)\bar\Phi}{\varphi}-w\Bigr)U-\Bigl(\frac{(1+w^2)\Phi}{\varphi}+w\Bigr)V$$となる。2 つの係数は非負である。実際 $g(w)=(1+w^2)\bar\Phi(w)-w\varphi(w)$ は $g'(w)=-2(\varphi-w\bar\Phi)\le0$、$g(w)\to0$($w\to\infty$)を満たすので $g\ge0$ であり、第 2 の係数は第 1 の係数の $w$ を $-w$ に替えたものである。ゆえに$$\lvert f_h''\rvert\le L\Bigl[1+\Bigl(\frac{(1+w^2)\bar\Phi}{\varphi}-w\Bigr)(w\Phi+\varphi)+\Bigl(\frac{(1+w^2)\Phi}{\varphi}+w\Bigr)(\varphi-w\bar\Phi)\Bigr].$$角括弧の第 2 項と第 3 項の和は、展開すると $(1+w^2)(\bar\Phi+\Phi)-w^2\Phi-w^2\bar\Phi=1$ になる。


よって $\lvert f_h''\rvert\le2L$ がほとんどいたるところで成り立ち、局所絶対連続な $f_h'$ は Lipschitz 定数 $2L$ をもつ。$\square$

$h(x)=x$ のとき $f_h\equiv-1$ で、1 の等号が成り立つ。

独立な和の正規近似

独立な和の Wasserstein 距離の評価

$\xi_1,\dots,\xi_n$ を独立な確率変数とし、各 $i$ について $E[\xi_i]=0$、$E\lvert\xi_i\rvert^3<\infty$ とし、さらに $\sum_{i=1}^nE[\xi_i^2]=1$ とする。$W=\sum_{i=1}^n\xi_i$、$Z\sim N(0,1)$ とすると
$$ d_{\mathrm W}(W,Z)\le3\sum_{i=1}^nE\lvert\xi_i\rvert^3 $$
である。

1 つずつ取り除いて Taylor 展開する

$h$ を Lipschitz 定数 $1$ の関数とし、$f=f_h$ を prop-stm-solution の解とする。lem-stm-bounds により $\lvert f\rvert\le1$ で、$f'$ は Lipschitz 定数 $2$ をもつ。とくに $\lvert f'(w)\rvert\le\lvert f'(0)\rvert+2\lvert w\rvert$ だから、以下の期待値はすべて有限である($E[W^2]=1$)。prop-stm-solution により
$$ E[h(W)]-E[h(Z)]=E[f'(W)]-E[Wf(W)] $$
であり、右辺を $1$ 次の項ずつ調べる。
$W_i=W-\xi_i$ とおく。$W_i$ は $\xi_i$ と独立である。
$E[Wf(W)]$ の展開。 $E[\xi_if(W_i)]=E[\xi_i]E[f(W_i)]=0$ だから
$$ E[Wf(W)]=\sum_{i=1}^nE\bigl[\xi_i\bigl(f(W)-f(W_i)\bigr)\bigr]=\sum_{i=1}^nE[\xi_i^2f'(W_i)]+\sum_{i=1}^nE[\xi_iR_i], $$
ここで $R_i=f(W)-f(W_i)-\xi_if'(W_i)$ である。独立性から $E[\xi_i^2f'(W_i)]=E[\xi_i^2]E[f'(W_i)]$ である。
$E[f'(W)]$ の展開。 $\sum_iE[\xi_i^2]=1$ を掛けて $E[f'(W)]=\sum_iE[\xi_i^2]E[f'(W)]$ と書く。
差の評価。 2 つを引くと
$$ E[f'(W)]-E[Wf(W)]=\sum_{i=1}^nE[\xi_i^2]\,E\bigl[f'(W)-f'(W_i)\bigr]-\sum_{i=1}^nE[\xi_iR_i]. $$
$f'$ が Lipschitz 定数 $2$ をもつので、$\lvert f'(W)-f'(W_i)\rvert\le2\lvert\xi_i\rvert$ であり、
$$ \lvert R_i\rvert=\Bigl\lvert\int_{W_i}^{W}\bigl(f'(t)-f'(W_i)\bigr)\,dt\Bigr\rvert\le\int_0^{\lvert\xi_i\rvert}2s\,ds=\xi_i^2 $$
である。したがって
$$ \bigl\lvert E[h(W)]-E[h(Z)]\bigr\rvert\le2\sum_{i=1}^nE[\xi_i^2]\,E\lvert\xi_i\rvert+\sum_{i=1}^nE\lvert\xi_i\rvert^3 . $$
Hölderの不等式 により $E[\xi_i^2]\le(E\lvert\xi_i\rvert^3)^{2/3}$、$E\lvert\xi_i\rvert\le(E\lvert\xi_i\rvert^3)^{1/3}$ だから $E[\xi_i^2]E\lvert\xi_i\rvert\le E\lvert\xi_i\rvert^3$ である。右辺は $3\sum_iE\lvert\xi_i\rvert^3$ 以下で、$h$ によらない。$h$ について上限をとって結論を得る。$\square$

証明で使ったのは「$W_i$ が $\xi_i$ と独立である」ことだけである。この議論は依存の近傍、交換可能な組、サイズバイアスや零バイアスの結合などへ拡張されている(Ros11 §3)。

独立同分布の場合

$X_1,X_2,\dots$ を独立同分布、$E[X_1]=0$、$E[X_1^2]=1$、$E\lvert X_1\rvert^3<\infty$ とし、$S_n=X_1+\dots+X_n$ とする。$Z\sim N(0,1)$ について
$$ d_{\mathrm W}\Bigl(\frac{S_n}{\sqrt n},Z\Bigr)\le\frac{3E\lvert X_1\rvert^3}{\sqrt n},\qquad d_{\mathrm K}\Bigl(\frac{S_n}{\sqrt n},Z\Bigr)\le\frac{(2/\pi)^{1/4}\sqrt{3E\lvert X_1\rvert^3}}{n^{1/4}} $$
である。

定理と比較の命題を当てる

$\xi_i=X_i/\sqrt n$ に thm-stm-main を当てると $\sum_iE\lvert\xi_i\rvert^3=nE\lvert X_1\rvert^3/n^{3/2}$ である。第 2 式は prop-stm-dk による。$\square$

Wasserstein 距離の位数 $n^{-1/2}$ は改良できない($X_1$ が $\pm1$ を等確率でとるとき、$S_n/\sqrt n$ は間隔 $2/\sqrt n$ の格子 $L_n$ に値をとるので、どの結合でも $\lvert S_n/\sqrt n-Z\rvert$ は $Z$ から $L_n$ までの距離以上であり、その期待値はおよそ $1/(2\sqrt n)$ である)。一方、Kolmogorov 距離の位数 $n^{-1/4}$ は最良ではなく、Berry–Esseenの定理 は同じ仮定で $n^{-1/2}$ を与える。Stein の方法で Kolmogorov 距離を直接評価するには、指示関数 $h=1_{(-\infty,x]}$ の Stein 方程式を扱う(解は $C^1$ でなくなる)。その解の評価は Ros11 Lemma 2.5 の 1 と Lemma 3.25 に、それを使う評価(有界な変数の和などの場合)は同 §3.6 にある。

二項分布の正規近似

$X_k$ を独立な Bernoulli 確率変数($P(X_k=1)=p$)とし、$\sigma^2=p(1-p)$、$\xi_k=(X_k-p)/(\sigma\sqrt n)$ とする。$E\lvert X_k-p\rvert^3=p(1-p)^3+(1-p)p^3=\sigma^2\bigl(p^2+(1-p)^2\bigr)$ だから、$B_n=X_1+\dots+X_n$ について
$$ d_{\mathrm W}\Bigl(\frac{B_n-np}{\sqrt{np(1-p)}},Z\Bigr)\le\frac{3\bigl(p^2+(1-p)^2\bigr)}{\sqrt{np(1-p)}} . $$
$p=1/2$、$n=100$ なら右辺は $0.3$、$p=0.1$、$n=100$ なら $0.82$ である。$p$ が $0$ に近いと $\sqrt{np}$ が小さく、正規近似は悪くなる。そのときは次の節の Poisson 近似が適する。

Poisson 近似

同じ考え方は離散の分布にも使える。$\mathbb Z_{\ge0}$ に値をとる確率変数を考え、$\mathrm{Po}(\lambda)$ で平均 $\lambda>0$ の Poisson分布 を表す。

Poisson 分布の Stein の特徴づけ

$W$ を $\mathbb Z_{\ge0}$ に値をとる確率変数とする。

  1. $W\sim\mathrm{Po}(\lambda)$ なら、有界な $f\colon\mathbb Z_{\ge0}\to\mathbb R$ のすべてについて $E[\lambda f(W+1)-Wf(W)]=0$ である。
  2. 逆に、台が有限な $f$ のすべてについて $E[\lambda f(W+1)-Wf(W)]=0$ なら、$W\sim\mathrm{Po}(\lambda)$ である。
添字をずらす
  1. $\sum_{k\ge1}kf(k)e^{-\lambda}\lambda^k/k!=\lambda\sum_{k\ge0}f(k+1)e^{-\lambda}\lambda^k/k!$ である(左辺の項の絶対値の和は $\lambda\sup\lvert f\rvert$ 以下である)。
  2. $j\ge1$ について $f=1_{\{j\}}$ を当てると $\lambda P(W=j-1)=jP(W=j)$ である。帰納法で $P(W=j)=\frac{\lambda^j}{j!}P(W=0)$ となり、総和が $1$ であることから $P(W=0)=e^{-\lambda}$ である。$\square$

対応する Stein 方程式 は $\lambda f(k+1)-kf(k)=1_A(k)-P(Z\in A)$($Z\sim\mathrm{Po}(\lambda)$、$A\subset\mathbb Z_{\ge0}$)である。$k=0$ から順に解けば解 $f_A$ が定まる($f_A(0)$ は方程式に現れない)。解の差分の評価
$$ \sup_k\lvert f_A(k+1)-f_A(k)\rvert\le\frac{1-e^{-\lambda}}{\lambda}\le\min\{1,\lambda^{-1}\} $$
が成り立つ(Ros11 Lemma 4.4。この記事では証明しない)。

独立な指示変数の和の Poisson 近似

$X_1,\dots,X_n$ を独立な確率変数で $P(X_i=1)=p_i$、$P(X_i=0)=1-p_i$ とし、$W=\sum_iX_i$、$\lambda=\sum_ip_i>0$、$Z\sim\mathrm{Po}(\lambda)$ とする。このとき
$$ d_{\mathrm{TV}}(W,Z)\le\frac{1-e^{-\lambda}}{\lambda}\sum_{i=1}^np_i^2\le\min\{1,\lambda^{-1}\}\sum_{i=1}^np_i^2 $$
である。

1 つの指示変数を外す

差分 $f_A(k+1)-f_A(k)$ の上の評価(引用)を使う。$W_i=W-X_i$ は $X_i$ と独立である。$X_if(W)=X_if(W_i+1)$ だから $E[Wf(W)]=\sum_ip_iE[f(W_i+1)]$ であり、
$$ E[\lambda f(W+1)-Wf(W)]=\sum_{i=1}^np_iE\bigl[f(W+1)-f(W_i+1)\bigr]=\sum_{i=1}^np_i^2\,E\bigl[f(W_i+2)-f(W_i+1)\bigr] $$
である($X_i=1$ のときだけ差が生じる)。$f=f_A$ とすると左辺は $P(W\in A)-P(Z\in A)$ に等しく、右辺の絶対値は差分の評価で抑えられる。$A$ について上限をとる。$\square$

$p_i=\lambda/n$ なら右辺は $\lambda\cdot\lambda/n\cdot\min\{1,\lambda^{-1}\}\le\lambda/n$ で、二項分布 $\mathrm{Bin}(n,\lambda/n)$ が $\mathrm{Po}(\lambda)$ に近いという少数の法則を誤差つきで与える。
独立でない場合の主定理が Chen–Stein の方法 である。次の形は依存の近傍を使う。

Chen–Stein の定理(依存の近傍)

$X_1,\dots,X_n$ を $\{0,1\}$ 値の確率変数とし、$p_i=P(X_i=1)$、$W=\sum_iX_i$、$\lambda=\sum_ip_i>0$、$Z\sim\mathrm{Po}(\lambda)$ とする。各 $i$ について $i\in N_i\subset\{1,\dots,n\}$ を、$X_i$ が $\{X_j:j\notin N_i\}$ と独立になるようにとり、$p_{ij}=E[X_iX_j]$ とおく。このとき
$$ d_{\mathrm{TV}}(W,Z)\le\min\{1,\lambda^{-1}\}\Bigl(\sum_{i=1}^n\sum_{j\in N_i}p_ip_j+\sum_{i=1}^n\sum_{j\in N_i\setminus\{i\}}p_{ij}\Bigr) $$
である(Ros11 Theorem 4.7。この記事では証明しない)。

誕生日の問題

$m$ 人の誕生日が $d$ 日から独立に一様に選ばれるとし、誕生日が一致する組の個数を $W=\sum_{\{a,b\}}X_{ab}$ とする。$p_{ab}=1/d$、$\lambda=\binom m2/d$ である。$N_{ab}$ を $\{a,b\}$ と人を共有する組(自身を含む、$2m-3$ 個)とすると、$X_{ab}$ はそれ以外の組の指示変数と独立である。人を 1 人だけ共有する 2 組の指示変数は独立なので $p_{ab,ac}=1/d^2$ である。thm-stm-chen から
$$ d_{\mathrm{TV}}(W,\mathrm{Po}(\lambda))\le\min\{1,\lambda^{-1}\}\binom m2\frac{(2m-3)+2(m-2)}{d^2}. $$
$m=23$、$d=365$ では $\lambda\approx0.6932$、右辺 $\approx0.161$ である。近似 $P(W=0)\approx e^{-\lambda}\approx0.500$ に対し、実際の値は $\prod_{k<23}(1-k/365)\approx0.4927$ で、差 $0.007$ は評価の範囲に収まる。

反例

各行は、ある主張の仮定をちょうど 1 つ外す。外した仮定は 1 列目に書く。

仮定を外した例
主張と外す仮定例成り立たなくなること
thm-stm-main:独立性1 つの $\varepsilon$($\pm1$ を等確率)で $\xi_i=\varepsilon/\sqrt n$。平均 $0$、分散の和 $1$ は保たれる右辺は $3/\sqrt n$ だが、$W=\sqrt n\,\varepsilon$ で、$h(x)=\lvert x\rvert$ により $d_{\mathrm W}(W,Z)\ge\sqrt n-\sqrt{2/\pi}$
thm-stm-main:平均 $0$定数 $\xi_i=1/\sqrt n$(独立で、$\sum E[\xi_i^2]=1$ は保たれる)右辺は $3/\sqrt n$ だが $W=\sqrt n$ で、$d_{\mathrm W}(W,Z)\ge\sqrt n-\sqrt{2/\pi}$
thm-stm-main:$\sum E[\xi_i^2]=1$独立な $\eta_i$($\pm1$ を等確率)で $\xi_i=2\eta_i/\sqrt n$。$\sum E[\xi_i^2]=4$右辺は $24/\sqrt n\to0$ だが、$W/2$ に定理を当てると $W\to N(0,4)$ で、$d_{\mathrm W}(W,Z)\to\sqrt{2/\pi}$($E\lvert2Z\rvert-E\lvert Z\rvert$)
prop-stm-dk:$Z$ の密度が有界$Z\equiv0$、$W=1/n$$d_{\mathrm W}=1/n\to0$ だが $d_{\mathrm K}=1$
thm-stm-lemma の 2:試験関数の族が、$f$ と $f'$ がともに有界な $C^1$ 級関数の全体であること試験関数を $f(w)=w$ だけにし、$W$ を $\pm1$ を等確率でとる変数とする$E[f'(W)]=1=E[W^2]$ だが $W$ は正規分布でない
thm-stm-poisson:独立性1 つの Bernoulli 変数 $Y$($P(Y=1)=\lambda/n$)で $X_i=Y$右辺は $\lambda/n\to0$ 程度だが、$W\in\{0,n\}$ で $d_{\mathrm{TV}}\ge P(W=0)-e^{-\lambda}\to1-e^{-\lambda}$

3 行目の極限は、$W/2=\sum_i\eta_i/\sqrt n$ に thm-stm-main を当てた $d_{\mathrm W}(W/2,Z)\le3/\sqrt n$ と、$d_{\mathrm W}(2Z,Z)=E\lvert Z\rvert=\sqrt{2/\pi}$($h(x)=\lvert x\rvert$ で下から、結合 $(2Z,Z)$ で上から)による。

文献

Stein の補題、Stein 方程式、解の評価、Poisson 近似は Ros11 の §2(Lemma 2.1、Lemma 2.5、pp. 6–9)と §4(Lemma 4.1、Lemma 4.4、Theorem 4.6・4.7、pp. 37–41)にある。prop-stm-dk は同 Proposition 1.2(p. 5)である。lem-stm-bounds と thm-stm-main の証明はこの記事の組み立てである(Ros11 Theorem 3.2 は 4 次モーメントを使う形)。

関連項目

参考文献

[1]
Nathan Ross, Fundamentals of Stein's method, Probability Surveys 8 (2011), 210–293, 2011, arXiv 版 v1:Proposition 1.2(p. 5)、Lemma 2.1(p. 6)、Lemma 2.5(p. 9)、Theorem 3.2(p. 10)、§3.6・Lemma 3.25(p. 33)、Lemma 4.1(p. 37)、Lemma 4.4(p. 38)、Theorem 4.6(p. 40)、Theorem 4.7(p. 41)

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