Обсуждение участника:Mishenkoil

Локальная лемма Ловаса

Бывают примеры, когда очень мала вероятность самого события, но тем не менее можно утверждать, что оно заведомо произойдет. Например, если каждое из большого количества независимых событий происходит с положительной вероятностью, то с положительной (но возможно очень маленькой) вероятностью произойдут все они одновременно. Следующая важная теорема обобщает это наблюдение на случай “слабо зависимых” событий.

Теорема (Локальная лемма Ловаса):

Пояснение: Пусть имеется семейство событий [math]A_1, A_2, ... , A_n[/math], и для каждого события [math]A_i[/math] выделено множество индексов [math]M(i) \subset \{ 1, 2, . . . , n \}[/math] такое, что [math]A_i[/math] не зависит от всех событий [math]A_j , j \notin M(i)[/math]. Это означает, что для любого события [math]B[/math], выражаемого через множество событий [math]\{ A_j, j \notin M(i) \}[/math], события [math]A_i[/math] и [math]B[/math] независимы. Через [math]\bar{A}[/math] будем обозначать дополнение события [math]A[/math]. Формулировка теоремы: Предположим, что нашлись такие числа [math]x_i \in (0, 1)[/math], что для всех [math]i[/math] выполняется неравенство [math]p(A_i) \leq x_i\prod_{j \in M(i)}(1-x_j)[/math]. Тогда [math]p(\bigcap \bar{A_i}) \geq \prod(1-x_i)[/math] - в частности, с положительной вероятностью ни одно из событий [math]A_i[/math] не происходит

Доказательство:

[math]\triangleright[/math]

puk-puk

[math]\triangleleft[/math]