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

Поделись знанием:
Перейти к: навигация, поиск

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





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

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

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

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

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

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

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

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

<math>\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>X_1, \dots, X_n</math>

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

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

<math>\Pr(X_i \in [a_i, b_i]) = 1.</math>

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

<math>\overline{X} = (X_1 + \cdots + X_n)/n \,.</math>

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

<math>\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>\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>\mathrm{E}[\overline{X}]</math> является мат.ожиданием <math>\overline{X}</math>.

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

См. также

Напишите отзыв о статье "Неравенство Хёфдинга"

Примечания

Ссылки

  • Robert J. Serfling Probability Inequalities for the Sum in Sampling without Replacement // The Annals of Statistics. — 1974. — Т. 2, № 1. — С. 39–48. — DOI:10.1214/aos/1176342611.
  • Wassily Hoeffding [www.jstor.org/stable/2282952 Probability inequalities for sums of bounded random variables] // Journal of the American Statistical Association. — 1963. — Т. 58, № 301. — С. 13–30.


К:Википедия:Изолированные статьи (тип: не указан)

Отрывок, характеризующий Неравенство Хёфдинга

– Хорошо, хорошо, мне теперь некогда, – сказал Ермолов и вышел из избы. Диспозиция, составленная Толем, была очень хорошая. Так же, как и в аустерлицкой диспозиции, было написано, хотя и не по немецки:
«Die erste Colonne marschiert [Первая колонна идет (нем.) ] туда то и туда то, die zweite Colonne marschiert [вторая колонна идет (нем.) ] туда то и туда то» и т. д. И все эти колонны на бумаге приходили в назначенное время в свое место и уничтожали неприятеля. Все было, как и во всех диспозициях, прекрасно придумано, и, как и по всем диспозициям, ни одна колонна не пришла в свое время и на свое место.
Когда диспозиция была готова в должном количестве экземпляров, был призван офицер и послан к Ермолову, чтобы передать ему бумаги для исполнения. Молодой кавалергардский офицер, ординарец Кутузова, довольный важностью данного ему поручения, отправился на квартиру Ермолова.
– Уехали, – отвечал денщик Ермолова. Кавалергардский офицер пошел к генералу, у которого часто бывал Ермолов.
– Нет, и генерала нет.
Кавалергардский офицер, сев верхом, поехал к другому.
– Нет, уехали.
«Как бы мне не отвечать за промедление! Вот досада!» – думал офицер. Он объездил весь лагерь. Кто говорил, что видели, как Ермолов проехал с другими генералами куда то, кто говорил, что он, верно, опять дома. Офицер, не обедая, искал до шести часов вечера. Нигде Ермолова не было и никто не знал, где он был. Офицер наскоро перекусил у товарища и поехал опять в авангард к Милорадовичу. Милорадовича не было тоже дома, но тут ему сказали, что Милорадович на балу у генерала Кикина, что, должно быть, и Ермолов там.
– Да где же это?
– А вон, в Ечкине, – сказал казачий офицер, указывая на далекий помещичий дом.
– Да как же там, за цепью?
– Выслали два полка наших в цепь, там нынче такой кутеж идет, беда! Две музыки, три хора песенников.
Офицер поехал за цепь к Ечкину. Издалека еще, подъезжая к дому, он услыхал дружные, веселые звуки плясовой солдатской песни.
«Во олузя а ах… во олузях!..» – с присвистом и с торбаном слышалось ему, изредка заглушаемое криком голосов. Офицеру и весело стало на душе от этих звуков, но вместе с тем и страшно за то, что он виноват, так долго не передав важного, порученного ему приказания. Был уже девятый час. Он слез с лошади и вошел на крыльцо и в переднюю большого, сохранившегося в целости помещичьего дома, находившегося между русских и французов. В буфетной и в передней суетились лакеи с винами и яствами. Под окнами стояли песенники. Офицера ввели в дверь, и он увидал вдруг всех вместе важнейших генералов армии, в том числе и большую, заметную фигуру Ермолова. Все генералы были в расстегнутых сюртуках, с красными, оживленными лицами и громко смеялись, стоя полукругом. В середине залы красивый невысокий генерал с красным лицом бойко и ловко выделывал трепака.
– Ха, ха, ха! Ай да Николай Иванович! ха, ха, ха!..
Офицер чувствовал, что, входя в эту минуту с важным приказанием, он делается вдвойне виноват, и он хотел подождать; но один из генералов увидал его и, узнав, зачем он, сказал Ермолову. Ермолов с нахмуренным лицом вышел к офицеру и, выслушав, взял от него бумагу, ничего не сказав ему.
– Ты думаешь, это нечаянно он уехал? – сказал в этот вечер штабный товарищ кавалергардскому офицеру про Ермолова. – Это штуки, это все нарочно. Коновницына подкатить. Посмотри, завтра каша какая будет!


На другой день, рано утром, дряхлый Кутузов встал, помолился богу, оделся и с неприятным сознанием того, что он должен руководить сражением, которого он не одобрял, сел в коляску и выехал из Леташевки, в пяти верстах позади Тарутина, к тому месту, где должны были быть собраны наступающие колонны. Кутузов ехал, засыпая и просыпаясь и прислушиваясь, нет ли справа выстрелов, не начиналось ли дело? Но все еще было тихо. Только начинался рассвет сырого и пасмурного осеннего дня. Подъезжая к Тарутину, Кутузов заметил кавалеристов, ведших на водопой лошадей через дорогу, по которой ехала коляска. Кутузов присмотрелся к ним, остановил коляску и спросил, какого полка? Кавалеристы были из той колонны, которая должна была быть уже далеко впереди в засаде. «Ошибка, может быть», – подумал старый главнокомандующий. Но, проехав еще дальше, Кутузов увидал пехотные полки, ружья в козлах, солдат за кашей и с дровами, в подштанниках. Позвали офицера. Офицер доложил, что никакого приказания о выступлении не было.