Локальная лемма Ловаса - Lovász local lemma

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

Есть несколько разных версий леммы. Самым простым и наиболее часто используемым является симметричный вариант, представленный ниже. Более слабая версия была доказана в 1975 г. Ласло Ловас и Пол Эрдёш в статье Проблемы и результаты по 3-хроматическим гиперграфам и некоторые связанные вопросы. Для других версий см. (Алон и Спенсер 2000 ). В 2020 году Робин Мозер и Габор Тардос получил Премия Гёделя за их алгоритмическую версию локальной леммы Ловаса.^[1]^[2]

Утверждения леммы (симметричный вариант)

Позволять А₁, А₂,..., А_k быть последовательностью событий, так что каждое событие происходит с вероятностью не более п и так, что каждое событие не зависит от всех других событий, за исключением не более чем d их.

Лемма I. (Ловас и Эрдеш 1973; опубликовано в 1975 г.) Если
${ displaystyle 4pd leq 1}$
тогда существует ненулевая вероятность того, что ни одно из событий не произойдет.

Лемма II. (Ловас 1977; опубликовано Джоэл Спенсер^[3]) Если
${ displaystyle ep (d + 1) leq 1,}$
куда е = 2,718 ... основание натурального логарифма, тогда существует ненулевая вероятность того, что ни одно из событий не произойдет.

Лемму II сегодня обычно называют «локальной леммой Ловаса».

Лемма III. (Ширер 1985^[4]) Если
${ displaystyle { begin {case} p <{ frac {(d-1) ^ {d-1}} {d ^ {d}}} & d> 1 p <{ tfrac {1} {2 }} & d = 1 end {case}}}$
тогда существует ненулевая вероятность того, что ни одно из событий не произойдет.

Порог в лемме III оптимален, и отсюда следует, что оценка

{ displaystyle epd leq 1}

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

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

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

Лемма (асимметричный вариант). Позволять ${ 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}}: 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 _ {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). Совсем недавно конструктивная версия локальной леммы был дан Робин Мозер и Габор Тардос не требует более сильных предварительных условий.

Неконструктивное доказательство

Мы докажем асимметричный вариант леммы, из которого можно вывести симметричный вариант. Используя принцип математической индукции мы доказываем, что для всех ${ displaystyle A}$ в ${ displaystyle { mathcal {A}}}$ и все подмножества ${ displaystyle S}$ из ${ displaystyle { mathcal {A}}}$ которые не включают ${ displaystyle A}$ , ${ displaystyle Pr left (A mid bigwedge _ {B in S} { overline {B}} right) leq x (A)}$ . Индукция здесь применяется к размеру (мощности) множества ${ displaystyle S}$ . Для базового случая ${ Displaystyle S = emptyset}$ утверждение очевидно, поскольку ${ Displaystyle Pr (A_ {i}) leq x left (A_ {i} right)}$ . Нам нужно показать, что неравенство выполняется для любого подмножества ${ displaystyle { mathcal {A}}}$ определенного мощность при условии, что это верно для всех подмножеств меньшей мощности.

Позволять ${ Displaystyle S_ {1} = S cap Gamma (A), S_ {2} = S setminus S_ {1}}$ . У нас есть от Теорема Байеса

{ displaystyle Pr left (A mid bigwedge _ {B in S} { overline {B}} right) = { frac { Pr left (A bigwedge _ {B in S_ { 1}} { overline {B}} mid bigwedge _ {B in S_ {2}} { overline {B}} right)} { Pr 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 {Numerator}} leq Pr left (A mid bigwedge _ {B in S_ {2}} { overline {B}} right) = Pr (A) leq x (A) prod _ {B in Gamma (A)} (1-x (B)). qquad (1)}

Раскладывая знаменатель с помощью теоремы Байеса, а затем используя индуктивное предположение, получаем

{ displaystyle { begin {align} & { text {Denominator}} = {} & Pr left ({ overline {B}} _ {j1} mid bigwedge _ {t = 2} ^ {l} { overline {B}} _ {jt} wedge bigwedge _ {B in S_ {2}} { overline {B}} right) cdot Pr left ({ overline {B }} _ {j2} mid bigwedge _ {t = 3} ^ {l} { overline {B}} _ {jt} wedge bigwedge _ {B in S_ {2}} { overline {B }} right) cdots Pr 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 {align}}}

Здесь можно применить индуктивное предположение, поскольку каждое событие обусловлено меньшим числом других событий, то есть подмножеством мощности меньше, чем ${ displaystyle | S |}$ . Из (1) и (2) получаем

{ displaystyle Pr 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 [0,1)}$ . Отметим, что мы по существу доказали ${ displaystyle Pr left ({ overline {A}} mid bigwedge _ {B in S} { overline {B}} right) geq 1-x (A)}$ . Чтобы получить желаемую вероятность, мы запишем ее в терминах условных вероятностей, неоднократно применяя теорему Байеса. Следовательно,

{ displaystyle { begin {align} & Pr left ({ overline {A_ {1}}} wedge cdots wedge { overline {A_ {n}}} right) = {} & Pr left ({ overline {A_ {1}}} mid { overline {A_ {2}}} wedge cdots { overline {A_ {n}}} right) cdot Pr left ({ overline {A_ {2}}} mid { overline {A_ {3}}} wedge cdots { overline {A_ {n}}} right) cdots Pr left ({ overline {A_ {n}}} right) geq {} & prod _ {A in { mathcal {A}}} (1-x (A)), end {align}}}

что мы и хотели доказать.

Пример

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

Чтобы убедиться в этом, представьте, что вы случайным образом выбираете точку каждого цвета, причем все точки будут выбраны с одинаковой вероятностью (то есть с вероятностью 1/11). 11п различные события, которых мы хотим избежать, соответствуют 11п пары соседних точек на окружности. Для каждой пары наши шансы получить обе точки в этой паре не более 1/121 (точно 1/121, если две точки разного цвета, в противном случае 0), поэтому мы возьмем р = 1/121.

Была ли данная пара (а, б) точек выбирается зависит только от того, что происходит в цветах а и б, а вовсе не от того, есть ли какой-либо другой набор очков в другом п - Выбрано 2 цвета. Это подразумевает событие "а и б оба выбраны "зависит только от тех пар соседних точек, которые имеют общий цвет либо с а или с б.

На круге 11 точек общего цвета с а (включая а себя), в каждой из которых задействовано по 2 пары. Это означает, что есть 21 пара, кроме (а, б), которые имеют тот же цвет, что и а, и то же самое верно для б. Худшее, что может случиться, это то, что эти два множества не пересекаются, поэтому мы можем взять d = 42 в лемме. Это дает

{ displaystyle ep (d + 1) приблизительно 0,966 <1.}

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

Примечания

^ «Бывший докторант Робин Мозер получает престижную премию Гёделя». ethz.ch. Получено 2020-04-20.
^ "ACM SIGACT - премия Гёделя". sigact.org. Получено 2020-04-20.
^ Спенсер, Дж. (1977). «Асимптотические нижние оценки для функций Рамсея». Дискретная математика. 20: 69–76. Дои:10.1016 / 0012-365x (77) 90044-9.
^ Ширер, Дж (1985). «По проблеме Спенсера». Комбинаторика. 5 (3): 241–245. Дои:10.1007 / BF02579368.