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

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

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

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

$\mathrm{Pr}(H(n)⩽k)=\sum _{i=0}^k(\genfrac{}{}{0ex}{}{n}{i})p^i(1-p{)}^{n-i}.$

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

$\mathrm{Pr}(H(n)⩽(p-\epsilon )n)⩽\exp (-2{\epsilon }^{2}n).$

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

$\mathrm{Pr}(H(n)⩾(p+\epsilon )n)⩽\exp (-2{\epsilon }^{2}n).$

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

$\mathrm{Pr}((p-\epsilon )n⩽H(n)⩽(p+\epsilon )n)⩾1-2\exp (-2{\epsilon }^{2}n).$

Общий случай

Пусть $X_1,\dots ,X_n$ — независимые случайные величины.

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

$\mathrm{Pr}(X_i\in [a_i,b_i])=1.$

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

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

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

$\mathrm{Pr}(\bar{X}-\mathrm{E}[\bar{X}]⩾t)⩽\exp (-\frac{2t^2{n}^2}{\sum _{i=1}^n(b_i-a_i{)}^2}),$

$\mathrm{Pr}(|\bar{X}-\mathrm{E}[\bar{X}]|⩾t)⩽2\exp (-\frac{2t^2{n}^2}{\sum _{i=1}^n(b_i-a_i{)}^2}),$

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

Заметим, что неравенство также верно, если $X_i$ были получены с использованием выборки без замены, в данном случае случайные переменные не являются больше независимыми. Доказательство этого утверждения можно найти в статье Хёфдинга. Для несколько лучших оценок границ в случае выборки без замены, см., например, статью, Шаблон:Sfn.

См. также

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

Ссылки

• Шаблон:Статья
• Шаблон:Статья