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

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

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

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

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

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

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