Лемма Хёффдингса - Hoeffdings lemma - Wikipedia

В теория вероятности, Лемма Хёффдинга является неравенство что ограничивает момент-производящая функция любой ограниченный случайная переменная.^[1] Он назван в честь Финский –Американец математик-статистик Василий Хёффдинг.

Доказательство леммы Хёффдинга использует Теорема Тейлора и Неравенство Дженсена. Сама лемма Хёффдинга используется при доказательстве Неравенство МакДиармида.

Утверждение леммы

Позволять Икс - любая случайная величина с действительным знаком с ожидаемое значение ${\displaystyle \mathbb {E} [X]=\eta }$, так что ${\displaystyle a\leq X\leq b}$ почти наверняка, т.е. с вероятностью единица. Тогда для всех ${\displaystyle \lambda \in \mathbb {R} }$,

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

Обратите внимание, что приведенное ниже доказательство основано на предположении, что случайная величина ${\displaystyle X}$ имеет нулевое ожидание (т.е. предполагая, что ${\displaystyle \eta =0}$), следовательно ${\displaystyle a}$ и ${\displaystyle b}$ в лемме должно удовлетворять ${\displaystyle a\leq 0\leq b}$. Для любой случайной величины, которая не подчиняется этому предположению, мы можем определить ${\displaystyle {\tilde {X}}\triangleq X-\eta }$, которые подчиняются предположениям и применяют доказательство на ${\displaystyle {\tilde {X}}}$.

Краткое доказательство леммы

С ${\displaystyle e^{\lambda x}}$ является выпуклой функцией от ${\displaystyle x}$, у нас есть

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

Так, ${\displaystyle \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}.}$

Позволять ${\displaystyle h=\lambda (b-a)}$, ${\displaystyle p={\frac {-a}{b-a}}}$ и ${\displaystyle L(h)=-hp+\ln(1-p+pe^{h})}$

Потом, ${\displaystyle {\frac {b-\mathbb {E} [X]}{b-a}}e^{\lambda a}+{\frac {\mathbb {E} [X]-a}{b-a}}e^{\lambda b}=e^{L(h)}}$ поскольку ${\displaystyle \mathbb {E} [X]=0}$

Взяв производную от ${\displaystyle L(h)}$,

${\displaystyle L(0)=L^{'}(0)=0{\text{ and }}L^{''}(h)\leq {\frac {1}{4}}}$ для всех ч.

По расширению Тейлора,

${\displaystyle L(h)\leq {\frac {1}{8}}h^{2}={\frac {1}{8}}\lambda ^{2}(b-a)^{2}}$

Следовательно, ${\displaystyle \mathbb {E} \left[e^{\lambda X}\right]\leq e^{{\frac {1}{8}}\lambda ^{2}(b-a)^{2}}}$

(Доказательство ниже - это то же доказательство с дополнительными пояснениями.)

Более подробное доказательство

Сначала обратите внимание, что если один из ${\displaystyle a}$ или же ${\displaystyle b}$ равно нулю, то ${\displaystyle \textstyle \mathbb {P} \left(X=0\right)=1}$ и следует неравенство. Если оба ненулевые, то ${\displaystyle a}$ должно быть отрицательным и ${\displaystyle b}$ должен быть положительным.

Далее напомним, что ${\displaystyle e^{sx}}$ это выпуклая функция на реальной линии:

${\displaystyle \forall x\in [a,b]:\qquad e^{sx}\leq {\frac {b-x}{b-a}}e^{sa}+{\frac {x-a}{b-a}}e^{sb}.}$

Применение ${\displaystyle \mathbb {E} }$ к обеим сторонам указанного неравенства дает нам:

${\displaystyle {\begin{aligned}\mathbb {E} \left[e^{sX}\right]&\leq {\frac {b-\mathbb {E} [X]}{b-a}}e^{sa}+{\frac {\mathbb {E} [X]-a}{b-a}}e^{sb}\\&={\frac {b}{b-a}}e^{sa}+{\frac {-a}{b-a}}e^{sb}&&\mathbb {E} (X)=0\\&=(1-\theta )e^{sa}+\theta e^{sb}&&\theta =-{\frac {a}{b-a}}>0\\&=e^{sa}\left(1-\theta +\theta e^{s(b-a)}\right)\\&=\left(1-\theta +\theta e^{s(b-a)}\right)e^{-s\theta (b-a)}\\\end{aligned}}}$

Позволять ${\displaystyle u=s(b-a)}$ и определите:

${\displaystyle {\begin{cases}\varphi :\mathbb {R} \to \mathbb {R} \\\varphi (u)=-\theta u+\log \left(1-\theta +\theta e^{u}\right)\end{cases}}}$

${\displaystyle \varphi }$ хорошо определен на ${\displaystyle \mathbb {R} }$, чтобы увидеть это, мы вычисляем:

${\displaystyle {\begin{aligned}1-\theta +\theta e^{u}&=\theta \left({\frac {1}{\theta }}-1+e^{u}\right)\\&=\theta \left(-{\frac {b}{a}}+e^{u}\right)\\&>0&&\theta >0,\quad {\frac {b}{a}}<0\end{aligned}}}$

Определение ${\displaystyle \varphi }$ подразумевает

${\displaystyle \mathbb {E} \left[e^{sX}\right]\leq e^{\varphi (u)}.}$

К Теорема Тейлора, для каждого реального ${\displaystyle u}$ существует ${\displaystyle v}$ между ${\displaystyle 0}$ и ${\displaystyle u}$ такой, что

${\displaystyle \varphi (u)=\varphi (0)+u\varphi '(0)+{\tfrac {1}{2}}u^{2}\varphi ''(v).}$

Обратите внимание, что:

${\displaystyle {\begin{aligned}\varphi (0)&=0\\\varphi '(0)&=-\theta +\left.{\frac {\theta e^{u}}{1-\theta +\theta e^{u}}}\right|_{u=0}\\&=0\\[6pt]\varphi ''(v)&={\frac {\theta e^{v}\left(1-\theta +\theta e^{v}\right)-\theta ^{2}e^{2v}}{\left(1-\theta +\theta e^{v}\right)^{2}}}\\[6pt]&={\frac {\theta e^{v}}{1-\theta +\theta e^{v}}}\left(1-{\frac {\theta e^{v}}{1-\theta +\theta e^{v}}}\right)\\[6pt]&=t(1-t)&&t={\frac {\theta e^{v}}{1-\theta +\theta e^{v}}}\\&\leq {\tfrac {1}{4}}&&t>0\end{aligned}}}$

Следовательно,

${\displaystyle \varphi (u)\leq 0+u\cdot 0+{\tfrac {1}{2}}u^{2}\cdot {\tfrac {1}{4}}={\tfrac {1}{8}}u^{2}={\tfrac {1}{8}}s^{2}(b-a)^{2}.}$

Из этого следует

${\displaystyle \mathbb {E} \left[e^{sX}\right]\leq \exp \left({\tfrac {1}{8}}s^{2}(b-a)^{2}\right).}$

Смотрите также

• Неравенство Хёффдинга
• Неравенство Беннета

Примечания

1. Паскаль Массарт (26 апреля 2007 г.). Неравенство концентраций и выбор модели: Ecole d'Eté de Probabilités de Saint-Flour XXXIII - 2003. Springer. п. 21. ISBN  978-3-540-48503-2.