Изменения
Новая статья
== Локальная лемма Ловаса ==
Бывают примеры, когда очень мала вероятность самого события, но тем не менее можно утверждать, что оно заведомо произойдет. Например, если каждое из большого количества независимых событий происходит с положительной вероятностью, то с положительной ''(но возможно очень маленькой)'' вероятностью произойдут все они одновременно. Следующая важная теорема обобщает это наблюдение на случай “слабо зависимых” событий.
{{Теорема
|id=thLovas
|about=Локальная лемма Ловаса
|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= Докажем более сильное утверждение: если <tex>I = I_1 \sqcup I_2</tex>, где $I_1, I_2$ - множества
индексов, то
<br><tex>
\begin{equation}
P \left( \bigcap\limits_{i \in I} \bar{A_i} \right) \geq P \left( \bigcap\limits_{i \in I_2} \bar{A_i} \right) \cdot \prod\limits_{j \in I_1}(1-x_j)
\end{equation}
</tex><br>
Для пустого $I_2$ получаем требуемое. Докажем индукцией по <tex>|I|</tex>. Если <tex>|I| = 1</tex>, то при <tex>I_2 = I, I_1 = \emptyset</tex> имеет место равенство, а при <tex>I_1 = I, I_2 = \emptyset</tex> имеем <tex>P(\bar{A_i}) = 1 - P(A_i) \geq 1 - x_i</tex>. Теперь предположим, что для всех множеств индексов мощности меньше <tex>|I|</tex> и любых их подразбиений на два подмножества неравенство имеет место. Докажем его для $I$. Рассмотрим сначала случай <tex>|I_1| = 1, I_1 = \{ k \}</tex>. Обозначим <tex>P(\bigcap_{i \in I_2} \bar{A_i}) = p_0</tex>. Имеем
<br><tex>
\begin{equation}
P \left( \bigcap\limits_{i \in I} \bar{A_i} \right) = p_0 - P \left( \bigcap\limits_{i \in I_2} \bar{A_i} \cap A_k \right) \geq p_0 - P \left( \bigcap\limits_{i \in I_2 \setminus M(k)} \bar{A_i} \cap A_k \right) =
\end{equation}
</tex><br>
<tex>
\begin{equation}
p_0 - P \left( \bigcap\limits_{i \in I_2 \setminus M(k)} \bar{A_i} \right) \cdot P(A_k) \geq p_0(1-x_k)
\end{equation}
</tex>.<br>
Чтобы проверить выполнение последнего неравенства, перепишем его в равносильном виде
<br><tex>
\begin{equation}
p_0x_k \geq P \left( \bigcap\limits_{i \in I_2 \setminus M(k)} \bar{A_i} \right) \cdot P(A_k)
\end{equation}
</tex>.<br>
Это неравенство следует из оценки <tex>P(A_k) \leq x_k \prod_{j \in M(k)}(1-x_j)</tex> и индукционного предположения.<br>
Пусть теперь <tex>I_1 = \{ k \} \sqcup I_3, |I_3| > 0</tex>. Имеем
<br><tex>
\begin{equation}
P \left( \bigcap\limits_{i \in I} \bar{A_i} \right) \geq P \left( \bigcap\limits_{i \in I_2 \cup I_3} \bar{A_i} \right) (1 - x_k) \geq P \left( \bigcap\limits_{i \in I_2} \bar{A_i} \right) (1 - x_k) \prod\limits_{j \in I_3} (1-x_j),
\end{equation}
</tex><br>
что и требовалось ''(здесь первое неравенство уже доказано, а второе следует из индукционного предположения)''.
}}
'''Замечание.''' Как видно из доказательства, вместо независимости каждого события $A_i$ от событий, не входящих в $M(i)$ достаточно требовать для любого множества $I$ такого, что <tex>I \cap (M(i) \cup \{ i \} ) = \emptyset</tex> оценки
<br><tex>
\begin{equation}
P \left( A_i | \bigcap\limits_{j \in I} \bar{A_j} \right) \leq x_i \prod \limits_{j \in M(i)} (1-x_j).
\end{equation}
</tex><br>
Иногда используется именно такая версия локальной леммы. <br>
В случае, когда оценки на вероятности всех событий совпадают, из леммы можно получить следующее утверждение:
{{Теорема
|id=thLocalLovas
|about=Симметричная версия локальной леммы
|statement=Предположим, что <tex>e \cdot p \cdot (d + 1) \leq 1,</tex> каждое событие $A_i$ происходит с вероятностью не больше, чем $p$ и <tex>|M(i)| \leq d</tex> для всех $i$. Тогда с положительной вероятностью ни одного события $A_i$ не происходит.
|proof=Выберем <tex>x_i = x = 1 / (d + 1)</tex>. Тогда <tex>(1 − x)^d \geq 1 / e</tex>, что следует из определения числа $e$. Следовательно, <tex>p \leq x(1 − x)^d</tex>, так что выполняются условия локальной леммы.
}}
Бывают примеры, когда очень мала вероятность самого события, но тем не менее можно утверждать, что оно заведомо произойдет. Например, если каждое из большого количества независимых событий происходит с положительной вероятностью, то с положительной ''(но возможно очень маленькой)'' вероятностью произойдут все они одновременно. Следующая важная теорема обобщает это наблюдение на случай “слабо зависимых” событий.
{{Теорема
|id=thLovas
|about=Локальная лемма Ловаса
|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= Докажем более сильное утверждение: если <tex>I = I_1 \sqcup I_2</tex>, где $I_1, I_2$ - множества
индексов, то
<br><tex>
\begin{equation}
P \left( \bigcap\limits_{i \in I} \bar{A_i} \right) \geq P \left( \bigcap\limits_{i \in I_2} \bar{A_i} \right) \cdot \prod\limits_{j \in I_1}(1-x_j)
\end{equation}
</tex><br>
Для пустого $I_2$ получаем требуемое. Докажем индукцией по <tex>|I|</tex>. Если <tex>|I| = 1</tex>, то при <tex>I_2 = I, I_1 = \emptyset</tex> имеет место равенство, а при <tex>I_1 = I, I_2 = \emptyset</tex> имеем <tex>P(\bar{A_i}) = 1 - P(A_i) \geq 1 - x_i</tex>. Теперь предположим, что для всех множеств индексов мощности меньше <tex>|I|</tex> и любых их подразбиений на два подмножества неравенство имеет место. Докажем его для $I$. Рассмотрим сначала случай <tex>|I_1| = 1, I_1 = \{ k \}</tex>. Обозначим <tex>P(\bigcap_{i \in I_2} \bar{A_i}) = p_0</tex>. Имеем
<br><tex>
\begin{equation}
P \left( \bigcap\limits_{i \in I} \bar{A_i} \right) = p_0 - P \left( \bigcap\limits_{i \in I_2} \bar{A_i} \cap A_k \right) \geq p_0 - P \left( \bigcap\limits_{i \in I_2 \setminus M(k)} \bar{A_i} \cap A_k \right) =
\end{equation}
</tex><br>
<tex>
\begin{equation}
p_0 - P \left( \bigcap\limits_{i \in I_2 \setminus M(k)} \bar{A_i} \right) \cdot P(A_k) \geq p_0(1-x_k)
\end{equation}
</tex>.<br>
Чтобы проверить выполнение последнего неравенства, перепишем его в равносильном виде
<br><tex>
\begin{equation}
p_0x_k \geq P \left( \bigcap\limits_{i \in I_2 \setminus M(k)} \bar{A_i} \right) \cdot P(A_k)
\end{equation}
</tex>.<br>
Это неравенство следует из оценки <tex>P(A_k) \leq x_k \prod_{j \in M(k)}(1-x_j)</tex> и индукционного предположения.<br>
Пусть теперь <tex>I_1 = \{ k \} \sqcup I_3, |I_3| > 0</tex>. Имеем
<br><tex>
\begin{equation}
P \left( \bigcap\limits_{i \in I} \bar{A_i} \right) \geq P \left( \bigcap\limits_{i \in I_2 \cup I_3} \bar{A_i} \right) (1 - x_k) \geq P \left( \bigcap\limits_{i \in I_2} \bar{A_i} \right) (1 - x_k) \prod\limits_{j \in I_3} (1-x_j),
\end{equation}
</tex><br>
что и требовалось ''(здесь первое неравенство уже доказано, а второе следует из индукционного предположения)''.
}}
'''Замечание.''' Как видно из доказательства, вместо независимости каждого события $A_i$ от событий, не входящих в $M(i)$ достаточно требовать для любого множества $I$ такого, что <tex>I \cap (M(i) \cup \{ i \} ) = \emptyset</tex> оценки
<br><tex>
\begin{equation}
P \left( A_i | \bigcap\limits_{j \in I} \bar{A_j} \right) \leq x_i \prod \limits_{j \in M(i)} (1-x_j).
\end{equation}
</tex><br>
Иногда используется именно такая версия локальной леммы. <br>
В случае, когда оценки на вероятности всех событий совпадают, из леммы можно получить следующее утверждение:
{{Теорема
|id=thLocalLovas
|about=Симметричная версия локальной леммы
|statement=Предположим, что <tex>e \cdot p \cdot (d + 1) \leq 1,</tex> каждое событие $A_i$ происходит с вероятностью не больше, чем $p$ и <tex>|M(i)| \leq d</tex> для всех $i$. Тогда с положительной вероятностью ни одного события $A_i$ не происходит.
|proof=Выберем <tex>x_i = x = 1 / (d + 1)</tex>. Тогда <tex>(1 − x)^d \geq 1 / e</tex>, что следует из определения числа $e$. Следовательно, <tex>p \leq x(1 − x)^d</tex>, так что выполняются условия локальной леммы.
}}
