Обсуждение участника:Mishenkoil

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

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

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

Пояснение: Пусть имеется семейство событий [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| = 2ed + 1[/math]. Обозначим [math]2ed + 1[/math] как [math]k[/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$ и такие события мы далее не рассматриваем. Для ребра $(u, v)$, для которого, скажем [math]u \in P_1, v \in P_2[/math], рассмотрим все ребра, выходящие из вершин множеств $P_1$ и $P_2$. Всего будет не более, чем $2kd - 2$ таких ребер (не считая ребра $(u, v)$). Заметим, что событие $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], что имеет место.

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

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