Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




18.04.2021


18.04.2021


18.04.2021


18.04.2021


18.04.2021





Яндекс.Метрика

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

12.10.2021

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

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

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

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

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

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

Pr ( A 1 ¯ ∧ ⋯ ∧ A n ¯ ) {displaystyle Pr left({overline {A_{1}}}wedge cdots wedge {overline {A_{n}}} ight)}

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

∏ A ∈ A ( 1 − x ( A ) ) {displaystyle prod _{Ain {mathcal {A}}}(1-x(A))} и поэтому, вероятно, будет очень мала.

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

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

История

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

| Γ ( A ) | < 2 n e . {displaystyle |Gamma (A)|<{frac {2^{n}}{e}}.}

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

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

Алгоритм

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

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

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

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

  • Для каждой величины P ∈ P {displaystyle Pin {mathcal {P}}} случайным образом вычислить некоторую его реализацию v P {displaystyle v_{P}}
  • Пока существует A ∈ A {displaystyle Ain {mathcal {A}}} такое, что ( v P ) P {displaystyle (v_{P})_{mathcal {P}}} удовлетворяет A {displaystyle A} :
    • Выбрать произвольное удовлетворенное событие A ∈ A {displaystyle Ain {mathcal {A}}}
    • Для каждой величины P ∈ vbl ( A ) {displaystyle Pin { ext{vbl}}(A)} вычислить новую реализацию v P {displaystyle v_{P}}
  • Вернуть ( v P ) P {displaystyle (v_{P})_{mathcal {P}}}
  • На первом этапе алгоритм случайным образом инициализирует текущее назначение v P {displaystyle v_{P}} для каждой случайной величины P ∈ P {displaystyle Pin {mathcal {P}}} . Это означает, что значение v P {displaystyle v_{P}} выбирается случайным образом и независимо в соответствии с распределением случайной величины P {displaystyle P} . Затем алгоритм входит в основной цикл, который выполняется до тех пор, пока не будет найдена нужная реализация. На каждой итерации основного цикла алгоритм выбирает произвольное удовлетворенное событие A {displaystyle {mathcal {A}}} и повторно выбирает все случайные величины, которые определяют A {displaystyle {mathcal {A}}} .

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

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

    ∀ A ∈ A : Pr ( A ) ≤ x ( A ) ∏ B ∈ Γ ( A ) ( 1 − x ( B ) ) {displaystyle forall Ain {mathcal {A}}:Pr(A)leq x(A)prod _{Bin Gamma (A)}(1-x(B))} ,

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

    x ( A ) 1 − x ( A ) {displaystyle {frac {x(A)}{1-x(A)}}}

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

    ∑ A ∈ A x ( A ) 1 − x ( A ) {displaystyle sum _{Ain {mathcal {A}}}{frac {x(A)}{1-x(A)}}} .

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

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

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

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

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

    Пример

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

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

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

    Pr ( A i ) = p = 2 − k . {displaystyle Pr(A_{i})=p=2^{-k}.}

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

    D = k ( 2 k k e − 1 ) ≤ 2 k e − 1 {displaystyle D=kleft({frac {2^{k}}{ke}}-1 ight)leq {frac {2^{k}}{e}}-1}

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

    D + 1 ≤ 2 k e . {displaystyle D+1leq {frac {2^{k}}{e}}.}

    Если умножить обе стороны на e p {displaystyle ep} , получится

    e p ( D + 1 ) ≤ e 2 − k 2 k e = 1 {displaystyle ep(D+1)leq e2^{-k}{frac {2^{k}}{e}}=1} .

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

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

    n 2 k e − k {displaystyle {frac {n}{{frac {2^{k}}{e}}-k}}}

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

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

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

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

    ∀ A ∈ A : Pr ( A ) ≤ ( 1 − ε ) x ( A ) ∏ B ∈ Γ ( A ) ( 1 − x ( B ) ) {displaystyle forall Ain {mathcal {A}}:Pr(A)leq (1-varepsilon )x(A)prod _{Bin Gamma (A)}(1-x(B))}

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

    O ( 1 ε log ⁡ ∑ A ∈ A x ( A ) 1 − x ( A ) ) {displaystyle Oleft({frac {1}{varepsilon }}log sum _{Ain {mathcal {A}}}{frac {x(A)}{1-x(A)}} ight)} .