Lokalny lemat Lovásza

Lokalny lemat Lovásza – twierdzenie w rachunku prawdopodobieństwa podające warunek wystarczający istnienia w danej przestrzeni probabilistycznej zdarzenia elementarnego, które jest niezależne względem ustalonej, skończonej liczby innych zdarzeń. Twierdzenie to jest uogólnieniem trywialnego warunku mówiącego, iż takie zdarzenie istnieje, gdy prawdopodobieństwo każdego z pozostałych rozważanych zdarzeń jest mniejsze od 1 i zdarzenia te są niezależne.

Twierdzenie to zostało udowodnione w 1975 roku przez Paula Erdősa i László Lovásza^[1].

Niech ${\displaystyle A_{1},A_{2},\dots ,A_{n}}$ będą zdarzeniami pewnej przestrzeni probabilistycznej, ${\displaystyle J(1),J(2),\dots ,J(n),}$ będą podzbiorami zbioru ${\displaystyle \{1,2,\dots ,n\},}$ a ${\displaystyle \gamma _{1},\gamma _{2},\dots ,\gamma _{n}}$ będą liczbami rzeczywistymi, ${\displaystyle 0<\gamma _{i}<1}$ dla ${\displaystyle i=1,2,\dots ,n.}$ Jeżeli ${\displaystyle A_{i}}$ jest niezależne od ${\displaystyle \{A_{j}:j\notin J(i)\cup {i}\}}$ oraz

${\displaystyle \mathbb {P} (A_{i})\leqslant \gamma _{i}\prod _{j\in J(i)}(1-\gamma _{j}),}$

to

${\displaystyle \mathbb {P} (\bigcap _{j=1}^{n}{\bar {A_{j}}})\geqslant \prod _{j=1}^{n}(1-\gamma _{j}).}$

Twierdzenie w powyżej przedstawionej formie może wydawać się skomplikowane i nieefektywne. Dlatego też wygodnie jest skorzystać z następującej interpretacji grafowej. Niech ${\displaystyle G=(V,E)}$ będzie grafem, którego wierzchołki odpowiadać będą naszym zdarzeniom, natomiast krawędzie łączyć będą te wierzchołki, dla których zdarzenia im odpowiadające są zależne. Tzn. zbiór wierzchołków ${\displaystyle V=\{1,2,\dots ,n\}}$ stanowią indeksy zdarzeń ${\displaystyle A_{i},}$ ${\displaystyle E=\{(i,j):i\in J(j)\}.}$ Strukturę taką nazywamy grafem zależności. Jest to o tyle wygodne, że jeżeli stopnie wierzchołków w tym grafie ${\displaystyle \deg _{G}(i),}$ będą „wystarczająco małe”, to praktyczna staje się następująca wersja lokalnego lematu Lovásza:

Lemat Lovásza w języku grafów

Niech ${\displaystyle G=(V,E)}$ będzie grafem zależności dla zdarzeń ${\displaystyle A_{1},A_{2},\dots ,A_{n}.}$ Jeżeli istnieją ${\displaystyle \gamma _{1},\gamma _{2},\dots ,\gamma _{n},}$ ${\displaystyle 0<\gamma _{i}<1,}$ takie, że dla każdego ${\displaystyle i}$

${\displaystyle \mathbb {P} (A_{i})\leqslant \gamma _{i}\prod _{j:(i,j)\in E}(1-\gamma _{j}),}$

to prawdziwa jest następująca nierówność:

${\displaystyle \mathbb {P} (\bigcap _{j=1}^{n}{\bar {A_{j}}})\geqslant \prod _{j=1}^{n}(1-\gamma _{j}).}$

W zastosowaniach najczęściej stosuje się poniższy wniosek.

Wniosek

Niech ${\displaystyle G}$ będzie grafem zależności dla zdarzeń ${\displaystyle A_{1},A_{2},\dots ,A_{n}}$ takim, że:

1. ${\displaystyle \mathbb {P} (A_{i})\leqslant p}$ dla każdego ${\displaystyle i\in \{1\dots ,n\},}$
2. ${\displaystyle \deg _{G}(i)\leqslant d}$ dla każdego ${\displaystyle i\in \{1\dots ,n\},}$
3. ${\displaystyle e\cdot p\cdot (d+1)\leqslant 1.}$ (${\displaystyle e}$ jest tutaj podstawą logarytmu naturalnego).

Wtedy ${\displaystyle \mathbb {P} (\bigcap _{j=1}^{n}{\bar {A_{j}}})>0.}$

Wniosek ten otrzymuje się, podstawiając ${\displaystyle \gamma _{1}=\gamma _{2}=\ldots =\gamma _{n}={\frac {1}{d+1}},}$ gdzie ${\displaystyle d\geqslant 2.}$

Lokalny lemat Lovásza stosuje się, w probabilistycznych dowodach istnień pewnych struktur o zadanych własnościach. Definiuje się odpowiednią przestrzeń probabilistyczną, której elementami będą dane struktury i udowadnia, że z niezerowym prawdopodobieństwem można wybrać z niej element o żądanej własności. W tym celu określa się zdarzenia ${\displaystyle A_{i}}$ i np. stosując powyższe twierdzenia pokazuje, że nie pokrywają one całej przestrzeni.

• nierówność Chernoffa
• nierówność Czebyszewa
• nierówność Markowa

• Zbigniew Palka, Andrzej Ruciński: Niekonstruktywne metody matematyki dyskretnej. Wyd. I. Warszawa: WNT, 1996. ISBN 83-204-1930-1. Brak numerów stron w książce