指数型確率不等式 | 確率論入門

1 指数 Markov 法と Chernoff の評価

積率母関数§E11.9 定義 4.1は $M_Z(t)=E[e^{tZ}]$ によって定義される。上側確率を評価するときは $t>0$ を取り、単調増加関数 $x\mapsto e^{tx}$ に Markov の不等式を適用する。

定理 1.1 (Chernoff の評価). $Z$ を実確率変数とし、 $u>0$ とする。

$t>0$ かつ $E[e^{tZ}]<\infty$ ならば、 $P(Z\geq u)\leq e^{-tu}E[e^{tZ}]$ が成り立つ。
$t>0$ かつ $E[e^{-tZ}]<\infty$ ならば、 $P(Z\leq-u)\leq e^{-tu}E[e^{-tZ}]$ が成り立つ。

したがって、右辺を有限にする $t>0$ の範囲で下限を取ることができる。

証明.主張 (1)を示す。 $t>0$ のとき $e^{tZ}$ は非負確率変数であり、

\{Z\geq u\}=\{e^{tZ}\geq e^{tu}\}

である。Markov の不等式§E11.4 定理 3.1を $e^{tZ}$ と閾値 $e^{tu}$ へ適用すると、

P(Z\geq u) \leq\frac{E[e^{tZ}]}{e^{tu}} =e^{-tu}E[e^{tZ}]

を得る。主張 (2)を示す。下側の評価は、同じ議論を $-Z$ へ適用して得られる。▨

2 区間に入る確率変数の指数積率

Hoeffding の補題の証明では、区間に入る確率変数の分散が区間幅だけで評価されることを用いる。この分散評価を、指数傾斜した確率測度へ適用する。

補題 2.1. $W$ を実確率変数とし、ある実数 $a\leq b$ について $P(a\leq W\leq b)=1$ と仮定する。このとき

\operatorname{Var}(W)\leq\frac{(b-a)^2}{4}

が成り立つ。

証明. $m=E[W]$ と置く。有界性により $m$ は有限であり、 $a\leq m\leq b$ である。点ごとに $(W-a)(b-W)\geq0$ であるから、

W^2\leq(a+b)W-ab

が成り立つ。期待値を取り、 $m^2$ を引くと、

\begin{aligned} \operatorname{Var}(W) &=E[W^2]-m^2\\ &\leq(a+b)m-ab-m^2\\ &=(b-m)(m-a)\\ &=\frac{(b-a)^2}{4}-\left(m-\frac{a+b}{2}\right)^2\\ &\leq\frac{(b-a)^2}{4} \end{aligned}

を得る。▨

2.1 証明方針

有界確率変数 $X$ の対数積率母関数を $\psi(t)=\log E[e^{tX}]$ とする。指数傾斜した確率測度の下で $\psi''(t)$ は $X$ の分散に等しい。指数傾斜によって $X$ の値域は変わらないため、補題 2.1が $\psi''$ を一様に評価する。中心化から $\psi(0)=\psi'(0)=0$ となるので、二階微分の評価を積分して対数積率母関数の二次上界を得る。

補題 2.2 (Hoeffding の補題). $X$ を実確率変数とし、ある実数 $a\leq b$ について $P(a\leq X\leq b)=1$ および $E[X]=0$ を仮定する。このとき、任意の $t\in\R$ に対して

E[e^{tX}]\leq\exp\!\left(\frac{t^2(b-a)^2}{8}\right)

が成り立つ。

証明. $M(t)=E[e^{tX}]$ および $\psi(t)=\log M(t)$ と置く。 $X$ は有界であるため、任意の有界な $t$ の区間上で $|X|^je^{tX}$ は定数によって抑えられる。優収束定理§E10.11 定理 3.1を差分商へ適用することにより、 $M$ は二回微分可能であり、

M'(t)=E[Xe^{tX}], \qquad M''(t)=E[X^2e^{tX}]

となる。

$M(t)>0$ であるから、

\psi'(t)=\frac{M'(t)}{M(t)}, \qquad \psi''(t)=\frac{M''(t)}{M(t)}-\left(\frac{M'(t)}{M(t)}\right)^2.

確率測度 $P_t$ を

P_t(A)=\frac{E[e^{tX}\mathbf1_A]}{M(t)} \qquad(A\in\mathcal F)

によって定める。上の二階微分は $P_t$ の下での $X$ の分散である。 $P_t(a\leq X\leq b)=1$ であるため、補題 2.1により

\psi''(t)\leq\frac{(b-a)^2}{4}

がすべての $t\in\R$ について成り立つ。

$c=(b-a)^2/4$ および $g(t)=\psi(t)-ct^2/2$ と置くと、 $g''(t)\leq0$ であるから $g$ は凹関数である。また、 $M(0)=1$ と $E[X]=0$ から $g(0)=g'(0)=0$ となる。凹関数は任意の点で接線以下にあるため、

g(t)\leq g(0)+g'(0)t=0

である。したがって、

\psi(t)\leq\frac{ct^2}{2}=\frac{t^2(b-a)^2}{8}.

両辺の指数を取ると主張を得る。▨

3 独立な有界確率変数の和

各確率変数が入る区間は同一である必要がない。各確率変数を中心化しても区間の幅は変わらないため、指数評価は各区間の幅の二乗和によって定まる。

3.1 証明方針

各 $X_i$ を $Y_i=X_i-E[X_i]$ と中心化する。Hoeffding の補題を各 $Y_i$ へ適用し、独立性によって指数積率を積へ分解する。得られた二次指数上界を Chernoff の評価へ代入し、指数の右辺を最小にする $t$ を選ぶ。下側確率には $-Y_i$ を用い、両側確率には和事象の評価を用いる。

定理 3.1 (Hoeffding の不等式). $X_1,\ldots,X_n$ を独立な実確率変数とする。各 $1\leq i\leq n$ について、実数 $a_i\leq b_i$ が

P(a_i\leq X_i\leq b_i)=1

を満たすと仮定する。さらに、

V=\sum_{i=1}^n(b_i-a_i)^2, \qquad T_n=\sum_{i=1}^n\bigl(X_i-E[X_i]\bigr)

と置く。

$V>0$ ならば、任意の $u>0$ に対して

\begin{aligned} P(T_n\geq u)&\leq\exp\!\left(-\frac{2u^2}{V}\right),\\ P(T_n\leq-u)&\leq\exp\!\left(-\frac{2u^2}{V}\right),\\ P(|T_n|\geq u)&\leq2\exp\!\left(-\frac{2u^2}{V}\right) \end{aligned}

が成り立つ。 $V=0$ ならば $T_n=0$ がほとんど確実に成り立つ。

証明. $\mu_i=E[X_i]$ および $Y_i=X_i-\mu_i$ と置く。有界性により各期待値は有限であり、 $a_i\leq\mu_i\leq b_i$ である。したがって、

a_i-\mu_i\leq Y_i\leq b_i-\mu_i

がほとんど確実に成り立ち、この区間の幅は $b_i-a_i$ である。さらに $E[Y_i]=0$ であるから、補題 2.2により、任意の $t\in\R$ に対して

E[e^{tY_i}]\leq\exp\!\left(\frac{t^2(b_i-a_i)^2}{8}\right)

となる。

$Y_1,\ldots,Y_n$ は独立であり、各 $e^{tY_i}$ は有限区間上の指数関数として有界である。したがって各因子は可積分であり、有限積 $\prod_{i=1}^ne^{tY_i}=e^{tT_n}$ も有界であって可積分である。 $2\leq k\leq n$ に対して、 $\prod_{i=1}^{k-1}e^{tY_i}$ は $Y_1,\ldots,Y_{k-1}$ が生成する σ-加法族に関して可測であり、 $e^{tY_k}$ と独立である。積の期待値の分解§E11.7 定理 3.1を $k=2$ から順に適用すると、

\begin{aligned} E[e^{tT_n}] &=\prod_{i=1}^nE[e^{tY_i}]\\ &\leq\exp\!\left(\frac{t^2}{8}\sum_{i=1}^n(b_i-a_i)^2\right)\\ &=\exp\!\left(\frac{t^2V}{8}\right) \end{aligned}

を得る。

$V>0$ と $u>0$ を仮定する。 $t>0$ に対して定理 1.1を用いると、

P(T_n\geq u) \leq\exp\!\left(-tu+\frac{t^2V}{8}\right).

右辺の指数は $t=4u/V$ で最小となり、最小値は $-2u^2/V$ である。この指数最小化から上側の評価を得る。 $-Y_1,\ldots,-Y_n$ も独立であり、それぞれ幅 $b_i-a_i$ の区間に入るため、同じ議論を $-T_n$ へ適用すると下側の評価を得る。最後に、

\{|T_n|\geq u\} =\{T_n\geq u\}\cup\{T_n\leq-u\}

へ和事象の評価を適用すると両側の評価を得る。

$V=0$ ならば、すべての $i$ について $a_i=b_i$ である。各 $X_i$ は定数 $a_i$ にほとんど確実に等しいため、 $Y_i=0$ 、したがって $T_n=0$ がほとんど確実に成り立つ。▨

4 具体例

例 4.1. $X_1,\ldots,X_n$ を独立とし、 $X_i$ が母数 $p_i\in[0,1]$ の Bernoulli 分布に従うとする。同一分布は仮定しない。各 $X_i$ は区間 $[0,1]$ に入るため $V=n$ であり、 $\bar p=n^{-1}\sum_{i=1}^np_i$ と置くと、任意の $\varepsilon>0$ に対して

P\!\left(\left|\frac1n\sum_{i=1}^nX_i-\bar p\right|\geq\varepsilon\right) \leq2e^{-2n\varepsilon^2}

が成り立つ。期待値が同一でなくても、独立性と共通の有界区間だけで指数的な評価を得ることができる。

注意 4.2. 本記事では、Bernstein・Bennett 型不等式および一般の劣 Gauss 確率変数を扱わない。

5 演習

問題 5.1.

実数 $a<b$ と $P(a\leq W\leq b)=1$ を満たす実確率変数 $W$ について、補題 2.1で等号 $\operatorname{Var}(W)=(b-a)^2/4$ が成り立つための必要十分条件は $P(W=a)=P(W=b)=1/2$ であることを証明せよ。
補題 2.2の証明で、指数傾斜後も $X$ が区間 $[a,b]$ にほとんど確実に入ることを、 $P_t$ の定義から示せ。
独立な $X_1,\ldots,X_n$ の各 $X_i$ が区間 $[-c_i,c_i]$ に入り、 $E[X_i]=0$ を満たす場合について、 $P(|\sum_iX_i|\geq u)$ の上界を $c_1,\ldots,c_n$ によって書き下せ。
$\varepsilon_1,\varepsilon_2,\ldots$ を独立同分布で $P(\varepsilon_i=1)=P(\varepsilon_i=-1)=1/2$ を満たす確率変数列とし、 $S_n=\sum_{i=1}^{n}\varepsilon_i$ とおく。 $\delta>0$ に対して $P(|S_n|\geq n\delta)\leq2e^{-n\delta^2/2}$ を示し、§E11.13 定理 2.1を用いて $S_n/n\to0$ がほとんど確実に成り立つことを証明せよ。また、Chebyshev の不等式から得られる上界 $1/(n\delta^2)$ では、同じ議論の総和が発散することを確かめよ。

解答.

$m=E[W]$ 、 $c=(a+b)/2$ とおく。 $W$ は有界であるから二次可積分であり、 $(W-c)^2=(W-m)^2+2(m-c)(W-m)+(m-c)^2$ の期待値をとると§E11.4 命題 1.2により
$E[(W-c)^2]=\operatorname{Var}(W)+(m-c)^2$
である。 $a\leq W\leq b$ がほとんど確実に成り立つので $|W-c|\leq(b-a)/2$ であり、 $E[(W-c)^2]\leq(b-a)^2/4$ である。したがって
$\operatorname{Var}(W)=E[(W-c)^2]-(m-c)^2\leq\frac{(b-a)^2}{4}-(m-c)^2\leq\frac{(b-a)^2}{4}$
である。等号 $\operatorname{Var}(W)=(b-a)^2/4$ が成り立つならば、二つの不等式がともに等号であり、 $m=c$ かつ $E[(b-a)^2/4-(W-c)^2]=0$ である。後者の被積分関数はほとんど確実に非負であるから、§E10.22 系 3.1により $|W-c|=(b-a)/2$ 、すなわち $W\in\{a,b\}$ がほとんど確実に成り立つ。 $p=P(W=b)$ とおくと $P(W=a)=1-p$ であり、 $m=pb+(1-p)a=c$ から $p(b-a)=(b-a)/2$ 、 $p=1/2$ を得る。

逆に $P(W=a)=P(W=b)=1/2$ ならば $m=c$ であり、 $(W-c)^2=(b-a)^2/4$ がほとんど確実に成り立つので $\operatorname{Var}(W)=E[(W-c)^2]=(b-a)^2/4$ である。
$C=\max\{|a|,|b|\}$ とおく。 $P(a\leq X\leq b)=1$ から $0<e^{tX}\leq e^{|t|C}$ がほとんど確実に成り立つので、 $M(t)=E[e^{tX}]$ は有限であり、 $e^{tX}>0$ から $M(t)>0$ である。したがって $P_t$ は定義される。 $N=\{X\notin[a,b]\}$ とおくと $P(N)=0$ であり、 $e^{tX}\mathbf 1_N$ は $N$ の外で $0$ であるから、§E10.10 補題 3.1により $E[e^{tX}\mathbf 1_N]=0$ である。 $P_t$ の定義から $P_t(N)=0$ であり、
$P_t(a\leq X\leq b)=\frac{E[e^{tX}\mathbf 1_{\Omega\setminus N}]}{M(t)}=\frac{E[e^{tX}]-E[e^{tX}\mathbf 1_N]}{M(t)}=\frac{M(t)}{M(t)}=1$
を得る。第二の等号では積分の線形性を用いた。
Hoeffding の不等式の設定どおり $X_1,\dots,X_n$ を独立とし、 $c_i\geq0$ 、 $P(-c_i\leq X_i\leq c_i)=1$ 、 $E[X_i]=0$ とする。 $a_i=-c_i$ 、 $b_i=c_i$ とおくと $b_i-a_i=2c_i$ であり、
$V=\sum_{i=1}^{n}(2c_i)^2=4\sum_{i=1}^{n}c_i^2, \qquad T_n=\sum_{i=1}^{n}(X_i-E[X_i])=\sum_{i=1}^{n}X_i$
である。 $\sum_ic_i^2>0$ ならば、定理 3.1の両側の評価により、任意の $u>0$ に対して
$P\left(\left|\sum_{i=1}^{n}X_i\right|\geq u\right)\leq2\exp\left(-\frac{2u^2}{4\sum_{i=1}^{n}c_i^2}\right)=2\exp\left(-\frac{u^2}{2\sum_{i=1}^{n}c_i^2}\right)$
が成り立つ。すべての $c_i$ が $0$ ならば $V=0$ であり、同定理により $\sum_iX_i=0$ がほとんど確実に成り立つので、 $u>0$ に対して左辺は $0$ である。
$a_i=-1$ 、 $b_i=1$ とおくと $P(a_i\leq\varepsilon_i\leq b_i)=1$ 、 $E[\varepsilon_i]=0$ であり、 $V=\sum_{i=1}^{n}(b_i-a_i)^2=4n>0$ 、 $T_n=S_n$ である。定理 3.1の両側の評価を $u=n\delta$ に適用すると
$P(|S_n|\geq n\delta)\leq2\exp\left(-\frac{2n^2\delta^2}{4n}\right)=2e^{-n\delta^2/2}$
である。 $\sum_n2e^{-n\delta^2/2}$ は公比 $e^{-\delta^2/2}<1$ の等比級数であり収束するので、§E11.13 定理 2.1により $P(\limsup_n\{|S_n|\geq n\delta\})=0$ である。 $N_r=\limsup_n\{|S_n|\geq n/r\}$ とおくと、 $N=\bigcup_{r\geq1}N_r$ は零事象である。 $\omega\notin N$ ならば、各 $r$ について十分大きいすべての $n$ で $|S_n(\omega)|/n<1/r$ であるから、 $S_n(\omega)/n\to0$ である。したがって $S_n/n\to0$ がほとんど確実に成り立つ。

一方、 $E[\varepsilon_i]=0$ 、 $E[\varepsilon_i^2]=1$ であり、§E11.7 系 3.2により $i\neq j$ のとき $\operatorname{Cov}(\varepsilon_i,\varepsilon_j)=0$ であるから、共分散の双線形性により $\operatorname{Var}(S_n)=\sum_{i=1}^{n}\operatorname{Var}(\varepsilon_i)=n$ である。よって、§E11.4 系 3.2から得られる上界は $P(|S_n|\geq n\delta)\leq n/(n\delta)^2=1/(n\delta^2)$ である。 $\sum_n1/(n\delta^2)=\infty$ であるから、この上界からは§E11.13 定理 2.1の仮定を確かめることができない。

▨

§E11.18指数型確率不等式