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

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

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

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

Применение симметричной версии локальной леммы

Задача:

Пусть $G$ - граф, степени всех вершин которого не больше $d$, $P_i$ - непересекающиеся подмножества множества вершин графа $G$ такие, что [math]|P_i| \gt 2e \cdot d[/math]. Тогда можно выбрать в каждом $P_i$ по вершине так, что никакие две соединенные ребром вершины не будут выбраны.

Решение:
Уменьшим при необходимости некоторые $P_i$ так, чтобы для всех $i$ выполнялось [math]|P_i| = k[/math], где [math]k = 2ed + 1[/math]. Будем выбирать вершины [math]x_i \in P_i[/math] случайно и независимо. Каждому ребру [math](u,v)[/math] графа $G$ сопоставим событие $A_{(u, v)}$, обозначающее, что оба конца $u$, $v$ этого ребра выбраны. Вероятность каждого такого события не больше, чем $1/k^2$. В случае, если концы ребра принадлежат одному и тому же $P_i$ или один из них не принадлежит ни одному $P_i$, вероятность такого события равна $0$ и такие $A_{(u, v)}$ мы далее не рассматриваем. Для ребра $(u, v)$, для которого, скажем [math]u \in P_1, v \in P_2[/math], рассмотрим все ребра, выходящие из вершин множеств $P_1$ и $P_2$. Таких ребер, не считая ребра $(u, v)$, будет не более, чем $2kd - 2$. Заметим, что событие $A_{(u, v)}$ не зависит от всех других событий типа [math]A_{(u', v')}[/math], где [math](u', v')[/math] - ребро, соединяющее вершины множеств, отличных от $P_1$ и $P_2$.
Таким образом, для применения симметричной версии локальной леммы достаточно проверить, что [math]e(2kd − 1) / k^2 \lt 1[/math], что имеет место.

Источники информации

• Конспект лекций Ф.В. Петрова — Локальная лемма Ласло Ловаса
• Лекция А.М.Райгородского в ШАД