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

Локальная лемма Ловаса — лемма теории вероятностей. Если некоторое количество событий не зависит друг от друга и вероятность каждого меньше 1, то вероятность того, что ни одно из событий не произойдет, положительна. Локальная лемма Ловаса позволяет ослабить условие независимости: пока события «не сильно зависимы» друг от друга и не слишком вероятны по отдельности, вероятность того, что ни одно из них не произойдет, положительна. Этот результат чаще всего используется в вероятностном методе, в частности для доказательства существования.

Существует несколько версий леммы. Симметричная версия, приведённая ниже, является самой простой и наиболее часто используемой. Более слабая версия была доказана в 1975 году Ласло Ловасом и Палом Эрдёшом в статье «Проблемы и результаты по 3-хроматическим гиперграфам и некоторые смежные вопросы». Другие версии см. (Алон & Спенсер 2000).

В 2020 году Робин Мозер и Габор Тардос получили премию Гёделя за алгоритмическую версию локальной леммы Ловаса.

Симметричная версия леммы

Пусть A₁, A₂,..., A_k – последовательность событий. Каждое событие происходит с вероятностью не более p и зависит не более чем от d других событий.

Лемма 1 (Ловас, Эрдёш 1973; опубликовано в 1975).

Пусть $4pd\leq 1$.

Тогда вероятность того, что ни одно из событий не произойдет, положительна.

Лемма 2 (Ловас 1977; опубликовано Джоэлом Спенсером).

Пусть $ep(d+1)\leq 1,$

где e = 2.718... является основанием натуральных логарифмов.

Тогда вероятность того, что ни одно из событий не произойдет, положительна.

Именно лемму 2 обычно называют «Локальной леммой Ловаса».

Лемма 3 (Ширер, 1985).

Пусть

${\begin{cases}p<{\frac {(d-1)^{d-1}}{d^{d}}},&d>1\\p<{\tfrac {1}{2}},&d=1\end{cases}}.$

Тогда вероятность того, что ни одно из событий не произойдет, положительна.

Условия, накладываемые леммой 3 оптимальны, а значит условие

$epd\leq 1$

тоже достаточно.

Асимметричная версия леммы

Формулировка асимметричной версии, учитывающей события с различными оценками вероятности:

Лемма (асимметричная версия).

Пусть ${\mathcal {A}}=\{A_{1},\ldots ,A_{n}\}$ – конечное множество событий в вероятностном пространстве Ω. Для любого $A\in {\mathcal {A}}$ пусть $\Gamma (A)$ определяет смежные с $A$ вершины в графе зависимостей (в графе зависимостей вершина $A$ не смежна с событиями, которые с ней взаимно независимы). Если существует отображение $x:{\mathcal {A}}\to [0,1)$ такое, что

$\forall A\in {\mathcal {A}}:P(A)\leq x(A)\prod _{B\in \Gamma (A)}(1-x(B)),$

то вероятность того, что ни одно из событий ${\mathcal {A}}$ не произойдет, положительна и справедливо неравенство

$P\left({\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right)\geq \prod _{i\in \{1,\cdot \cdot \cdot ,n\}}(1-x(A_{i})).$

Симметричная версия немедленно вытекает из асимметричной версии. Для этого достаточно положить

$\forall A\in {\mathcal {A}}:x(A)={\frac {1}{d+1}}$.

Тогда выполняется достаточное условие

$p\leq {\frac {1}{d+1}}\cdot {\frac {1}{e}}$,

поскольку

${\frac {1}{e}}\leq \left(1-{\frac {1}{d+1}}\right)^{d}.$

Конструктивное против неконструктивного

Как и многие утверждения о вероятностях, эта лемма неконструктивна и не содержит метода явного определения вероятностного пространства, в котором ни одно из событий не происходит. Однако известны алгоритмические версии локальной леммы с более сильными условиями (Beck 1991; Czumaj and Scheideler 2000). В 2009 году Робин Мозер и Габор Тардос сформулировали конструктивную версию локальной леммы, не требующую более сильных условий. Они также предложили распределённую версию алгоритма. В 2016 году Кай-Мин Чунг, Сет Петти, Шин-Ха Су предложили ещё два более эффективных распределённых алгоритма в статье "Распределённые алгоритмы для локальной леммы Ловаса и раскраска графов".

Неконструктивное доказательство

Докажем асимметричную версию леммы, из которой можно получить симметричную версию.

Индукцией по мощности $S$ докажем, что для всех $A\in$ ${\mathcal {A}}$ и для всех $S\subset {\mathcal {A}}$ : $A\not \in {\mathcal {A}}$ выполняется неравенство $P\left(A\mid \bigwedge _{B\in S}{\overline {B}}\right)\leq x(A)$.

База индукции. Для $S=\emptyset$ утверждение верно, так как неравенство $P(A_{i})\leq x\left(A_{i}\right)$ выполняется по условию леммы.

Шаг индукции. Необходимо показать, что неравенство выполняется для любого $S\subset {\mathcal {A}}$, если оно выполняется для всех $S_{i}\subset {\mathcal {A}}$ : $|S_{i}|<|S|$.

Положим $S_{1}=S\cap \Gamma (A),S_{2}=S\setminus S_{1}$. Применим теорему Байеса и получим

$P\left(A\mid \bigwedge _{B\in S}{\overline {B}}\right)={\frac {P\left(A\bigwedge _{B\in S_{1}}{\overline {B}}\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right)}{P\left(\bigwedge _{B\in S_{1}}{\overline {B}}\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right)}}.$

Оценим отдельно числитель и знаменатель. Пусть $S_{1}=\{B_{j1},B_{j2},\ldots ,B_{jl}\}$. Так как $A$ не зависит от событий из $S_{2}$,

${\text{Числитель}}\leq P\left(A\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right)=P(A)\leq x(A)\prod _{B\in \Gamma (A)}(1-x(B)).\qquad (1)$

Разложим знаменатель с помощью теоремы Байеса, а затем воспользуемся предположением индукции. Мы можем применить предположение индукции, поскольку каждое событие зависит от подмножества множества ${\mathcal {A}}$ и каждое из этих подмножеств имеет мощность меньшую, чем $|S|$. Получим

${\begin{aligned}&{\text{Знаменатель}}=P\left({\overline {B}}_{j1}\mid \bigwedge _{t=2}^{l}{\overline {B}}_{jt}\wedge \bigwedge _{B\in S_{2}}{\overline {B}}\right)\cdot P\left({\overline {B}}_{j2}\mid \bigwedge _{t=3}^{l}{\overline {B}}_{jt}\wedge \bigwedge _{B\in S_{2}}{\overline {B}}\right)\cdot \ldots \cdot P\left({\overline {B}}_{jl}\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right)\geq \prod _{B\in S_{1}}(1-x(B)).\qquad (2)\end{aligned}}$

Из $(1)$ и $(2)$ получим

$P\left(A\mid \bigwedge _{B\in S}{\overline {B}}\right)\leq x(A)\prod _{B\in \Gamma (A)-S_{1}}(1-x(B))\leq x(A)$,

так как значение $x$ всегда принадлежит $[0,1)$. Мы доказали, что $P\left({\overline {A}}\mid \bigwedge _{B\in S}{\overline {B}}\right)\geq 1-x(A)$.

Запишем искомую вероятность, многократно использовав определение условной вероятности. Получим

${\begin{aligned}P\left({\overline {A_{1}}}\wedge \ldots \wedge {\overline {A_{n}}}\right)=P\left({\overline {A_{1}}}\mid {\overline {A_{2}}}\wedge \ldots \wedge {\overline {A_{n}}}\right)\cdot P\left({\overline {A_{2}}}\mid {\overline {A_{3}}}\wedge \ldots \wedge {\overline {A_{n}}}\right)\cdot \ldots \cdot P\left({\overline {A_{n}}}\right)\geq \prod _{A\in {\mathcal {A}}}(1-x(A)),\end{aligned}}$

что и требовалось доказать.

Пример

Предположим, что 11n точек расположены на окружности и окрашены в n различных цветов таким образом, что каждый цвет окрашивает ровно 11 точек. В любой такой раскраске должен быть набор из n точек, содержащий одну точку каждого цвета, но не содержащий пары соседних точек.

Чтобы убедиться в этом, представьте, что вы выбираете точку каждого цвета случайным образом. Причем все точки выбираются равновероятно, то есть с вероятностью 1/11. Есть 11n различных событий, которых мы хотим избежать, они соответствуют 11n парам соседних точек на окружности. Для каждой пары вероятность выбрать обе точки в этой паре составляет не более, чем 1/121 (ровно 1/121, если две точки имеют разные цвета, иначе 0), поэтому положим p = 1/121.

Будет ли выбрана конкретная пара точек (a, b), зависит только от выбора точек цвета a и цвета b и не зависит от выбора любого другого набора точек в других n - 2 цветах. Это означает, что событие "a и b оба выбраны" зависит только от тех пар соседних точек, которые разделяют цвет либо с a, либо с b.

На окружности 11 точек, имеющих общий с a цвет (включая саму точку a), каждая из которых состоит в двух парах. Это означает, что есть 21 пара, кроме (a, b), которые включают в себя тот же цвет, что и a, и то же самое верно для b. В худшем случае эти два множества не пересекаются, поэтому мы можем взять d = 42 в условии леммы. Получаем

$ep(d+1)\approx 0.966<1.$

По локальной лемме существует положительная вероятность того, что ни одно из нежелательных событий не произойдет, то есть того, что наше множество не содержит пары соседних точек. Это означает, что множество, удовлетворяющее нашим условиям, должно существовать.

Ссылки

• Alon, Noga; Spencer, Joel H.. The probabilistic method (неопр.). — 2nd. — New York: Wiley-Interscience, 2000. — ISBN 0-471-37046-0.
• Beck, J. An algorithmic approach to the Lovász local lemma, I (англ.) // Random Structures and Algorithms : journal. — 1991. — Vol. 2, no. 4. — P. 343—365. — doi:10.1002/rsa.3240020402.
• Czumaj, Artur; Scheideler, Christian. Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lovász local lemma (англ.) // Random Structures & Algorithms : journal. — 2000. — Vol. 17, no. 3—4. — P. 213—237. — doi:10.1002/1098-2418(200010/12)17:3/4<213::AID-RSA3>3.0.CO;2-Y.
• Moser, Robin A. (2008). "A constructive proof of the Lovasz Local Lemma". arXiv:0810.4812 [cs.DS].