確率変数の和と平均の不等式：ヘフティングの不等式

ヘフティングの公式

期待値がゼロ$${E[x]=0}$$で、$${a < x < b}$$の確率変数の$${x}$$を扱う。$${\theta (0<\theta < 1)}$$を用いて$${[a,b]}$$間の任意の点$${\theta a + (1-\theta)b}$$が定義でき、これを$${x}$$とおき、下の凸関数$${h(tx)=e^{tx}, (t >0)}$$を適用する。
$${h(\theta a + (1-\theta)b) \leq \theta h(a) + (1-\theta)h(b)}$$は明らかであるから、$${\theta a + (1-\theta)b=x}$$より、これを$${x}$$を使って示せば、
$${e^{tx}\displaystyle{\leq \frac{b-x}{b-a}e^{ta} + \frac{x-a}{b-a}e^{tb}}}$$
となる。
この両辺の期待値を取り、$${E[x]=0}$$から、
$${E[e^{tx}]\displaystyle{\leq \frac{b}{b-a}e^{ta} - \frac{a}{b-a}e^{tb}= e^{ta}\Big(\frac{b}{b-a} -(1- \frac{b}{b-a})e^{t(b-a)}\Big)}}$$
ここで、右辺を$${\displaystyle{\frac{b}{b-a}=p, s=(b-a)t}}$$とし、$${s}$$の関数$${\phi(ts)}$$を用いて、$${e^{\phi(s)}}$$とし、$${0<\tau<1}$$を使いテイラー展開すると、$${\phi(s)=\phi(0)+ s \phi'(0) + \frac{1}{2}s^2 \phi''(s\tau)}$$となる。
$${\phi(s)=\displaystyle{\log e^{ta}\Big(p+(1-p)e^{s}\Big) =(p-1)s+\log \Big(p-(1-p)e^{t(b-a)}\Big)}}$$より、
$${\phi'(s)=\displaystyle{(p-1) + \frac{(1-p)e^s}{p+(1-p)e^s}}}$$
$${\phi''(s)=\displaystyle{\frac{(1-p)e^s}{p+(1-p)e^s} - \frac{(1-p)^2e^{2s}}{(p+(1-p)e^s)^2}=-\Big(\frac{(1-p)e^s}{p+(1-p)e^s} - \frac{1}{2}\Big)^2+\frac{1}{4} \leq \frac{1}{4} }}$$
$${\phi(s)=0, \phi'(s)=0, \displaystyle{\phi''(s)\leq \frac{1}{4}}}$$から、
$${\phi(s) \leq \displaystyle{\frac{1}{8}s^2} }$$
よって、
$${E[e^{tx}]\displaystyle{\leq e^{\phi(s)} \leq \exp(\frac{(b-a)^2}{8}t^2)}}$$
この、期待値がゼロ$${E[x]=0}$$で、$${a < x < b}$$の確率変数の$${x}$$に対し、$${E[e^{tx}]\displaystyle{\leq \exp(\frac{(b-a)^2}{8}t^2)}}$$が成立することをヘフティングの公式（Hoeffding's lemma）と呼ぶ。

ヘフティングの不等式

互いに独立で、それぞれの期待値がゼロ$${E[x_i]=0}$$で、$${a_i< x_i < b_i}$$の確率変数の$${\bf{ x}}$$の総和$${X=\sum x}$$に関して、非負の実数$${\epsilon}$$を用いたチェルノフ不等式が成り立つ。
$${Pr(X-E[X]\geq \epsilon)\leq e^{-t \epsilon} \Pi E[\exp t(x_i-E[x_i])])}$$
この左辺に上記のヘフティングの公式を適用すれば、
$${\displaystyle{Pr(X-E[X]\geq \epsilon)\leq e^{-t \epsilon} \Pi \exp\frac{b_i-a_i}{8}t^2 =\exp \Big( \frac{t^2}{8}\sum (b_i - a_i)^2 -t\epsilon \Big)}}$$
ここで、非負の実数$${t}$$を、左辺を最小にするように選ぶと、
$${ \displaystyle{\frac{t^2}{8}\sum (b_i - a_i)^2 -t\epsilon =\frac{\sum (b_i - a_i)^2}{8}(t-\frac{4\epsilon }{\sum (b_i - a_i)^2})^2- \frac{2\epsilon^2 }{\sum (b_i - a_i)^2} }}$$
より、
$${\displaystyle{Pr(X-E[X]\geq \epsilon)\leq \exp\Big( - \frac{2\epsilon^2 }{\sum (b_i - a_i)^2}\Big)}}$$
これをヘフティングの不等式と呼ぶ。
これを$${\bf {x}}$$の平均値$${\bar{x}}$$にも適用すると、
$${\displaystyle{Pr(\bar{x}-E[\bar{x}]\geq \epsilon)\leq \exp\Big( - \frac{2n\epsilon^2 }{\frac{1}{n}\sum (b_i - a_i)^2}\Big)}}$$より、
$${\displaystyle{Pr(\bar{x}-E[\bar{x}]\geq \epsilon)\leq \exp\Big( - \frac{2n^2\epsilon^2 }{\sum (b_i - a_i)^2}\Big)}}$$
となる。