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

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

(Различия между версиями)
Перейти к: навигация, поиск
(ссылки)
Строка 37: Строка 37:
== Ссылки ==
== Ссылки ==
-
Эта статья содержит материал о [http://planetmath.org/?op=getobj&from=objects&id=6049 неравенстве Бонферрони] взятый с сайта [http://planetmath.org/ planetmath.org].
+
* ''J. Galambos'', ''I. Simonelli''. Bonferroni-type inequalities — recent advances // 1st conf. on Applied Statistical Science, Lawrenceville, NJ, May 20–21, 1995 — Nova Science Publishers, Commack, NY, 1996 — pp. 127–135.
 +
* ''J. Galambos'', ''I. Simonelli''. Bonferroni-type Inequalities with Applications — Springer-Verlag, New York, 1996.
 +
* ''Klaus Dohmen''. [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.5502 Improved Inclusion-Exclusion Identities and Bonferroni Inequalities with Applications to Reliability Analysis of Coherent Systems]. 2000.
 +
* [http://planetmath.org/?op=getobj&from=objects&id=6049 Неравенство Бонферрони] — материал с сайта [http://planetmath.org/ planetmath.org].

Версия 22:46, 24 ноября 2008


Частным случаем неравенства Бонферрони является неравенство Буля (известное так же как 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»
Личные инструменты