50
правок
Изменения
→Локальная лемма Ловаса: новая тема
== Локальная лемма Ловаса ==
Бывают примеры, когда очень мала вероятность самого события, но тем не менее можно утверждать, что оно заведомо произойдет. Например, если каждое из большого количества независимых событий происходит с положительной вероятностью, то с положительной (но возможно очень маленькой) вероятностью произойдут все они одновременно. Следующая важная теорема обобщает это наблюдение на случай “слабо зависимых” событий.
{{Теорема
|id=thLovas
|author=Локальная лемма Ловаса
|statement='''Пояснение:'''<br>Пусть имеется семейство событий <tex>A_1, A_2, ... , A_n</tex>, и для каждого события <tex>A_i</tex> выделено множество индексов <tex>M(i) \subset \{ 1, 2, . . . , n \}</tex> такое, что <tex>A_i</tex> не зависит от всех событий <tex>A_j
, j \notin M(i)</tex>. Это означает, что для любого события <tex>B</tex>, выражаемого через множество событий <tex>\{ A_j, j \notin M(i) \}</tex>, события <tex>A_i</tex> и <tex>B</tex> независимы. Через <tex>\bar{A}</tex> будем обозначать дополнение события <tex>A</tex>. <br>
'''Формулировка теоремы:'''<br>
Предположим, что нашлись такие числа <tex>x_i \in (0, 1)</tex>, что для всех <tex>i</tex> выполняется неравенство <tex>p(A_i) \leq x_i\prod_{j \in M(i)}(1-x_j)</tex>. Тогда <tex>p(\bigcap \bar{A_i}) \geq \prod(1-x_i)</tex> - в частности, с положительной вероятностью ни одно из событий <tex>A_i</tex> не происходит
|proof=puk-puk
}}
Бывают примеры, когда очень мала вероятность самого события, но тем не менее можно утверждать, что оно заведомо произойдет. Например, если каждое из большого количества независимых событий происходит с положительной вероятностью, то с положительной (но возможно очень маленькой) вероятностью произойдут все они одновременно. Следующая важная теорема обобщает это наблюдение на случай “слабо зависимых” событий.
{{Теорема
|id=thLovas
|author=Локальная лемма Ловаса
|statement='''Пояснение:'''<br>Пусть имеется семейство событий <tex>A_1, A_2, ... , A_n</tex>, и для каждого события <tex>A_i</tex> выделено множество индексов <tex>M(i) \subset \{ 1, 2, . . . , n \}</tex> такое, что <tex>A_i</tex> не зависит от всех событий <tex>A_j
, j \notin M(i)</tex>. Это означает, что для любого события <tex>B</tex>, выражаемого через множество событий <tex>\{ A_j, j \notin M(i) \}</tex>, события <tex>A_i</tex> и <tex>B</tex> независимы. Через <tex>\bar{A}</tex> будем обозначать дополнение события <tex>A</tex>. <br>
'''Формулировка теоремы:'''<br>
Предположим, что нашлись такие числа <tex>x_i \in (0, 1)</tex>, что для всех <tex>i</tex> выполняется неравенство <tex>p(A_i) \leq x_i\prod_{j \in M(i)}(1-x_j)</tex>. Тогда <tex>p(\bigcap \bar{A_i}) \geq \prod(1-x_i)</tex> - в частности, с положительной вероятностью ни одно из событий <tex>A_i</tex> не происходит
|proof=puk-puk
}}
