Chernoff 限界と指数的な裾の評価

確率論入門　第10章 §10.3　★★★ 積率母関数を使うと、独立和の裾の確率は項数について指数的に減ることが示せる

Chernoff 限界

§10.1 の Chebyshev の不等式から、独立同分布の和 $S_n$ について次が得られる。

$$P(S_n-n\mu\ge n\varepsilon )\le\frac{\sigma^2}{n\varepsilon ^2}$$

右辺は $n$ について $1/n$ の速さでしか減らない。実際の裾はもっと速く減ることが多い。たとえば和が正規分布 $\mathrm N(n\mu,n\sigma^2)$ に従うなら、この確率は $\mathrm{e}^{-n\varepsilon ^2/(2\sigma^2)}$ 程度で減る。

この差は、Chebyshev の不等式が2次モーメントしか使っていないことによる。すべてのモーメントの情報を一度に使うには、Markov の不等式を $\mathrm{e}^{tX}$ に使えばよい（系 10.2）。

証明

$t>0$ を固定する。関数 $x\mapsto\mathrm{e}^{tx}$ は狭義増加なので、$\{X\ge a\}=\{\mathrm{e}^{tX}\ge\mathrm{e}^{ta}\}$ である。非負の確率変数 $\mathrm{e}^{tX}$ に Markov の不等式を使うと

$$P(X\ge a)\le\mathrm{e}^{-ta}E[\mathrm{e}^{tX}]=\mathrm{e}^{-ta}M_X(t)$$

である。$t=0$ では右辺は 1 なので、不等式は自明である。すべての $t\ge0$ で成り立つので、下限をとってよい。

(10.20) は、$-X$ に (10.19) を使い、$M_{-X}(t)=M_X(-t)$ と書き直せば得られる。

キュムラント母関数 $K_X(t)=\log M_X(t)$ で書けば、(10.19) の右辺は次の形である。

$$\exp\Bigl(-\sup_{t\ge0}\bigl(ta-K_X(t)\bigr)\Bigr)$$

そこで次の関数を導入する。

$K_X(0)=0$ なので、$t=0$ の項からレート関数は非負である。レート関数は $K_X$ の Legendre 変換であり、$K_X$ が凸関数であることと対になる量である。$K_X$ の凸性は、確認テスト 8.2-5 の $M_X$ の凸性と Hölder の不等式から示すことができる。

証明

Jensen の不等式から、すべての実数で $M_X(t)\ge\mathrm{e}^{t\mu}$、すなわち $K_X(t)\ge t\mu$ が成り立つ。負の $t$ と $a\ge\mu$ について

$$ta-K_X(t)\le ta-t\mu=t(a-\mu)\le0=0\cdot a-K_X(0)$$

であり、負の $t$ の項は $t=0$ の項を超えない。したがって上限は非負の $t$ でとれば十分で、(10.19) から (10.22) を得る。平均以下の $a$ の場合も、正の $t$ の項について同じ議論をすればよい。

独立和と指数的な減少

この評価は独立和に対して計算しやすい形になる。$X_1,X_2,\dots$ が独立で $X$ と同分布なら、第8章 §8.2 から

$$M_{S_n}(t)=M_X(t)^n,\qquad\text{すなわち}\qquad K_{S_n}(t)=nK_X(t)$$

である。したがって

$$I_{S_n}(na)=\sup_t\bigl(tna-nK_X(t)\bigr)=n\sup_t\bigl(ta-K_X(t)\bigr)=nI_X(a)$$

となり、命題 10.16 から次の評価を得る。

$M_X$ が 0 の近くで有限なら、平均より大きい $a$ でレート関数は正となる。実際、第8章 §8.4 のキュムラントの展開

$$K_X(t)=\mu t+\frac{\sigma^2}2t^2+ o(t^2)$$

から、十分小さい $t>0$ で

$$ta-K_X(t)=t(a-\mu)-\frac{\sigma^2}{2}t^2+ o(t^2)>0$$

である。したがって (10.23) の右辺は $n$ について指数関数的に減る。

代表的な分布のレート関数を計算しておく。どれも $t\mapsto ta-K_X(t)$ を微分して 0 と置けば、最大点が求まる。キュムラント母関数は凸なので、停留点が最大点である。

正規分布 $\mathrm N(\mu,\sigma^2)$ では $K_X(t)=\mu t+\frac{\sigma^2t^2}2$ である。停留点の条件 $a-\mu-\sigma^2t=0$ から $t=(a-\mu)/\sigma^2$ で、

$$I_X(a)=\frac{(a-\mu)^2}{\sigma^2}-\frac{(a-\mu)^2}{2\sigma^2}=\frac{(a-\mu)^2}{2\sigma^2}\tag{10.24}$$

となる。とくに標準正規分布 $Z$ について、$a\ge0$ なら次が成り立つ。

$$P(Z\ge a)\le\mathrm{e}^{-a^2/2}$$

Poisson 分布 $\mathrm{Po}(\lambda)$ では $K_X(t)=\lambda(\mathrm{e}^t-1)$ である。停留点の条件は $a=\lambda\mathrm{e}^t$ である。正の $a$ についてこれを解くと、$t=\log(a/\lambda)$ である。よって

$$I_X(a)=a\log\frac a\lambda-\lambda\Bigl(\frac a\lambda-1\Bigr)=a\log\frac{a}{\lambda}-a+\lambda .\tag{10.25}$$

Bernoulli 分布（成功確率 $p\in(0,1)$）では $K_X(t)=\log(1-p+p\mathrm{e}^t)$ である。$0<a<1$ について、停留点の条件を解くと

$$a=\frac{p\mathrm{e}^t}{1-p+p\mathrm{e}^t}\quad\Longrightarrow\quad\mathrm{e}^t=\frac{a(1-p)}{p(1-a)}$$

である。このとき

$$1-p+p\mathrm{e}^t=1-p+\frac{a(1-p)}{1-a}=\frac{1-p}{1-a}$$

である。代入すると

$$I_X(a)=a\log\frac{a(1-p)}{p(1-a)}-\log\frac{1-p}{1-a}=a\log\frac ap+(1-a)\log\frac{1-a}{1-p}\eqqcolon D(a\,\|\,p)\tag{10.26}$$

となる。$D(a\,\|\,p)$ は、2点分布のあいだの Kullback–Leibler 情報量（相対エントロピー）である。(10.23) から、二項分布 $S_n\sim\mathrm{Bin}(n,p)$ について、$a\ge p$ なら次が成り立つ。

$$P(S_n\ge na)\le\mathrm{e}^{-nD(a\|p)}$$

指数分布 $\mathrm{Ex}(\lambda)$ では、$t<\lambda$ の範囲で次のようになる。

$$K_X(t)=-\log(1-t/\lambda)$$

正の $a$ について、停留点の条件 $a-\frac{1}{\lambda-t}=0$ を解く。答えは $t=\lambda-\frac1a$ である。よって

$$I_X(a)=\lambda a-1+\log\frac{1}{\lambda a}=\lambda a-1-\log(\lambda a)\tag{10.27}$$

となる（$1-t/\lambda=\frac{1}{\lambda a}$ を使った）。

正規分布の裾の精密な評価

正規分布では Chernoff 限界 $\mathrm{e}^{-a^2/2}$ を、多項式の因子の分だけさらに精密にすることができる。標準正規分布の密度を、第6章 §6.2 と同じく次のように書く。

$$\phi(x)=\frac{1}{\sqrt{2\pi}}\mathrm{e}^{-x^2/2}$$

上からの評価は第6章 §6.2 の正規分布の裾の評価と同じもので、ここでは下からの評価を別の形で示す。

証明

$\phi'(x)=-x\phi(x)$ である。上からの評価は、積分範囲で $1\le x/a$ であることから

$$P(Z\ge a)=\int_a^\infty\phi(x)\,\mathrm{d} x\le\int_a^\infty\frac xa\phi(x)\,\mathrm{d} x=\frac1a\Bigl[-\phi(x)\Bigr]_a^\infty=\frac{\phi(a)}{a}$$

となる。下からの評価には、次の微分を使う。

$$\frac{d }{d x}\Bigl(-\frac{\phi(x)}{x}\Bigr)=\frac{\phi(x)}{x^2}-\frac{\phi'(x)}{x}=\Bigl(1+\frac1{x^2}\Bigr)\phi(x)$$

積分範囲で $1+\frac1{x^2}\le1+\frac1{a^2}$ なので

$$\frac{\phi(a)}{a}=\int_a^\infty\Bigl(1+\frac1{x^2}\Bigr)\phi(x)\,\mathrm{d} x\le\Bigl(1+\frac1{a^2}\Bigr)P(Z\ge a)$$

となる。両辺に $\frac{a^2}{1+a^2}$ を掛けて、下からの評価を得る。

$a=3$ での値を比べる。

• Chernoff 限界：$\mathrm{e}^{-4.5}\approx0.0111$
• Mills の上限：$\phi(3)/3\approx0.00148$
• Mills の下限：$0.3\,\phi(3)\approx0.00133$
• 正確な値：$P(Z\ge3)\approx0.00135$

(10.28) の上下の比は $1+1/a^2$ で、無限遠で 1 に近づく。Chernoff 限界は指数の部分 $\mathrm{e}^{-a^2/2}$ と一致し、前に付く因子 $1/(a\sqrt{2\pi})$ を含まない。

Hoeffding の不等式

レート関数は分布ごとに計算しなければならず、分布が分からないときには使えない。確率変数が有界であることだけを仮定して、積率母関数を分布によらない形で上から抑えたものが Hoeffding の補題である。

証明

平均が 0 で値が区間に入るので、$a\le0\le b$ である。区間内の点 $x$ は、両端の凸結合として

$$x=\frac{b-x}{b-a}\,a+\frac{x-a}{b-a}\,b$$

と書ける。係数はどちらも $[0,1]$ にあって、和が 1 である。指数関数の凸性から

$$\mathrm{e}^{tx}\le\frac{b-x}{b-a}\,\mathrm{e}^{ta}+\frac{x-a}{b-a}\,\mathrm{e}^{tb}\qquad(a\le x\le b)$$

が成り立つ。$x=X$ を代入して期待値をとり、平均が 0 であることを使うと

$$E[\mathrm{e}^{tX}]\le\frac{b\,\mathrm{e}^{ta}-a\,\mathrm{e}^{tb}}{b-a}$$

となる。次のように置く。

$$\theta=\frac{-a}{b-a}\in[0,1],\qquad u=t(b-a)$$

すると次の関係が成り立つ。

$$\frac{b}{b-a}=1-\theta,\qquad ta=-\theta u,\qquad tb=(1-\theta)u$$

よって右辺は

$$(1-\theta)\mathrm{e}^{-\theta u}+\theta\mathrm{e}^{(1-\theta)u}=\mathrm{e}^{-\theta u}\bigl(1-\theta+\theta\mathrm{e}^u\bigr)=\mathrm{e}^{L(u)},\qquad L(u)\coloneqq-\theta u+\log\bigl(1-\theta+\theta\mathrm{e}^u\bigr)$$

と書ける。$L$ を微分すると

$$L'(u)=-\theta+\frac{\theta\mathrm{e}^u}{1-\theta+\theta\mathrm{e}^u},\qquad L''(u)=\frac{\theta\mathrm{e}^u(1-\theta+\theta\mathrm{e}^u)-(\theta\mathrm{e}^u)^2}{(1-\theta+\theta\mathrm{e}^u)^2}=\rho(u)\bigl(1-\rho(u)\bigr)$$

である。ここで次の2つを使った。

$$\rho(u)=\frac{\theta\mathrm{e}^u}{1-\theta+\theta\mathrm{e}^u}\in[0,1],\qquad1-\rho(u)=\frac{1-\theta}{1-\theta+\theta\mathrm{e}^u}$$

原点での値は $L(0)=0$、$L'(0)=-\theta+\theta=0$ である。また $\rho(1-\rho)\le\frac14$ なので、$L''\le\frac14$ である。Taylor の定理（Lagrange の剰余項）から、ある $\xi$ について

$$L(u)=L(0)+L'(0)u+\frac{L''(\xi)}{2}u^2\le\frac{u^2}{8}=\frac{t^2(b-a)^2}{8}$$

となり、(10.29) を得る。

証明

$Y_i=X_i-E[X_i]$ と置く。$E[Y_i]=0$ である。また $Y_i$ は区間 $[a_i-E[X_i],\,b_i-E[X_i]]$ に値をとる。その幅は $b_i-a_i$ である。これらは独立なので、$t>0$ について

$$E\bigl[\mathrm{e}^{t(S_n-E[S_n])}\bigr]=\prod_{i=1}^nE[\mathrm{e}^{tY_i}]\le\prod_{i=1}^n\exp\Bigl(\frac{t^2(b_i-a_i)^2}{8}\Bigr)=\exp\Bigl(\frac{t^2C}{8}\Bigr),\qquad C=\sum_{i=1}^n(b_i-a_i)^2$$

である（1つ目の等号は独立な確率変数の積の期待値、不等号は補題 10.19）。Chernoff 限界から

$$P\bigl(S_n-E[S_n]\ge s\bigr)\le\exp\Bigl(-ts+\frac{t^2C}{8}\Bigr)$$

がすべての $t>0$ で成り立つ。指数の2次式は $t=4s/C$ で最小値をとる。

$$-\frac{4s^2}{C}+\frac{2s^2}{C}=-\frac{2s^2}{C}$$

よって (10.30) を得る。下側は、区間 $[-b_i,-a_i]$ に値をとる $-X_i$ に同じ議論を使えばよい。両側は、2つの事象の和に劣加法性を使えばよい。

各項が $[0,1]$ に値をとる独立同分布の場合を考える。標本平均 $\bar X_n$ について $s=n\varepsilon$ と置くと

$$P\bigl(\bar X_n-\mu\ge\varepsilon \bigr)\le\mathrm{e}^{-2n\varepsilon ^2}\tag{10.31}$$

となる。Chebyshev の評価 (10.8) が $1/n$ の速さで減るのに対し、こちらは $n$ について指数関数的に減る。

図 10.3 に、公正なコインを $n$ 回投げて表の割合が 0.6 以上になる確率を示す。Chebyshev・Hoeffding・Chernoff の上限と正確な値を比べた。縦軸は対数目盛りである。

• Chebyshev の上限は直線的に下がらない（$1/n$ は対数目盛りで緩やかな曲線になる）。
• 指数的な上限と正確な値は、どれも直線に近い傾きで下がる。

正確な値の傾きは Chernoff 限界の傾き $D(0.6\,\|\,0.5)\approx0.0201$ とほぼ等しく、Cramér の定理の主張と合っている。

確認テスト

オリジナル

1. 10.3-1 $Z\sim\mathrm N(0,1)$ について、Chernoff 限界 $\inf_{t\ge0}\mathrm{e}^{-ta}M_Z(t)$ を直接計算せよ。それが $\mathrm{e}^{-a^2/2}$ になることを確かめよ。また $a=3$ のときの値を、正確な値 $P(Z\ge3)\approx0.00135$ と比べよ。

2. 10.3-2 $S\sim\mathrm{Bin}(100,\frac12)$ とする。$P(S\ge75)$ の上限を、次の3つで求めよ。

   • Chernoff 限界 $\mathrm{e}^{-nD(a\|p)}$
   • Hoeffding の不等式
   • Chebyshev の不等式

また正確な値 $P(S\ge75)\approx2.82\times10^{-7}$ と比べよ。3. 10.3-3 $X_1,\dots,X_n$ を独立で $\mathrm{Ex}(1)$ に従う確率変数とする。和を $S_n$ とする。$P(S_n\ge2n)\le(2/\mathrm{e})^n$ を示せ。また $n=10$ のときの値を、次の正確な値と比べよ。

$$P(S_{10}\ge20)=\mathrm{e}^{-20}\sum_{k=0}^{9}\frac{20^k}{k!}\approx0.00500$$ 4. 10.3-4 $\varepsilon _1,\dots,\varepsilon _n$ を、$\pm1$ を等確率でとる独立な確率変数とする。級数の比較で $\cosh t\le\mathrm{e}^{t^2/2}$ を示せ。それを使って、$s>0$ について次を導け。

$$P(\varepsilon _1+\cdots+\varepsilon _n\ge s)\le\mathrm{e}^{-s^2/(2n)}$$ 5. 10.3-5 $X\sim\mathrm{Po}(\lambda)$ について、下側の Chernoff 限界から次を示せ。

$$P(X\le\lambda/2)\le\exp\Bigl(-\frac{\lambda}{2}(1-\log2)\Bigr)$$

また $\lambda=20$ のときの値を、正確な値 $P(X\le10)\approx0.0108$ と比べよ。