Материал из Викиконспекты
|
|
| (не показано 26 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| − | == Локальная лемма Ловаса ==
| |
| | | | |
| − | Бывают примеры, когда очень мала вероятность самого события, но тем не менее можно утверждать, что оно заведомо произойдет. Например, если каждое из большого количества независимых событий происходит с положительной вероятностью, то с положительной (но возможно очень маленькой) вероятностью произойдут все они одновременно. Следующая важная теорема обобщает это наблюдение на случай “слабо зависимых” событий.
| |
| − |
| |
| − | {{Теорема
| |
| − | |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
| |
| − | }}
| |
Текущая версия на 22:30, 12 мая 2022
