Локальная лемма Ловаса
Бывают примеры, когда очень мала вероятность самого события, но тем не менее можно утверждать, что оно заведомо произойдет. Например, если каждое из большого количества независимых событий происходит с положительной вероятностью, то с положительной (но возможно очень маленькой) вероятностью произойдут все они одновременно. Следующая важная теорема обобщает это наблюдение на случай “слабо зависимых” событий.
| Теорема (Локальная лемма Ловаса): |
Пояснение:Пусть имеется семейство событий [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], что имеет место.
Источники информации
