Неравенство Беннета

В теории вероятностей неравенство обеспечивает Беннета верхнюю границу вероятности того , что сумма независимых случайных величин отклоняется от своего ожидаемого значения более чем на любую заданную величину. Неравенство Беннета было доказано Джорджем Беннетом из Университета Нового Южного Уэльса в 1962 году.

Заявление

Позволять Х ₁ , … Х _н быть независимыми случайными величинами с конечной дисперсией. Далее предположим | Икс _я - Е Икс _я | ≤ a почти наверняка для всех i и определим $S_{n}=\sum _{i=1}^{n}\left[X_{i}-\operatorname {E} (X_{i})\right]$ и $\sigma ^{2}=\sum _{i=1}^{n}\operatorname {E} (X_{i}-\operatorname {E} X_{i})^{2}.$ Тогда для любого t ≥ 0

$\Pr \left(S_{n}>t\right)\leq \exp \left(-{\frac {\sigma ^{2}}{a^{2}}}h\left({\frac {at}{\sigma ^{2}}}\right)\right),$

где h ( u ) = (1 + u )log(1 + u ) – u и log обозначает натуральный логарифм.

Обобщения и сравнения с другими границами

Обобщения см. в Freedman (1975). и Фань, Грама и Лю (2012) для мартингальной версии неравенства Беннета и его улучшения соответственно.

Неравенство Хеффдинга предполагает, что слагаемые ограничены почти наверняка, в то время как неравенство Беннета предлагает некоторое улучшение, когда дисперсии слагаемых малы по сравнению с их почти надежными границами. Однако неравенство Хеффдинга влечет за собой субгауссовы хвосты, тогда как в целом неравенство Беннета имеет пуассоновские хвосты.

Неравенство Беннета наиболее похоже на неравенства Бернштейна , первое из которых также дает концентрацию с точки зрения дисперсии и почти наверняка связано с отдельными членами. Неравенство Беннета сильнее этой границы, но его сложнее вычислить.

В обоих неравенствах, в отличие от некоторых других неравенств или предельных теорем, нет требования, чтобы составляющие переменные имели одинаковое или подобное распределение.

Пример

Предположим, что каждый X _i является независимой двоичной случайной величиной с вероятностью p . Тогда неравенство Беннета говорит, что:

$\Pr \left(\sum _{i=1}^{n}X_{i}>pn+t\right)\leq \exp \left(-nph\left({\frac {t}{np}}\right)\right).$

Для $t\geq 10np$, $h({\frac {t}{np}})\geq {\frac {t}{2np}}\log {\frac {t}{np}},$ так

$\Pr \left(\sum _{i=1}^{n}X_{i}>pn+t\right)\leq \left({\frac {t}{np}}\right)^{-t/2}$

для $t\geq 10np$.

Напротив, неравенство Хеффдинга дает оценку $\exp(-2t^{2}/n)$ и первое неравенство Бернштейна дает оценку $\exp(-{\frac {t^{2}}{2np+2t/3}})$. Для $t\gg np$, неравенство Хеффдинга дает $\exp(-\Theta (t^{2}/n))$, Бернштейн дает $\exp(-\Theta (t))$, и Беннетт дает $\exp(-\Theta (t\log {\frac {t}{np}}))$.

См. также

• Неравенство концентрации - сводка хвостовых границ случайных величин.