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

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

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

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

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

Пусть 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.}$

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

Примечания

1. Paul Erdős, László Lovász. Problems and results on 3-chromatic hypergraphs and some related questions (англ.) // North-Holland Pub. Co. — 1975. Архивировано 4 марта 2016 года.
2. Former doctoral student Robin Moser receives prestigious Gödel Prize (англ.). ethz.ch. Дата обращения: 20 апреля 2020. Архивировано 31 октября 2021 года.
3. ACM SIGACT - Gödel Prize  (неопр.). sigact.org. Дата обращения: 20 апреля 2020. Архивировано 9 января 2020 года.
4. Spencer, J. Asymptotic lower bounds for Ramsey functions // Discrete Mathematics. — 1977. — Т. 20. — С. 69—76. — doi:10.1016/0012-365x(77)90044-9.
5. Shearer, J. On a problem of Spencer (неопр.) // Combinatorica^[англ.]. — 1985. — Т. 5, № 3. — С. 241—245. — doi:10.1007/BF02579368.
6. József Beck. An algorithmic approach to the Lovász local lemma. I (англ.) // Random Structures & Algorithms. — 1991. — Vol. 2, iss. 4. — P. 343—365. — ISSN 1098-2418. — doi:10.1002/rsa.3240020402. Архивировано 10 декабря 2019 года.
7. Artur Czumaj, Christian Scheideler. Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lovász local lemma (англ.) // Random Structures & Algorithms. — 2000. — Vol. 17, iss. 3—4. — P. 213—237. — ISSN 1098-2418. — doi:10.1002/1098-2418(200010/12)17:3/43.0.CO;2-Y.
8. Robin A. Moser, Gábor Tardos. A constructive proof of the general lovász local lemma (англ.) // Journal of the ACM. — 2009. Архивировано 14 июня 2020 года.
9. Robin A. Moser, Gábor Tardos. A constructive proof of the general lovász local lemma (англ.) // Journal of the ACM. — 2010. — February. Архивировано 8 марта 2022 года.
10. Kai-Min Chung, Seth Pettie & Hsin-Hao Su. Distributed algorithms for the Lovász local lemma and graph coloring  (неопр.). SpringerLink (21 ноября 2016). Дата обращения: 1 мая 2020. Архивировано 3 июня 2020 года.

Ссылки

• 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].