Неравенство Бонферрони

Материал из MachineLearning.

Версия от 18:49, 3 января 2014; Vokov (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск


Частным случаем неравенства Бонферрони является неравенство Буля (известное так же как union bound). Оно утверждает, что для конечного множества событий вероятность того, что реализуется хотя бы одно из них, не превосходит суммы вероятностей самих событий.

Таким образом для множества событий A1, A2, ..., An выполнено

P\left(\bigcup_{i=1}^n A_i\right) \leq \sum_i P\left(A_i\right).

Содержание

Неравенство Бонферрони

Неравенство Буля можно обобщить, получив более точные оценки, называемые неравенствами Бонферрони.

Обозначим

S_1 = \sum_{i=1}^n P(A_i),
S_2 = \sum_{i<j} P(A_i \cap A_j),

и для 2 < k ≤ n,

S_k = \sum P(A_{i_1}\cap \cdots \cap A_{i_k} ),

где суммирование идет по всем k-элементным подмножествам.

Тогда для нечетных k ≥ 1 выполнено

P\left( \bigcup_{i=1}^n A_i \right) \leq \sum_{j=1}^k (-1)^{j+1} S_j,

а для четных k ≥ 2

P\left( \bigcup_{i=1}^n A_i \right) \geq \sum_{j=1}^k (-1)^{j+1} S_j.

Неравенство Буля можно получить, положив k = 1.

При k = n неравенство превращается в точное равенство, известное как принцип включений-исключений.

Применение

[ToDo]

Ссылки

См. также

Поправка Бонферрони

Литература

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%91%D0%BE%D0%BD%D1%84%D0%B5%D1%80%D1%80%D0%BE%D0%BD%D0%B8»
Личные инструменты