ホーフディングの補題

確率論において、ヘフディングの補題は、任意の有界確率変数のモーメント生成関数を有界とする不等式であり、^[1]そのような変数はサブガウス分布であることを意味します。フィンランド系アメリカ人の数理統計学者ワシリー・ヘフディングにちなんで名付けられました。

ホーフディングの補題の証明には、テイラーの定理とジェンセンの不等式が使われます。ホーフディングの補題自体は、ホーフディングの不等式の証明だけでなく、マクダーミッドの不等式の一般化にも使われます。

X を任意の実数値ランダム変数とし、ほぼ確実に、つまり確率 1 であるとする。すると、すべての に対して、 ${\displaystyle a\leq X\leq b}$ ${\displaystyle \lambda \in \mathbb {R} }$

${\displaystyle \mathbb {E} \left[e^{\lambda X}\right]\leq \exp {\Big (}\lambda \mathbb {E} [X]+{\frac {\lambda ^{2}(b-a)^{2}}{8}}{\Big )},}$

または同等に、

${\displaystyle \mathbb {E} \left[e^{\lambda (X-\mathbb {E} [X])}\right]\leq \exp {\Big (}{\frac {\lambda ^{2}(b-a)^{2}}{8}}{\Big )}.}$

以下の証明は直接的だが、ややアドホックである。別の証明では指数傾斜法を使用する。^{[2] :}対称化を用いた、やや劣る定数による補題2.2の証明も可能である。^[3]

一般性を失うことなく、を に置き換えることで を仮定することができ、 となります。 ${\displaystyle X}$${\displaystyle X-\mathbb {E} [X]}$${\displaystyle \mathbb {E} [X]=0}$${\displaystyle a\leq 0\leq b}$

は の凸関数なので、すべての に対して、 ${\displaystyle e^{\lambda x}}$${\displaystyle x}$${\displaystyle x\in [a,b]}$

${\displaystyle e^{\lambda x}\leq {\frac {b-x}{b-a}}e^{\lambda a}+{\frac {x-a}{b-a}}e^{\lambda b}}$

それで、

${\displaystyle {\begin{aligned}\mathbb {E} \left[e^{\lambda X}\right]&\leq {\frac {b-\mathbb {E} [X]}{b-a}}e^{\lambda a}+{\frac {\mathbb {E} [X]-a}{b-a}}e^{\lambda b}\\&={\frac {b}{b-a}}e^{\lambda a}+{\frac {-a}{b-a}}e^{\lambda b}\\&=e^{L(\lambda (b-a))},\end{aligned}}}$

ここで、導関数を計算すると、 ${\displaystyle L(h)={\frac {ha}{b-a}}+\ln(1+{\frac {a-e^{h}a}{b-a}})}$

${\displaystyle L(0)=L'(0)=0}$そして。${\displaystyle L''(h)=-{\frac {abe^{h}}{(b-ae^{h})^{2}}}}$

AMGM不等式から、すべての に対して であることがわかり、したがってテイラーの定理から、 となるようなものが存在することがわかる。 ${\displaystyle L''(h)\leq {\frac {1}{4}}}$${\displaystyle h}$${\displaystyle 0\leq \theta \leq 1}$

${\displaystyle L(h)=L(0)+hL'(0)+{\frac {1}{2}}h^{2}L''(h\theta )\leq {\frac {1}{8}}h^{2}.}$

したがって、。 ${\displaystyle \mathbb {E} \left[e^{\lambda X}\right]\leq e^{{\frac {1}{8}}\lambda ^{2}(b-a)^{2}}}$

• ホーフディングの不等式
• ベネットの不等式