Hoeffdingの不等式(Hoeffding's inequality)とは、互いに独立で各 $X_i$ が区間 $[a_i,b_i]$ に値をとる確率変数の和 $S_n$ について、$t>0$ なら $P(S_n-E[S_n]\ge t)\le\exp(-2t^2/\sum_i(b_i-a_i)^2)$ が成り立つという不等式である。有界で平均 $0$ の確率変数の積率母関数を区間の幅で抑える Hoeffding の補題と、Markov の不等式を指数関数に当てる Chernoff の方法から従う。標本平均のずれの確率が観測の回数について指数関数的に小さくなることを保証する点で、回数の逆数の速さでしか減らない Chebyshev の不等式の評価と異なる。
前提知識: Markovの不等式, 期待値, 独立性(確率論), 積率母関数
Hoeffding の不等式(Hoeffding's inequality)は、値が有界な独立な確率変数の和が平均から離れる確率を、指数関数で上から抑える不等式である。$X_1,\dots,X_n$ が互いに独立で、各 $X_i$ が確率 $1$ で区間 $[a_i,b_i]$ に値をとるとき、$S_n:=X_1+\cdots+X_n$ と $t>0$ について
$$
P\bigl(S_n-E[S_n]\ge t\bigr)\le\exp\Bigl(-\frac{2t^2}{\sum_{i=1}^n(b_i-a_i)^2}\Bigr)
$$
が成り立つ。名前は W. Hoeffding による。
Chebyshevの不等式 は分散だけを使い、ずれの確率を $1/t^2$ の速さでしか抑えない。値が有界であることまで使うと、上の式のように $e^{-ct^2}$ の速さで抑えられる。標本平均に直すと、$n$ 回の独立な観測の平均が真の平均から $\varepsilon$ 以上ずれる確率は $n$ について指数関数的に小さくなり、「誤差 $\varepsilon$ を確率 $1-\delta$ 以上で保証するには何回観測すればよいか」に、$\log(1/\delta)$ に比例する答えを与える。この形の評価は、統計的推定、Monte Carlo 法、機械学習の汎化誤差の評価で基本の道具になる。
証明は 2 段に分かれる。まず 1 つの有界な確率変数の積率母関数を評価し(Hoeffding の補題)、次に Markovの不等式 を指数関数に当てて独立性で積に分ける(Chernoff の方法)。
以下、確率空間 $(\Omega,\mathcal F,P)$ の上の実数値の確率変数を考える。$a\le b$ と確率変数 $X$ について、「$X$ が $[a,b]$ に値をとる」は、確率 $1$ で $a\le X\le b$ であることを指す。このとき $X$ は有界なので、すべての実数 $\lambda$ で $E[e^{\lambda X}]$ は有限である。
確率変数 $X$ が $[a,b]$ に値をとり、$E[X]=0$ であるとする。このとき、すべての実数 $\lambda$ について
$$
E\bigl[e^{\lambda X}\bigr]\le\exp\Bigl(\frac{\lambda^2(b-a)^2}8\Bigr)
$$
である。
$a=b$ なら $X=a=E[X]=0$ なので両辺は $1$ である。以下 $a< b$ とする。$a\le X\le b$ と $E[X]=0$ から $a\le0\le b$ である。
凸性。 $x\in[a,b]$ を $x=\frac{b-x}{b-a}a+\frac{x-a}{b-a}b$ と端点の重みつき平均に書くと、$y\mapsto e^{\lambda y}$ は凸関数なので
$$
e^{\lambda x}\le\frac{b-x}{b-a}e^{\lambda a}+\frac{x-a}{b-a}e^{\lambda b}
$$
である。$x=X$ として期待値をとり $E[X]=0$ を使うと、$p:=\frac{-a}{b-a}\in[0,1]$ として
$$
E[e^{\lambda X}]\le\frac b{b-a}e^{\lambda a}+\frac{-a}{b-a}e^{\lambda b}=(1-p)e^{\lambda a}+pe^{\lambda b}
$$
となる。$u:=\lambda(b-a)$ とおくと $\lambda a=-pu$ なので、右辺は $e^{-pu}(1-p+pe^u)=e^{\varphi(u)}$、ただし
$$
\varphi(u):=-pu+\log\bigl(1-p+pe^u\bigr)
$$
である($1-p+pe^u>0$)。
2 次の評価。 $q(u):=\dfrac{pe^u}{1-p+pe^u}\in[0,1]$ とおくと $\varphi'(u)=-p+q(u)$ で、$q'(u)=q(u)\bigl(1-q(u)\bigr)$ なので $\varphi''(u)=q(u)(1-q(u))\le\frac14$ である。$\varphi(0)=0$、$\varphi'(0)=-p+p=0$ なので、Taylorの定理 の定理「Lagrange剰余つきのTaylorの定理」により、ある $\xi$ で
$$
\varphi(u)=\frac{\varphi''(\xi)}2u^2\le\frac{u^2}8=\frac{\lambda^2(b-a)^2}8
$$
である。$\square$
2 点分布の場合を見ると評価の意味が分かる。$a=-1$、$b=1$ で $X$ が $\pm1$ を確率 $\frac12$ ずつとるとき $E[e^{\lambda X}]=\cosh\lambda$ で、補題は $\cosh\lambda\le e^{\lambda^2/2}$ を述べる。両辺の $\lambda^2$ の係数はどちらも $\frac12$ なので、$\lambda\to0$ の近くでは係数 $\frac18$ は改良できない。
$X_1,\dots,X_n$ を互いに独立な確率変数とし、各 $X_i$ は $[a_i,b_i]$ に値をとるとする。$S_n:=\sum_{i=1}^nX_i$、$D:=\sum_{i=1}^n(b_i-a_i)^2$ とし、$D>0$ とする。このとき、すべての $t>0$ について
$$
P\bigl(S_n-E[S_n]\ge t\bigr)\le e^{-2t^2/D},\qquad P\bigl(S_n-E[S_n]\le-t\bigr)\le e^{-2t^2/D}
$$
であり、したがって $P\bigl(\lvert S_n-E[S_n]\rvert\ge t\bigr)\le2e^{-2t^2/D}$ である。
$Y_i:=X_i-E[X_i]$ とおくと、$Y_i$ は $\bigl[a_i-E[X_i],\,b_i-E[X_i]\bigr]$ に値をとり(区間の幅は $b_i-a_i$)、$E[Y_i]=0$ である。$Y_1,\dots,Y_n$ は互いに独立である(独立な確率変数の関数。独立性(確率論) の命題「独立な確率変数の関数」)。
$\lambda>0$ を固定する。$S_n-E[S_n]=\sum_iY_i$ であり、$y\mapsto e^{\lambda y}$ は増加関数なので、Markovの不等式 の定理「Markov の不等式」を $0$ 以上の確率変数 $e^{\lambda\sum_iY_i}$ に当てて
$$
P\Bigl(\sum_iY_i\ge t\Bigr)=P\Bigl(e^{\lambda\sum_iY_i}\ge e^{\lambda t}\Bigr)\le e^{-\lambda t}\,E\Bigl[\prod_{i=1}^ne^{\lambda Y_i}\Bigr]
$$
を得る。積率母関数 の補題「独立な確率変数の関数の積の期待値」により右辺の期待値は $\prod_iE[e^{\lambda Y_i}]$ で、lem-hoef-lemma から各因子は $\exp(\lambda^2(b_i-a_i)^2/8)$ 以下である。よって
$$
P\bigl(S_n-E[S_n]\ge t\bigr)\le\exp\Bigl(-\lambda t+\frac{\lambda^2D}8\Bigr)
$$
がすべての $\lambda>0$ で成り立つ。右辺の指数は $\lambda=4t/D$ で最小値 $-\frac{4t^2}D+\frac{2t^2}D=-\frac{2t^2}D$ をとるので、1 つ目の不等式を得る。
2 つ目は、$-X_i$($[-b_i,-a_i]$ に値をとり、区間の幅は同じ)に 1 つ目を当てればよい。最後の不等式は、事象 $\{\lvert S_n-E[S_n]\rvert\ge t\}$ が 2 つの事象の和集合であることから従う。$\square$
$\lambda$ を 1 つ固定して得た不等式を最後に $\lambda$ について最適化する、というこの手順を Chernoff の方法 という(積率母関数 の命題「指数型の裾の評価」)。Hoeffding の不等式は、積率母関数を分布によらず区間の幅だけで抑えたところに特徴がある。
$X_1,\dots,X_n$ が互いに独立で、どれも $[a,b]$($a< b$)に値をとり、期待値がすべて $\mu$ であるとする。$\bar X_n:=\frac1n\sum_{i=1}^nX_i$ とおくと、すべての $\varepsilon>0$ について
$$
P\bigl(\lvert\bar X_n-\mu\rvert\ge\varepsilon\bigr)\le2\exp\Bigl(-\frac{2n\varepsilon^2}{(b-a)^2}\Bigr)
$$
である。とくに $0< \delta< 1$ について $n\ge\dfrac{(b-a)^2}{2\varepsilon^2}\log\dfrac2\delta$ なら、$P(\lvert\bar X_n-\mu\rvert< \varepsilon)\ge1-\delta$ である。
thm-hoef-main を $t=n\varepsilon$、$D=n(b-a)^2$ で使うと、$\lvert\bar X_n-\mu\rvert\ge\varepsilon$ は $\lvert S_n-E[S_n]\rvert\ge n\varepsilon$ と同じなので、確率は $2\exp(-2n^2\varepsilon^2/(n(b-a)^2))$ 以下である。後半は、$n$ の条件が右辺 $\le\delta$ と同値であることによる。$\square$
独立同分布の場合の cor-hoef-mean の評価は SSBD14 の Lemma B.6(§B.4。事象は $>\varepsilon$)、$\lambda>0$ の場合の lem-hoef-lemma は同 Lemma B.7 にある。
表の回数 $S$ は、$[0,1]$ に値をとる独立な 100 個の確率変数(表なら $1$)の和で、$E[S]=50$、分散は $25$ である。表が $65$ 回以上出る確率を評価すると次のようになる。
| 評価 | 使う情報 | $P(S\ge65)$ の上界 |
|---|---|---|
| Chebyshevの不等式(両側) | 分散 $25$ | $\frac{25}{15^2}=0.111$ |
| 片側の Chebyshev の不等式 | 分散 $25$ | $\frac{25}{25+15^2}=0.1$ |
| thm-hoef-main($t=15$、$D=100$) | 値が $[0,1]$ にあること | $e^{-2\cdot225/100}=e^{-4.5}=0.0111$ |
| 実際の確率 | 二項分布 そのもの | $0.00176$ |
最後の行は $2^{-100}\sum_{k=65}^{100}\binom{100}k$ を計算した値である。この場合の Hoeffding の評価は、Markovの不等式 の命題「独立な符号の和の裾」と同じ値になる($\pm1$ の和に直すと $2S-100\ge30$ である)。
ある事象の確率 $\mu$ を、独立な $n$ 回の試行での相対頻度 $\bar X_n$ で推定する($X_i$ は $i$ 回目に事象が起これば $1$、起こらなければ $0$)。誤差 $0.05$ 未満を確率 $0.95$ 以上で保証したい。
| Chebyshevの不等式 | Hoeffding の不等式 | |
|---|---|---|
| 仮定 | 分散が有限 | 独立で、値が有界な区間にある |
| $P(\lvert\bar X_n-\mu\rvert\ge\varepsilon)$ の上界 | $\dfrac{\sigma^2}{n\varepsilon^2}$(独立でなく無相関でよい) | $2e^{-2n\varepsilon^2/(b-a)^2}$ |
| $n$ についての減り方 | $1/n$ | 指数関数的 |
| 確率 $1-\delta$ の保証に要る $n$ | $1/\delta$ に比例 | $\log(2/\delta)$ に比例 |
| 分散が小さいとき | 小さい分散を生かせる | 区間の幅だけで決まり、生かせない |
Chebyshev の列は、$X_i$ の分散がどれも $\sigma^2$ の場合である。表の最後の行のとおり、Hoeffding の不等式は分散を見ない。分散が区間の幅に比べて小さい場合の改良の例が、後の節の Chernoff の限界である。
thm-hoef-main の指数の係数 $2$ は、仮定だけから導ける評価としては大きくできない。
$c>2$ とする。独立で $[-1,1]$ に値をとる確率変数 $X_1,\dots,X_n$ の和 $S_n$ と $t>0$ で
$$
P\bigl(S_n-E[S_n]\ge t\bigr)>\exp\Bigl(-\frac{ct^2}{4n}\Bigr)
$$
となるものがある($a_i=-1$、$b_i=1$ なら $D=4n$ である)。
$X_1,X_2,\dots$ を独立で $\pm1$ を確率 $\frac12$ ずつとる確率変数とし、$S_n:=\sum_{i\le n}X_i$ とおく。$E[S_n]=0$、$E[X_i^2]=1$ である。$x>0$ を固定すると、中心極限定理 の定理「中心極限定理」により $P(S_n\ge x\sqrt n)=1-P(S_n/\sqrt n< x)$ は $1-\Phi(x)$ に近づく。ここで $\Phi$ は標準正規分布の分布関数で、連続なので、$P(S_n/\sqrt n\le x-\eta)\le P(S_n/\sqrt n< x)\le P(S_n/\sqrt n\le x)$ で $\eta\downarrow0$ とすれば $< $ と $\le$ の違いは極限に影響しない。一方 $t=x\sqrt n$ での右辺は $\exp(-cx^2/4)$ で、$n$ によらない。
$\gamma:=c/2>1$ とおく。$1-\Phi(x)\ge\int_x^{x+1}\frac{e^{-u^2/2}}{\sqrt{2\pi}}\,du\ge\frac{e^{-(x+1)^2/2}}{\sqrt{2\pi}}$ であり、$\gamma x^2-(x+1)^2-\log(2\pi)\to\infty$($x\to\infty$)なので、$x$ を大きくとれば $1-\Phi(x)>e^{-\gamma x^2/2}=e^{-cx^2/4}$ となる。この $x$ について、十分大きい $n$ で $P(S_n\ge x\sqrt n)>e^{-cx^2/4}$ である。$\square$
ここで示したのは、$n$ と $t$ をすべて動かすと係数 $2$ を大きくできないということである。個々の分布については、分散などを使ってよりよい評価が得られることがある。
値が $0$ か $1$ で、$1$ になる確率が小さい場合には、区間の幅だけを使う Hoeffding の評価は粗い。積率母関数を確率 $p_i$ まで使って評価すると、次の形になる。
$X_1,\dots,X_n$ を互いに独立な確率変数とし、$P(X_i=1)=p_i$、$P(X_i=0)=1-p_i$ とする。$S_n:=\sum_iX_i$、$\mu:=E[S_n]=\sum_ip_i$ とし、$\mu>0$ とする。このとき、すべての $\delta>0$ について
$$
P\bigl(S_n\ge(1+\delta)\mu\bigr)\le\Bigl(\frac{e^\delta}{(1+\delta)^{1+\delta}}\Bigr)^\mu
$$
である。
$\lambda>0$ について、$E[e^{\lambda X_i}]=1+p_i(e^\lambda-1)\le\exp\bigl(p_i(e^\lambda-1)\bigr)$($1+y\le e^y$)である。thm-hoef-main の証明と同じく Markov の不等式と独立性を使うと
$$
P\bigl(S_n\ge(1+\delta)\mu\bigr)\le e^{-\lambda(1+\delta)\mu}\prod_iE[e^{\lambda X_i}]\le\exp\bigl(-\lambda(1+\delta)\mu+(e^\lambda-1)\mu\bigr)
$$
である。$\lambda=\log(1+\delta)$ とおくと右辺は $\exp\bigl(\mu(\delta-(1+\delta)\log(1+\delta))\bigr)$ で、主張の右辺に等しい。$\square$
同じ上界は SSBD14 の Lemma B.3(§B.3)にある(事象は $S_n>(1+\delta)\mu$)。$n=1000$、$p_i=0.01$($\mu=10$)で $P(S_n\ge20)$ を評価すると、Hoeffding の不等式($t=10$、$D=1000$)では $e^{-0.2}=0.819$、Chebyshev の不等式(分散 $9.9$)では $0.099$、Chernoff の限界($\delta=1$)では $(e/4)^{10}=0.0210$ で、実際の確率は $0.0033$ である。
独立性は、マルチンゲールの増分であることに弱められる。次の不等式は Azuma の不等式とも書かれ、Hoeffding の名を添えて呼ばれることもある。
$(M_k)_{0\le k\le n}$ をフィルトレーション $(\mathcal F_k)$ に関するマルチンゲールとし、定数 $c_1,\dots,c_n>0$ について、確率 $1$ で $\lvert M_k-M_{k-1}\rvert\le c_k$($1\le k\le n$)であるとする。このとき、すべての $t>0$ について
$$
P(M_n-M_0\ge t)\le\exp\Bigl(-\frac{t^2}{2\sum_{k=1}^nc_k^2}\Bigr)
$$
である。$-M$ に当てると、下側についても同じ評価が成り立つ。
$d_k:=M_k-M_{k-1}$ とおく。$\lambda>0$ とする。prf-hoef-lemma の凸性の不等式を $a=-c_k$、$b=c_k$、$x=d_k$ で使うと、確率 $1$ で
$$
e^{\lambda d_k}\le\frac{c_k-d_k}{2c_k}e^{-\lambda c_k}+\frac{c_k+d_k}{2c_k}e^{\lambda c_k}
$$
である。マルチンゲールの条件から $E[d_k\mid\mathcal F_{k-1}]=0$ なので、両辺の条件付き期待値をとると(同記事の定理「条件付き期待値の基本性質」の 1・2・4)、$E[e^{\lambda d_k}\mid\mathcal F_{k-1}]\le\cosh(\lambda c_k)\le e^{\lambda^2c_k^2/2}$ を得る(最後の不等式は、$\pm1$ を確率 $\frac12$ ずつとる確率変数と $\lambda c_k$ に lem-hoef-lemma を当てたものである)。
$Z_k:=e^{\lambda(M_k-M_0)}$ は $\mathcal F_k$-可測で正の値をとり、$\lvert M_k-M_0\rvert\le\sum_{j\le k}c_j$ なので有界である。$Z_n=Z_{n-1}e^{\lambda d_n}$ に同じ定理の 3・6 を使い、$Z_{n-1}>0$ と 2 で上の評価を当てると
$$
E[Z_n]=E\bigl[Z_{n-1}E[e^{\lambda d_n}\mid\mathcal F_{n-1}]\bigr]\le e^{\lambda^2c_n^2/2}E[Z_{n-1}]
$$
であり、$Z_0=1$ から繰り返して $E[Z_n]\le\exp(\lambda^2\sum_kc_k^2/2)$ である。Markov の不等式から $P(M_n-M_0\ge t)\le\exp(-\lambda t+\lambda^2\sum_kc_k^2/2)$ で、$\lambda=t/\sum_kc_k^2$ とおけばよい。$\square$
独立な場合と比べる。$X_1,\dots,X_n$ が独立で、$X_i$ が幅 $c_i$ の区間 $[a_i,a_i+c_i]$ に値をとるとし、$M_0:=0$、$M_k:=\sum_{i\le k}(X_i-E[X_i])$、$\mathcal F_k:=\sigma(X_1,\dots,X_k)$ とおく。$M$ はマルチンゲールで、増分は $\lvert X_i-E[X_i]\rvert\le c_i$ を満たすので、吾妻の不等式は $\exp(-t^2/(2\sum c_i^2))$ を与える。thm-hoef-main では $D=\sum c_i^2$ なので $\exp(-2t^2/\sum c_i^2)$ で、この場合は Hoeffding の不等式のほうが指数が 4 倍よい。吾妻の不等式は、増分のとる区間の幅ではなく、絶対値の上限 $c_k$ だけを使っているからである。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 値が有界な区間にあること | $X$ が平均 $1$ の 指数分布 に従う($n=1$) | $P(X-1\ge t)=e^{-1-t}$ は、どの $c>0$ についても $t$ が大きいと $e^{-ct^2}$ を上回る |
| 独立性 | 確率 $\frac12$ ずつで $\pm1$ をとる $\varepsilon$ について $X_1=\cdots=X_n=\varepsilon$ | $P(S_n\ge n)=\frac12$ だが、thm-hoef-main の右辺は $e^{-2n^2/(4n)}=e^{-n/2}$($n\ge2$ で $\frac12$ より小さい) |
| 補題で $E[X]=0$ | $X\equiv1$、$[a,b]=[0,2]$ | $E[e^{\lambda X}]=e^\lambda$ は、$0< \lambda< 2$ で $e^{\lambda^2(b-a)^2/8}=e^{\lambda^2/2}$ を上回る |
1 行目では、$n=1$、$[a_1,b_1]$ をどう選んでも $X$ はその区間に値をとらないので、仮定が満たされない。Hoeffding の形の評価 $e^{-ct^2}$ は裾が正規分布と同じ速さで減ることを意味し、指数分布の裾 $e^{-t}$ はそれより重い。2 行目の各 $X_i$ は $[-1,1]$ に値をとり、平均は $0$ である。3 行目は、lem-hoef-lemma の評価が平均を引いた確率変数についてのものであることを示す(thm-hoef-main の証明で $Y_i=X_i-E[X_i]$ に当てたのはこのためである)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する