Обсуждение участника:Mishenkoil — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Локальная лемма Ловаса: новая тема)
 
(Полностью удалено содержимое страницы)
 
(не показано 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