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

Неравенство Хёфдинга даёт верхнюю границу вероятности того, что сумма случайных величин отклоняется от своего математического ожидания. Неравенство Хёфдинга было доказано Василием Хёфдингом^[англ.] в 1963 году.^[1] Неравенство Хёфдинга является частным случаем неравенства Азумы и более общим случаем неравенства Бернштейна^[англ.], доказанного Сергеем Бернштейном в 1923 году. Они также являются частными случаями неравенства МакДиармида.

Частный случай для случайных величин Бернулли

Неравенство Хефдинга может быть применено к важному частному случаю одинаково распределенных бернуллиевских случайных величин, и, как неравенство, часто используется в комбинаторике и информатике. Рассматриваем смещённую монету, у которой орёл выпадает с вероятностью ${\displaystyle p}$ и решка — с вероятностью ${\displaystyle 1-p}$. Мы бросаем монету ${\displaystyle n}$ раз. Математическое ожидание того, сколько раз монета упадет орлом, есть ${\displaystyle p\cdot n}$. Далее, вероятность того, что монета упадет орлом не более ${\displaystyle k}$ раз, может быть точно оценена выражением:

${\displaystyle \Pr {\Big (}H(n)\leqslant k{\Big )}=\sum _{i=0}^{k}{\binom {n}{i}}p^{i}(1-p)^{n-i}\,.}$

В случае ${\displaystyle k=(p-\varepsilon )n}$ для некоторого ${\displaystyle \varepsilon >0}$ неравенство Хёфдинга ограничивает эту вероятность выражением, которое экспоненциально убывает от ${\displaystyle \varepsilon ^{2}\cdot n}$:

${\displaystyle \Pr {\Big (}H(n)\leqslant (p-\varepsilon )n{\Big )}\leqslant \exp {\big (}-2\varepsilon ^{2}n{\big )}\,.}$

Похожим образом, в случае ${\displaystyle k=(p+\varepsilon )n}$ для некоторого ${\displaystyle \varepsilon >0}$ неравенство Хёфдинга ограничивает вероятность того, что выпадет не меньше ${\displaystyle \varepsilon n}$ орлов, чем ожидаемо, выражением:

${\displaystyle \Pr {\Big (}H(n)\geqslant (p+\varepsilon )n{\Big )}\leqslant \exp {\big (}-2\varepsilon ^{2}n{\big )}\,.}$

Таким образом, неравенство Хёфдинга означает, что число выпадений орла, концентрируется вокруг среднего, с экспоненциально малым хвостом.

${\displaystyle \Pr {\Big (}(p-\varepsilon )n\leqslant H(n)\leqslant (p+\varepsilon )n{\Big )}\geqslant 1-2\exp {\big (}-2\varepsilon ^{2}n{\big )}\,.}$

Общий случай

Пусть ${\displaystyle X_{1},\dots ,X_{n}}$ — независимые случайные величины.

Положим, что ${\displaystyle X_{i}}$ являются почти достоверно ограниченными, то есть, положим для ${\displaystyle 1\leqslant i\leqslant n}$, что:

${\displaystyle \Pr(X_{i}\in [a_{i},b_{i}])=1.}$

Мы определяем эмпирическое среднее этих переменных:

${\displaystyle {\overline {X}}=(X_{1}+\cdots +X_{n})/n\,.}$

Теорема 2 из Hoeffding (1963), доказывает неравенства:

${\displaystyle \Pr({\overline {X}}-\mathrm {E} [{\overline {X}}]\geqslant t)\leqslant \exp \left(-{\frac {2t^{2}n^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),}$

${\displaystyle \Pr(|{\overline {X}}-\mathrm {E} [{\overline {X}}]|\geqslant t)\leqslant 2\exp \left(-{\frac {2t^{2}n^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),}$

которые верны для всех положительных значений t. Здесь ${\displaystyle \mathrm {E} [{\overline {X}}]}$ является мат.ожиданием ${\displaystyle {\overline {X}}}$.

Заметим, что неравенство также верно, если ${\displaystyle X_{i}}$ были получены с использованием выборки без замены, в данном случае случайные переменные не являются больше независимыми. Доказательство этого утверждения можно найти в статье Хёфдинга. Для несколько лучших оценок границ в случае выборки без замены, см., например, статью, ^[2].

См. также

• Неравенство Чебышёва
• Неравенство Маркова

Примечания

1. Hoeffding, 1963.
2. Serfling, 1974.

Ссылки

• Robert J. Serfling. Probability Inequalities for the Sum in Sampling without Replacement // The Annals of Statistics. — 1974. — Т. 2, № 1. — С. 39–48. — doi:10.1214/aos/1176342611.
• Wassily Hoeffding. Probability inequalities for sums of bounded random variables // Journal of the American Statistical Association. — 1963. — Т. 58, № 301. — С. 13–30.