Неравенство Хёфдинга (Uyjgfyuvmfk }~s;nuig)

Перейти к навигации Перейти к поиску

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

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

[править | править код]

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

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

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

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

Общий случай

[править | править код]

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

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

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

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

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

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

Примечания

[править | править код]