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

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

При заданном конечном наборе плохих событий { A ₁ , ..., A _n } в вероятностном пространстве с ограниченной зависимостью между A _i и с определенными границами их соответствующих вероятностей локальная лемма Ловаса доказывает, что с ненулевой вероятностью всех этих событий можно избежать. Однако лемма неконструктивна, поскольку не дает никакого представления о том, как избежать плохих событий.

Если события { A ₁ , ..., A _n } определяются конечным набором взаимно независимых случайных величин, то простой алгоритм Лас-Вегаса с ожидаемым полиномиальным временем выполнения, предложенный Робином Мозером и Габором Тардосом ^[1], может вычислить назначение случайным величинам таким образом, чтобы избежать всех событий.

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

Пусть будет конечным множеством событий в вероятностном пространстве Ω. Для пусть обозначает подмножество такое, что не зависит от набора событий . Если существует присвоение вещественных чисел событиям такое, что${\displaystyle {\mathcal {A}}=\{A_{1},\ldots ,A_{n}\}}$${\displaystyle A\in {\mathcal {A}}}$${\displaystyle \Гамма (А)}$${\displaystyle {\mathcal {A}}}$${\displaystyle А}$${\displaystyle {\mathcal {A}}\setminus (\{A\}\cup \Gamma (A))}$${\displaystyle x:{\mathcal {A}}\rightarrow (0,1)}$

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

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

${\displaystyle \Pr \left[\,{\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\,\right]\geq \prod _{A\in {\mathcal {A}}}(1-x(A)).}$

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

${\displaystyle \Pr \left[{\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right]}$

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

${\displaystyle \prod _{A\in {\mathcal {A}}}(1-x(A))}$

и поэтому, вероятно, будет очень маленьким.

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

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

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

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

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

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

Для любой случайной величины обозначает текущее присвоение (оценку) P. Присвоение (оценка) всем случайным величинам обозначается .${\displaystyle P\in {\mathcal {P}},v_{P}}$${\displaystyle (v_{P})_{\mathcal {P}}}$

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

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

Учитывая набор плохих событий, которых мы хотим избежать, который определяется набором взаимно независимых случайных величин , алгоритм работает следующим образом:${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {P}}}$

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

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

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

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

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

то существует присвоение значений переменным, избегающее всех событий в .${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {A}}}$

Более того, описанный выше рандомизированный алгоритм повторно выбирает событие максимум за ожидаемое время.${\displaystyle A\in {\mathcal {A}}}$

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

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

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

Доказательство этой теоремы с использованием метода сжатия энтропии можно найти в статье Мозера и Тардоса ^[1].

Требование функции назначения x, удовлетворяющей набору неравенств в теореме выше, является сложным и неинтуитивным. Но это требование можно заменить тремя простыми условиями:

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

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

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

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

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

Пусть Φ — формула CNF над переменными X ₁ , ..., X _n , содержащая n предложений, и с по крайней мере k литералами в каждом предложении, и с каждой переменной X _{i ,} появляющейся не более чем в предложениях. Тогда Φ выполнима.${\displaystyle {\frac {2^{k}}{ke}}}$

Это утверждение можно легко доказать, используя симметричную версию алгоритмической локальной леммы Ловаса. Пусть X ₁ , ..., X _n — множество взаимно независимых случайных величин, которые выбираются равномерно случайным образом .${\displaystyle {\mathcal {P}}}$

Во-первых, мы усекаем каждое предложение в Φ, чтобы оно содержало ровно k литералов. Поскольку каждое предложение является дизъюнкцией, это не вредит выполнимости, поскольку если мы можем найти удовлетворяющее назначение для усеченной формулы, ее можно легко расширить до удовлетворяющего назначения для исходной формулы, повторно вставив усеченные литералы.

Теперь определим плохое событие A _j для каждого предложения в Φ, где A _j — это событие, при котором предложение j в Φ не удовлетворяется текущим назначением. Поскольку каждое предложение содержит k литералов (и, следовательно, k переменных) и поскольку все переменные выбираются равномерно случайным образом, мы можем ограничить вероятность каждого плохого события

${\displaystyle \Pr[A_{j}]=p=2^{-k}.}$

Поскольку каждая переменная может появляться не более чем в нескольких предложениях, а в каждом предложении имеется k переменных, каждое плохое событие A _j может зависеть не более чем от${\displaystyle {\frac {2^{k}}{ke}}}$

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

другие события. Поэтому:

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

умножив обе части на ep, получаем:

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

Из симметричной локальной леммы Ловаса следует, что вероятность случайного назначения X ₁ , ..., X _{n ,} удовлетворяющего всем условиям Φ, не равна нулю, и, следовательно, такое назначение должно существовать.

Теперь, Алгоритмическая Локальная Лемма Ловаса фактически позволяет нам эффективно вычислять такое назначение, применяя алгоритм, описанный выше. Алгоритм работает следующим образом:

Он начинается со случайного назначения истинностных значений переменным X ₁ , ..., X _{n ,} выбранным равномерно случайным образом. Пока существует предложение в Φ, которое не удовлетворено, он случайным образом выбирает неудовлетворенное предложение C в Φ и назначает новое истинностное значение всем переменным, которые появляются в C, выбранным равномерно случайным образом. Как только все предложения в Φ удовлетворены, алгоритм возвращает текущее назначение. Следовательно, алгоритмическая локальная лемма Ловаса доказывает, что этот алгоритм имеет ожидаемое время выполнения не более

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

шаги по формулам CNF, которые удовлетворяют двум условиям выше. Более сильная версия приведенного выше утверждения доказана Мозером, ^[3] см. также Берман, Карпински и Скотт. ^[4]

Алгоритм похож на WalkSAT , который используется для решения общих задач булевой выполнимости . Главное отличие заключается в том, что в WalkSAT после выбора неудовлетворенного предложения C случайным образом выбирается одна переменная в C , и ее значение инвертируется (что можно рассматривать как равномерный выбор только среди, а не среди всех назначений значений C ).${\displaystyle k}$${\displaystyle 2^{k}}$

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

• Вероятностные доказательства невероятностных теорем
• Случайный график

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

При условии, что функция назначения x удовлетворяет несколько более сильным условиям:

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

для некоторого ε > 0 Мозер и Тардос доказали, что параллельный алгоритм достигает лучшей сложности выполнения. В этом случае параллельная версия алгоритма занимает ожидаемое

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

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