確率変数の和と期待値の不等式：ベネットの不等式

ベネットの公式

ある正実数$${b\geq 0}$$とともに、期待値がゼロで、分散$${\sigma^2}$$の確率変数$${x}$$は、
$${|x| \leq b}$$ならば、$${x}$$のモーメント母関数$${M_x(t)=E[e^{xt}]}$$は、$${t >0}$$なる$${t}$$とともに、$${\displaystyle{M_x(t)\leq \exp\Big( \frac{\sigma^2}{b^2}(e^{tb}-tb-1)\Big)}}$$を満たす。
また、$${k>3}$$の任意の整数$${k}$$に対し$${E[x^k]\leq \displaystyle{\frac{1}{2}k!\sigma^2b^{k-2}}}$$であり、$${0 < t < \frac{1}{b}}$$の時には、
$${\displaystyle{M_x(t)\leq \exp\frac{t^2\sigma^2}{2(1-tb)}}}$$
が成り立つ。

証明）

まず、$${t>0}$$とする。
$${x}$$のモーメント母関数は
$${\displaystyle{M_x(t)=1+E[x]t+\frac{1}{2}E[x^2] + \sum_{k\geq 3}\frac{t^k}{k!}E[x^k]}}$$
であったから、$${E[x]=0}$$と$${E[x^2]=\sigma^2-E^2[x]\leq \sigma^2 }$$より、
$${\displaystyle{M_x(t)\leq 1+\frac{1}{2}\sigma^2 + \sum_{k\geq 3}\frac{t^k}{k!}E[x^k]}}$$
$${|x|\leq b}$$とすれば、
$${\displaystyle{\sum_{k\geq 3}\frac{t^k}{k!}E[x^k] \leq \sum_{k\geq 3}\frac{t^k}{k!}E[b^{k-2}x^2]=\sum_{k\geq 3}\frac{t^kb^{k-2}}{k!}E[x^2]\leq \frac{\sigma^2}{b^2}\sum_{k\geq 3}\frac{(tb)^k}{k!}}}$$
ここで、$${e^x=1+x+\frac{1}{2}x^2+\displaystyle{\sum_{k>3}\frac{x^k}{k!}}}$$を適用し、
$${\displaystyle{\sum_{k\geq 3}\frac{t^k}{k!}E[x^k] \leq \frac{\sigma^2}{b^2}\sum_{k\geq 3}\frac{(tb)^k}{k!}=\frac{\sigma^2}{b^2}(e^{tb}-\frac{t^2b^2}{2}-tb-1)}}$$より、
よって、
$${\displaystyle{M_x(t)\leq 1+\frac{\sigma^2}{b^2}(e^{tb}-tb-1) \leq \exp\Big( \frac{\sigma^2}{b^2}(e^{tb}-tb-1)\Big)}}$$
が証明された。
次に、$${k >3}$$の時、$${E[x^k] \leq\frac{1}{2}k!\sigma^2b^{k-2}}$$とおくと、
$${\displaystyle{M_x(t)=1+\frac{1}{2}t^2\sigma^2+\frac{\sigma^2t^2}{2}\sum_{k \geq 3}(tb)^{k-2}}}$$
ここで、最後の項は等比数列の和であり、$${0 < t <\frac{1}{b}}$$であれば、$${tb<1}$$より、$${lim_{n\to\infty}(tb)^n=0}$$となるから、
$${\displaystyle{M_x(t)\leq 1+\frac{1}{2}t^2\sigma^2+\frac{\sigma^2t^2}{2}\frac{tb}{1-tb}=1+\frac{\sigma^2t^2}{2}\frac{1}{1-tb} \leq \exp\frac{\sigma^2t^2}{2(1-tb)}}}$$
が成り立つ。

ベネットの不等式

単調増加関数$${H(x)=(1+x)\log(1+x)-x, (x>0)}$$とおく。
互いに独立な確率変数$${\bf{x}=(x_1,\cdots, x_n)}$$のそれぞれが、$${|x_i|\leq b, (b\geq 0)}$$であるとき、$${E[x_i^2]\leq \sigma_i^2}$$を使えば、ある正実数$${S}$$とともに、
$${\displaystyle{Pr(\Big|\sum x_i\Big|\geq S)\leq 2 \exp\Big( -\frac{\sum\sigma_i^2}{b^2}H(\frac{bS}{\sum\sigma_i^2})\Big)}}$$を満たす。

証明）

$${t>0}$$として、$${\bf{x}}$$のそれぞれに上記の公式を適用すれば、
$${\displaystyle{M_{x_i}(t)\leq \exp\Big( \frac{\sigma_i^2}{b^2}(e^{tb}-tb-1)\Big)}}$$となる。
$${X=\sum x_i}$$として、$${\displaystyle{M_{X}(t)=E[e^{Xt}]=\Pi_iE[e^{tx_i}]}}$$であるから、
$${\displaystyle{M_{X}(t) \leq \Pi \exp\Big( \frac{\sigma_i^2}{b^2}(e^{tb}-tb-1)\Big) = \exp\frac{\sum \sigma_i}{b^2}(e^{tb}-tb=1)}}$$
また、この式に、$${X \geq S}$$に対してのチェルノフ不等式を適用すると、
$${\displaystyle{Pr(X \geq S)\leq min_{t>0} e^{-tS} E[e^{tX}] \leq min_{t>0}\exp\Big(\frac{\sum\sigma_i^2}{b^2}(e^{tb} - tb -1) - tS \Big)}}$$
右辺の最小を与える$${t}$$値とその最小値を得るために、
$${\displaystyle{\varphi(t)=\frac{\sum\sigma_i^2}{b^2}(e^{tb} - tb -1) - tS}}$$とする。
$${\varphi'(t)=\displaystyle{\frac{\sum\sigma_i^2}{b} (e^{tb}-1)-S}}$$
これから、
$${\displaystyle{e^{tb}=(\frac{\sum\sigma_i^2}{b}+S)\frac{b}{\sum\sigma_i^2}=1+\frac{Sb}{\sum\sigma_i^2}}}$$
よって、$${t_{min}=\displaystyle{\frac{1}{b}\log(1+\frac{Sb}{\sum \sigma_i^2})}}$$の時、$${\varphi(t)}$$は最小値をとり、その最小値は
$${\varphi(t_{min})=\displaystyle{\frac{\sum \sigma_i^2}{b^2}\Big(\frac{Sb}{\sum \sigma_i^2}-\log(1+\frac{Sb}{\sum \sigma_i^2})\Big) -\frac{S}{b}}\log(1+\frac{Sb}{\sum \sigma_i^2})}$$
$${\displaystyle{=-\Big(\frac{\sum \sigma_i^2}{b^2} + \frac{S}{b}\Big)\log(1+\frac{Sb}{\sum \sigma_i^2})+\frac{S}{b}}}$$
$${\displaystyle{= -\frac{\sum \sigma_i^2}{b^2}\Big( (1+\frac{bS}{\sum \sigma_i^2})\log(1+\frac{Sb}{\sum \sigma_i^2} )+ \frac{Sb}{\sum \sigma_i^2} \Big)=-\frac{\sum \sigma_i^2}{b^2}H(\frac{Sb}{\sum \sigma_i^2})}}$$
よって、
$${\displaystyle{Pr(X\geq S)\leq \exp(-\frac{\sum \sigma_i^2}{b^2}H(\frac{Sb}{\sum \sigma_i^2}))}}$$
$${\bf{-x}=(-x_1,\cdots,-x_n)}$$についても同様に行えば、
$${\displaystyle{Pr(X\leq -S)\leq \exp(-\frac{\sum \sigma_i^2}{b^2}H(\frac{Sb}{\sum \sigma_i^2}))}}$$
これを合わせて、
$${\displaystyle{Pr(|X|\geq S)=Pr(X\geq S)+Pr(X\leq -S) \leq 2\exp(-\frac{\sum \sigma_i^2}{b^2}H(\frac{Sb}{\sum \sigma_i^2}))}}$$
よって、ベネットの不等式が証明された。