Алгоритмическая локальная лемма Ловаса

Алгоритмическая локальная лемма Ловаcа — лемма в теоретической информатике, позволяющая конструировать объекты, подчиняющиеся определённым ограничениям.

Из локальной леммы Ловаса следует, что вероятность того, что ни одно событие из некоторого множества «плохих» событий $\{A_{1},\dots ,A_{n}\}$ не произойдёт, строго положительна, если эти события удовлетворяют некоторым дополнительным ограничениям. В то же время лемма неконструктивна и не позволяет явным образом конструировать примеры объектов, для которых эти события не наступают. В случае когда указанные события определяются конечным набором независимых друг от друга случайных величин, разработанный учёными Робином Мозером и Габором Тардосом алгоритм типа «Лас-Вегас» с полиномиальным временем работы позволяет в явном виде вычислить некоторый набор значений этих величин, для которого не выполняется ни одно из рассматриваемых случайных событий.

Обзор локальной леммы Ловаса

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

Локальная лемма Ловаса является мощным инструментом, обычно используемым в вероятностном методе для доказательства существования некоторых сложных математических объектов с набором заданных признаков. Типичное доказательство сводится к рассмотрению свойств объекта с точки зрения теории вероятностей и использованию локальной леммы Ловаса для оценки вероятности отсутствия какого-либо из признаков. Отсутствие признака считается «плохим» событием, и если можно показать, что можно одновременно избежать всех таких «плохих» событий, то существование объекта доказано. Сама лемма формулируется следующим образом:

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

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

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

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

Алгоритмическая версия локальной леммы Ловаса

Локальная лемма Ловаса неконструктивна, поскольку она позволяет сделать вывод о существовании структурных свойств или сложных объектов, но не указывает, как можно их эффективно найти или построить на практике. При этом случайное семплирование из вероятностного пространства $\Omega$, вероятно, будет неэффективным, поскольку вероятность события, представляющего интерес,

$\Pr \left({\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right)$

ограничена только произведением малых величин

$\prod _{A\in {\mathcal {A}}}(1-x(A))$ и поэтому, вероятно, будет очень мала.

В предположении, что все события из ${\mathcal {A}}$ определяются конечным набором независимых друг от друга случайных величин ${\mathcal {P}}$ из $\Omega$, Робин Мозер и Габор Тардос предложили эффективный случайный алгоритм, который находит набор случайных величин в ${\mathcal {P}}$ таких, что все события из ${\mathcal {A}}$ не выполняются.

Следовательно, этот алгоритм может использоваться для эффективного построения сложных объектов с предписанными характеристиками для большинства задач, к которым применима локальная лемма Ловаса.

История

Работе Мозера и Тардоса предшествовали и другие результаты, благодаря которым был достигнут прогресс в разработке алгоритмических версий локальной леммы Ловаса. В 1991 Джозеф Бек впервые показал, что разработка алгоритмической версии леммы принципиально возможна. В его работе формулировка леммы была более строгой, чем в первоначальном неконструктивном определении. Подход Бека требовал, чтобы для каждого $A\in {\mathcal {A}}$ число зависимостей $A$ было ограничено сверху как $|\Gamma (A)|<2^{\frac {n}{48}}$. Неконструктивная версия локальной леммы допускает более слабое ограничение:

$|\Gamma (A)|<{\frac {2^{n}}{e}}.$

Эта оценка является неулучшаемой. Последующие работы постепенно сдвигали эту оценку, пока Мозер и Тардос не предъявили алгоритм, который её достигает.

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

Алгоритм

Пусть $v_{P}$ — текущая реализация случайной величины $P\in {\mathcal {P}}$, а $(v_{P})_{\mathcal {P}}$ — реализация всех случайных величин из ${\mathcal {P}}$.

Уникальное минимальное подмножество случайных величин в ${\mathcal {P}}$, которые определяют, наступит ли событие $A$, обозначается ${\text{vbl}}(A)$.

Если событие $A$ верно при вычислении $(v_{P})_{\mathcal {P}}$, будем говорить, что вычисление $(v_{P})_{\mathcal {P}}$ удовлетворяет $A$, в противном случае оно избегает $A$.

Алгоритм работает следующим образом:

1. Для каждой величины $P\in {\mathcal {P}}$ случайным образом вычислить некоторую его реализацию $v_{P}$
2. Пока существует $A\in {\mathcal {A}}$ такое, что $(v_{P})_{\mathcal {P}}$ удовлетворяет $A$:
   • Выбрать произвольное удовлетворенное событие $A\in {\mathcal {A}}$
   • Для каждой величины $P\in {\text{vbl}}(A)$ вычислить новую реализацию $v_{P}$
3. Вернуть $(v_{P})_{\mathcal {P}}$

На первом этапе алгоритм случайным образом инициализирует текущее назначение $v_{P}$ для каждой случайной величины $P\in {\mathcal {P}}$. Это означает, что значение $v_{P}$ выбирается случайным образом и независимо в соответствии с распределением случайной величины $P$. Затем алгоритм входит в основной цикл, который выполняется до тех пор, пока не будет найдена нужная реализация. На каждой итерации основного цикла алгоритм выбирает произвольное удовлетворенное событие ${\mathcal {A}}$ и повторно выбирает все случайные величины, которые определяют ${\mathcal {A}}$.

Основная теорема

Пусть ${\mathcal {P}}$ — конечное множество независимых в совокупности случайных величин в вероятностном пространстве $\Omega$, ${\mathcal {A}}$ — конечное множество событий, определяемых этими величинами. Если существует набор $x:{\mathcal {A}}\to (0,1)$ такой, что

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

то существует реализация ${\mathcal {P}}$, избегающая всех событий из ${\mathcal {A}}$. Кроме того, описанный выше рандомизированный алгоритм повторно выбирает событие $A\in {\mathcal {A}}$ не более чем

${\frac {x(A)}{1-x(A)}}$

раз, прежде чем он найдет требуемую реализацию. Таким образом, ожидаемое время выполнения алгоритма не превосходит

$\sum _{A\in {\mathcal {A}}}{\frac {x(A)}{1-x(A)}}$.

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

Требования к $x$ могут показаться сложными и неинтуитивными. Но его можно заменить тремя простыми условиями:

• $\forall A\in {\mathcal {A}}:|\Gamma (A)|\leq D$, то есть каждое событие $A$ зависит не более чем от $D$ других событий;
• $\forall A\in {\mathcal {A}}:\Pr(A)\leq p$, то есть вероятность каждого события $A$ не превосходит $p$;
• $ep(D+1)\leq 1$, где $e$ — это основание натурального логарифма.

Вариант локальной леммы Ловаса с этими тремя условиями вместо набора $x$ называется симметричной локальной леммой Ловаса. Также можно сформулировать симметричную алгоритмическую локальную лемму Ловаса:

Пусть ${\mathcal {P}}$ — конечный набор независимых в совокупности случайных величин и ${\mathcal {A}}$ — конечный набор событий, определяемых этими величинами. Если вышеуказанные три условия выполняются, то существует реализация величин из ${\mathcal {P}}$, избегающая всех событий из ${\mathcal {A}}$. Кроме того, описанный выше рандомизированный алгоритм повторно выбирает событие $A\in {\mathcal {A}}$ не больше чем ${\frac {1}{D}}$ раз, прежде чем он найдет эту реализацию. Таким образом, общее ожидаемое время выполнения алгоритма не превосходит ${\frac {n}{D}}$.

Пример

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

Пусть $\Phi$ — конъюнктивная нормальная форма формулы над переменными $X_{1},\dots ,X_{n}$, содержащая $n$ дизъюнктов и имеющая по крайней мере $k$ литералов в каждом дизъюнкте, при этом каждая переменная $X_{i}$ присутствует не более чем в ${\frac {2^{k}}{ke}}$ дизъюнктах. Тогда $\Phi$ выполнима.

Это утверждение можно доказать, используя симметричную версию алгоритмической локальной леммы Ловаса. Пусть $X_{1},\dots ,X_{n}$ — множество независимых в совокупности случайных величин ${\mathcal {P}}$, которые выбираются равномерно и независимо друг от друга. Без ограничения общности можно считать, что в каждом дизъюнкте ровно $k$ литералов. «Плохим» в данной задаче будет событие $A_{i}$, соответствующее тому, что $i$-й дизъюнкт не выполнен. Поскольку каждый дизъюнкт содержит $k$ литералов (и, следовательно, $k$ переменных) и все переменные выбираются случайным образом, можно оценить вероятность каждого «плохого» события следующим образом:

$\Pr(A_{i})=p=2^{-k}.$

Поскольку каждая переменная может появляться не более чем в ${\frac {2^{k}}{ke}}$ дизъюнктах, и в каждом дизъюнкте $k$ переменных, каждое «плохое» событие $A_{i}$ может зависеть не более чем от

$D=k\left({\frac {2^{k}}{ke}}-1\right)\leq {\frac {2^{k}}{e}}-1$

других событий, следовательно

$D+1\leq {\frac {2^{k}}{e}}.$

Если умножить обе стороны на $ep$, получится

$ep(D+1)\leq e2^{-k}{\frac {2^{k}}{e}}=1$.

Из симметричной локальной леммы Ловаса следует, что вероятность реализации $X_{1},\dots ,X_{n}$, при которой все дизъюнкты из $\Phi$ выполнены, не нулевая, и, следовательно, такая реализация должна существовать. Алгоритмическая лемма Ловаса позволяет найти такое присваивание за разумное время с помощью алгоритма, описанного выше. Алгоритм работает следующим образом:

Изначально берётся случайная реализация $X_{1},\dots ,X_{n}$. Пока вся формула $\Phi$ не становится истинной, случайным образом выбирается невыполненный дизъюнкт $C$ из $\Phi$, а затем всем переменным, которые встречаются в $C$, присваиваются новые значения, которые выбираются равномерно случайным образом. Как только все дизъюнкты из $\Phi$ выполнены, алгоритм возвращает текущую реализацию. Следовательно, алгоритмическая локальная лемма Ловаса доказывает, что этот алгоритм будет работать не более чем за

${\frac {n}{{\frac {2^{k}}{e}}-k}}$

шагов на формулах, которые удовлетворяют двум вышеуказанным условиям. Более сильная версия приведенного выше утверждения доказана Мозером, см. также работу Бирмана, Карпинского и Скотта.

Параллельная версия

Описанный выше алгоритм хорошо подходит для распараллеливания, так как параллельная генерация новых реализаций для событий $A,B\in {\mathcal {A}}$ таких, что ${\text{vbl}}(A)\cap {\text{vbl}}(B)=\emptyset$, эквивалентна последовательной. Следовательно, на каждой итерации основного цикла можно определить максимальный набор независимых удовлетворенных событий $S$ и перегенерировать все события в $S$ параллельно.

Если набор $x$ удовлетворяет несколько более строгим условиям:

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

для некоторого $\varepsilon >0$, то параллельный алгоритм даёт ожидаемое время исполнения порядка

$O\left({\frac {1}{\varepsilon }}\log \sum _{A\in {\mathcal {A}}}{\frac {x(A)}{1-x(A)}}\right)$.