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

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

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

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

$\Pr\Big(\text{ pri brosanii monety } n \text{ raz vypadaet orel ne bolee } k \text{ raz}\Big)= \sum_{i=0}^{k} \binom{n}{i} p^i (1-p)^{n-i}\,.$

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

$\Pr\Big(\text{ pri brosanii monety } n \text{ raz vypadaet orel ne bolee chem } (p-\epsilon) n \text{ raz}\Big)\leq\exp\big(-2\epsilon^2 n\big)\,.$

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

$\Pr\Big(n \text{ broskov vydayut orla po men'shey mere } (p+\epsilon) n \text{ raz}\Big)\leq\exp\big(-2\epsilon^2 n\big)\,.$

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

$\Pr\Big(n \text{ broskov monety vydayut orla v kolichestve mezhdu } (p-\epsilon)n \text{ i } (p+\epsilon)n \text{ raz}\Big)\geq 1-2\exp\big(-2\epsilon^2 n\big)\,.$

Общий случай

Пусть

$X_1, \dots, X_n \!$

— независимые случайные величины.

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

$\Pr(X_i \in [a_i, b_i]) = 1. \!$

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

$\overline{X} = (X_1 + \cdots + X_n)/n \,.$

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

$\Pr(\overline{X} - \mathrm{E}[\overline{X}] \geq t) \leq \exp \left( - \frac{2t^2n^2}{\sum_{i=1}^n (b_i - a_i)^2} \right),\!$

$\Pr(|\overline{X} - \mathrm{E}[\overline{X}]| \geq t) \leq 2\exp \left( - \frac{2t^2n^2}{\sum_{i=1}^n (b_i - a_i)^2} \right),\!$

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

Заметим, что неравенство также верно, если $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.

Связать^?

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.