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

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

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

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

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

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

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

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

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

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

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

Пусть

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

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

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

${\displaystyle epd\leq 1}$

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

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

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

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

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

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

${\displaystyle 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})).}$

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

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

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

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

поскольку

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

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

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

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

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

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

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

${\displaystyle 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)}}.}$

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

${\displaystyle {\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)}$

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

${\displaystyle {\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}}}$

Из ${\displaystyle (1)}$ и ${\displaystyle (2)}$ получим

${\displaystyle 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)}$,

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

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

${\displaystyle {\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 в условии леммы. Получаем

${\displaystyle 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, arΧiv:0810.4812 [cs.DS]