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

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

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

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

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

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

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

\Pr\Big( H(n) \leqslant (p-\varepsilon) n \Big)\leqslant\exp\big(-2\varepsilon^2 n\big)\,.

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

\Pr\Big( H(n) \geqslant (p+\varepsilon) n \Big)\leqslant\exp\big(-2\varepsilon^2 n\big)\,.

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

\Pr\Big( (p-\varepsilon)n \leqslant H(n) \leqslant (p+\varepsilon)n \Big)\geqslant 1-2\exp\big(-2\varepsilon^2 n\big)\,.

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

Пусть

X_1, \dots, X_n \!

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

Положим, что X_i являются почти достоверно ограниченными, то есть, положим для 1 \leqslant i \leqslant 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}] \geqslant t) \leqslant \exp \left( - \frac{2t^2n^2}{\sum_{i=1}^n (b_i - a_i)^2} \right),\!
\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),\!

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

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

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

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

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