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

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

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

Содержание

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

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

\Pr\Big(\text{ pri brosanii monety } n \text{ raz vypadaet orel ne bolee } k \text{ raz}\Big)= \sum_{i=0}^{k} \binom{n}{i} p^i (1-p)^{n-i}\,.

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

\Pr\Big(\text{ pri brosanii monety } n \text{ raz vypadaet orel ne bolee chem } (p-\epsilon) n \text{ raz}\Big)\leq\exp\big(-2\epsilon^2 n\big)\,.

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

\Pr\Big(n \text{ broskov vydayut orla po men'shey mere } (p+\epsilon) n \text{ raz}\Big)\leq\exp\big(-2\epsilon^2 n\big)\,.

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

\Pr\Big(n \text{ broskov monety vydayut orla v kolichestve mezhdu } (p-\epsilon)n \text{ i } (p+\epsilon)n \text{ raz}\Big)\geq 1-2\exp\big(-2\epsilon^2 n\big)\,.

Общий случай

Пусть

X_1, \dots, X_n \!

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

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

См. также

Примечания

  1. ↑ Hoeffding, 1963
  2. ↑ Serfling, 1974

Ссылки

Wiki letter w.svg
 На эту статью не ссылаются другие статьи Википедии.
Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное



Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»