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

21.02.2021

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

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

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

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

Пусть A1, A2,..., Ak – последовательность событий. Каждое событие происходит с вероятностью не более p и зависит не более чем от d других событий.

Лемма 1 (Ловас, Эрдёш 1973; опубликовано в 1975).

Пусть 4 p d ≤ 1 {displaystyle 4pdleq 1} .

Тогда вероятность того, что ни одно из событий не произойдет, положительна.

Лемма 2 (Ловас 1977; опубликовано Джоэлом Спенсером).

Пусть e p ( d + 1 ) ≤ 1 , {displaystyle ep(d+1)leq 1,}

где e = 2.718... является основанием натуральных логарифмов.

Тогда вероятность того, что ни одно из событий не произойдет, положительна.

Именно лемму 2 обычно называют «Локальной леммой Ловаса».

Лемма 3 (Ширер, 1985).

Пусть

{ p < ( d − 1 ) d − 1 d d , d > 1 p < 1 2 , d = 1 . {displaystyle {egin{cases}p<{frac {(d-1)^{d-1}}{d^{d}}},&d>1p<{ frac {1}{2}},&d=1end{cases}}.}

Тогда вероятность того, что ни одно из событий не произойдет, положительна.

Условия, накладываемые леммой 3 оптимальны, а значит условие

e p d ≤ 1 {displaystyle epdleq 1}

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

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

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

Лемма (асимметричная версия).

Пусть A = { A 1 , … , A n } {displaystyle {mathcal {A}}={A_{1},ldots ,A_{n}}} – конечное множество событий в вероятностном пространстве Ω. Для любого A ∈ A {displaystyle Ain {mathcal {A}}} пусть Γ ( A ) {displaystyle Gamma (A)} определяет смежные с A {displaystyle A} вершины в графе зависимостей (в графе зависимостей вершина A {displaystyle A} не смежна с событиями, которые с ней взаимно независимы). Если существует отображение x : A → [ 0 , 1 ) {displaystyle x:{mathcal {A}} o [0,1)} такое, что

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

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

P ( A 1 ¯ ∧ ⋯ ∧ A n ¯ ) ≥ ∏ i ∈ { 1 , ⋅ ⋅ ⋅ , n } ( 1 − x ( A i ) ) . {displaystyle Pleft({overline {A_{1}}}wedge cdots wedge {overline {A_{n}}} ight)geq prod _{iin {1,cdot cdot cdot ,n}}(1-x(A_{i})).}

Симметричная версия немедленно вытекает из асимметричной версии. Для этого достаточно положить

∀ A ∈ A : x ( A ) = 1 d + 1 {displaystyle forall Ain {mathcal {A}}:x(A)={frac {1}{d+1}}} .

Тогда выполняется достаточное условие

p ≤ 1 d + 1 ⋅ 1 e {displaystyle pleq {frac {1}{d+1}}cdot {frac {1}{e}}} ,

поскольку

1 e ≤ ( 1 − 1 d + 1 ) d . {displaystyle {frac {1}{e}}leq left(1-{frac {1}{d+1}} ight)^{d}.}

Конструктивное против неконструктивного

Как и многие утверждения о вероятностях, эта лемма неконструктивна и не содержит метода явного определения вероятностного пространства, в котором ни одно из событий не происходит. Однако известны алгоритмические версии локальной леммы с более сильными условиями (Beck 1991; Czumaj and Scheideler 2000). В 2009 году Робин Мозер и Габор Тардос сформулировали конструктивную версию локальной леммы, не требующую более сильных условий. Они также предложили распределённую версию алгоритма. В 2016 году Кай-Мин Чунг, Сет Петти, Шин-Ха Су предложили ещё два более эффективных распределённых алгоритма в статье "Распределённые алгоритмы для локальной леммы Ловаса и раскраска графов".

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

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

Индукцией по мощности S {displaystyle S} докажем, что для всех A ∈ {displaystyle Ain } A {displaystyle {mathcal {A}}} и для всех S ⊂ A {displaystyle Ssubset {mathcal {A}}} : A ∉ A {displaystyle A ot in {mathcal {A}}} выполняется неравенство P ( A ∣ ⋀ B ∈ S B ¯ ) ≤ x ( A ) {displaystyle Pleft(Amid igwedge _{Bin S}{overline {B}} ight)leq x(A)} .

База индукции. Для S = ∅ {displaystyle S=emptyset } утверждение верно, так как неравенство P ( A i ) ≤ x ( A i ) {displaystyle P(A_{i})leq xleft(A_{i} ight)} выполняется по условию леммы.

Шаг индукции. Необходимо показать, что неравенство выполняется для любого S ⊂ A {displaystyle Ssubset {mathcal {A}}} , если оно выполняется для всех S i ⊂ A {displaystyle S_{i}subset {mathcal {A}}} : | S i | < | S | {displaystyle |S_{i}|<|S|} .

Положим S 1 = S ∩ Γ ( A ) , S 2 = S ∖ S 1 {displaystyle S_{1}=Scap Gamma (A),S_{2}=Ssetminus S_{1}} . Применим теорему Байеса и получим

P ( A ∣ ⋀ B ∈ S B ¯ ) = P ( A ⋀ B ∈ S 1 B ¯ ∣ ⋀ B ∈ S 2 B ¯ ) P ( ⋀ B ∈ S 1 B ¯ ∣ ⋀ B ∈ S 2 B ¯ ) . {displaystyle Pleft(Amid igwedge _{Bin S}{overline {B}} ight)={frac {Pleft(Aigwedge _{Bin S_{1}}{overline {B}}mid igwedge _{Bin S_{2}}{overline {B}} ight)}{Pleft(igwedge _{Bin S_{1}}{overline {B}}mid igwedge _{Bin S_{2}}{overline {B}} ight)}}.}

Оценим отдельно числитель и знаменатель. Пусть S 1 = { B j 1 , B j 2 , … , B j l } {displaystyle S_{1}={B_{j1},B_{j2},ldots ,B_{jl}}} . Так как A {displaystyle A} не зависит от событий из S 2 {displaystyle S_{2}} ,

Числитель ≤ P ( A ∣ ⋀ B ∈ S 2 B ¯ ) = P ( A ) ≤ x ( A ) ∏ B ∈ Γ ( A ) ( 1 − x ( B ) ) . ( 1 ) {displaystyle { ext{Числитель}}leq Pleft(Amid igwedge _{Bin S_{2}}{overline {B}} ight)=P(A)leq x(A)prod _{Bin Gamma (A)}(1-x(B)).qquad (1)}

Разложим знаменатель с помощью теоремы Байеса, а затем воспользуемся предположением индукции. Мы можем применить предположение индукции, поскольку каждое событие зависит от подмножества множества A {displaystyle {mathcal {A}}} и каждое из этих подмножеств имеет мощность меньшую, чем | S | {displaystyle |S|} . Получим

Знаменатель = P ( B ¯ j 1 ∣ ⋀ t = 2 l B ¯ j t ∧ ⋀ B ∈ S 2 B ¯ ) ⋅ P ( B ¯ j 2 ∣ ⋀ t = 3 l B ¯ j t ∧ ⋀ B ∈ S 2 B ¯ ) ⋅ … ⋅ P ( B ¯ j l ∣ ⋀ B ∈ S 2 B ¯ ) ≥ ∏ B ∈ S 1 ( 1 − x ( B ) ) . ( 2 ) {displaystyle {egin{aligned}&{ ext{Знаменатель}}=Pleft({overline {B}}_{j1}mid igwedge _{t=2}^{l}{overline {B}}_{jt}wedge igwedge _{Bin S_{2}}{overline {B}} ight)cdot Pleft({overline {B}}_{j2}mid igwedge _{t=3}^{l}{overline {B}}_{jt}wedge igwedge _{Bin S_{2}}{overline {B}} ight)cdot ldots cdot Pleft({overline {B}}_{jl}mid igwedge _{Bin S_{2}}{overline {B}} ight)geq prod _{Bin S_{1}}(1-x(B)).qquad (2)end{aligned}}}

Из ( 1 ) {displaystyle (1)} и ( 2 ) {displaystyle (2)} получим

P ( A ∣ ⋀ B ∈ S B ¯ ) ≤ x ( A ) ∏ B ∈ Γ ( A ) − S 1 ( 1 − x ( B ) ) ≤ x ( A ) {displaystyle Pleft(Amid igwedge _{Bin S}{overline {B}} ight)leq x(A)prod _{Bin Gamma (A)-S_{1}}(1-x(B))leq x(A)} ,

так как значение x {displaystyle x} всегда принадлежит [ 0 , 1 ) {displaystyle [0,1)} . Мы доказали, что P ( A ¯ ∣ ⋀ B ∈ S B ¯ ) ≥ 1 − x ( A ) {displaystyle Pleft({overline {A}}mid igwedge _{Bin S}{overline {B}} ight)geq 1-x(A)} .

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

P ( A 1 ¯ ∧ … ∧ A n ¯ ) = P ( A 1 ¯ ∣ A 2 ¯ ∧ … ∧ A n ¯ ) ⋅ P ( A 2 ¯ ∣ A 3 ¯ ∧ … ∧ A n ¯ ) ⋅ … ⋅ P ( A n ¯ ) ≥ ∏ A ∈ A ( 1 − x ( A ) ) , {displaystyle {egin{aligned}Pleft({overline {A_{1}}}wedge ldots wedge {overline {A_{n}}} ight)=Pleft({overline {A_{1}}}mid {overline {A_{2}}}wedge ldots wedge {overline {A_{n}}} ight)cdot Pleft({overline {A_{2}}}mid {overline {A_{3}}}wedge ldots wedge {overline {A_{n}}} ight)cdot ldots cdot Pleft({overline {A_{n}}} ight)geq prod _{Ain {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 в условии леммы. Получаем

e p ( d + 1 ) ≈ 0.966 < 1. {displaystyle ep(d+1)approx 0.966<1.}

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


Имя:*
E-Mail:
Комментарий: