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

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\mathbb 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}$ は定数によって抑えられる。優収束定理§E9.7 定理 3.2を差分商へ適用することにより、 $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\mathbb 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\mathbb 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 (独立な Bernoulli 確率変数の平均). $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}

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

5 演習

問題 5.1.

補題 2.1で等号が成り立つための分布を一つ与え、証明中の二つの不等式がともに等号になることを確認せよ。
補題 2.2の証明で、指数傾斜後も $X$ が区間 $[a,b]$ にほとんど確実に入ることを、 $P_t$ の定義から示せ。
$X_i$ が区間 $[-c_i,c_i]$ に入り、 $E[X_i]=0$ を満たす場合について、 $P(|\sum_iX_i|\geq u)$ の上界を $c_1,\ldots,c_n$ によって書き下せ。
Hoeffding の不等式の証明で、各 $e^{tY_i}$ の可積分性だけでなく積 $e^{tT_n}$ の可積分性も確認する必要がある理由を、積率母関数の積公式の仮定と対応させて説明せよ。

6 扱った範囲と後続単元との境界

本記事は、指数 Markov 法、Chernoff の評価、Hoeffding の補題、および独立な有界確率変数の有限和に対する片側・両側の Hoeffding の不等式を扱った。各確率変数の区間は異なってよい。Bernstein・Bennett 型不等式、一般の劣 Gauss 確率変数は扱っていない。マルチンゲール差分列に対する Azuma–Hoeffding の不等式は、フィルトレーションとマルチンゲールを扱う「確率過程」へ委ねる。

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