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

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

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

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

Пояснение: Пусть имеется семейство событий [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]

Докажем более сильное утверждение: если [math]I = I_1 \sqcup I_2[/math], где $I_1, I_2$ - множества индексов, то [math] \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} [/math] Для пустого $I_2$ получаем требуемое. Докажем индукцией по [math]|I|[/math]. Если [math]|I| = 1[/math], то при [math]I_2 = I, I_1 = \emptyset[/math] имеет место равенство, а при [math]I_1 = I, I_2 = \emptyset[/math] имеем [math]P(\bar{A_i}) = 1 - P(A_i) \geq 1 - x_i[/math]. Теперь предположим, что для всех множеств индексов мощности меньше [math]|I|[/math] и любых их подразбиений на два подмножества неравенство имеет место. Докажем его для $I$. Рассмотрим сначала случай [math]|I_1| = 1, I_1 = \{ k \}[/math]. Обозначим [math]P(\bigcap_{i \in I_2} \bar{A_i}) = p_0[/math]. Имеем [math] \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} [/math] [math] \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} [/math]. Чтобы проверить выполнение последнего неравенства, перепишем его в равносильном виде [math] \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} [/math]. Это неравенство следует из оценки [math]P(A_k) \leq x_k \prod_{j \in M(k)}(1-x_j)[/math] и индукционного предположения. Пусть теперь [math]I_1 = \{ k \} \sqcup I_3, |I_3| \gt 0[/math]. Имеем [math] \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} [/math] что и требовалось (здесь первое неравенство уже доказано, а второе следует из индукционного предположения).

[math]\triangleleft[/math]

Замечание. Как видно из доказательства, вместо независимости каждого события $A_i$ от событий, не входящих в $M(i)$ достаточно требовать для любого множества $I$ такого, что [math]I \cap (M(i) \cup \{ i \} ) = \emptyset[/math] оценки
[math] \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} [/math]
Иногда используется именно такая версия локальной леммы.
В случае, когда оценки на вероятности всех событий совпадают, из леммы можно получить следующее утверждение:

Теорема (Симметричная версия локальной леммы):

Предположим, что [math]e \cdot p \cdot (d + 1) \leq 1,[/math] каждое событие $A_i$ происходит с вероятностью не больше, чем $p$ и [math]|M(i)| \leq d[/math] для всех $i$. Тогда с положительной вероятностью ни одного события $A_i$ не происходит.

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

[math]\triangleright[/math]

Выберем [math]x_i = x = 1 / (d + 1)[/math]. Тогда [math](1 − x)^d \geq 1 / e[/math], что следует из определения числа $e$. Следовательно, [math]p \leq x(1 − x)^d[/math], так что выполняются условия локальной леммы.

[math]\triangleleft[/math]