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

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

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

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

[math]\displaystyle{ \Pr\Big( H(n) \leqslant k \Big) = \sum_{i=0}^{k} \binom{n}{i} p^i (1-p)^{n-i}\,. }[/math]

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

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

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

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

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

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

Общий случай

Пусть [math]\displaystyle{ X_1, \dots, X_n }[/math] — независимые случайные величины.

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

[math]\displaystyle{ \Pr(X_i \in [a_i, b_i]) = 1. }[/math]

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

[math]\displaystyle{ \overline{X} = (X_1 + \cdots + X_n)/n \,. }[/math]

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

[math]\displaystyle{ \Pr(\overline{X} - \mathrm{E}[\overline{X}] \geqslant t) \leqslant \exp \left( - \frac{2t^2n^2}{\sum_{i=1}^n (b_i - a_i)^2} \right), }[/math]

[math]\displaystyle{ \Pr(|\overline{X} - \mathrm{E}[\overline{X}]| \geqslant t) \leqslant 2\exp \left( - \frac{2t^2n^2}{\sum_{i=1}^n (b_i - a_i)^2} \right), }[/math]

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

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

См. также

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