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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Частный случай для случайных величин Бернулли[править | править вики-текст]

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

В случае для некоторого неравенство Хёфдинга ограничивает эту вероятность выражением, которое экспоненциально убывает от :

Похожим образом, в случае для некоторого неравенство Хёфдинга ограничивает вероятность того, что выпадет не меньше орлов, чем ожидаемо, выражением:

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

Общий случай[править | править вики-текст]

Пусть

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

Положим, что являются почти достоверно ограниченными, то есть, положим для , что:

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

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

которые верны для всех положительных значений t. Здесь является мат.ожиданием .

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]