Lokalny lemat Lovásza

Lokalny lemat Lovásza – twierdzenie w rachunku prawdopobień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.

Twierdzenie

Niech $A_1,A_2,\ldots,A_n$ będą zdarzeniami pewnej przestrzeni probabilistycznej, $J(1),J(2),\ldots,J(n),$ będą podzbiorami zbioru $\{1,2,\ldots,n\}$, a $\gamma_1,\gamma_2,\ldots,\gamma_n$ będą liczbami rzeczywistymi, $0<\gamma_i<1\$ dla $i=1,2,\ldots,n$. Jeżeli $A_i\$ jest niezależne od $\{A_j:j\notin J(i)\cup{i}\}$ oraz

$\mathbb{P}(A_i)\leqslant\gamma_i\prod_{j\in J(i)}(1-\gamma_j)$,

to

$\mathbb{P}(\bigcap_{j=1}^n \bar{A_j})\geqslant\prod_{j=1}^n(1-\gamma_j)$

Interpretacja grafowa

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 $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 $V=\{1,2,\ldots,n\}$ stanowią indeksy zdarzeń $A_i\$, $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 $\operatorname{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 $G=(V,E)\$ będzie grafem zależności dla zdarzeń $A_1,A_2,\ldots,A_n$. Jeżeli istnieją $\gamma_1,\gamma_2,\ldots,\gamma_n$, $0< \gamma_i < 1\$, takie, że dla każdego $i\$

$\mathbb{P}(A_i)\leqslant\gamma_i\prod_{j:(i,j)\in E}(1-\gamma_j)$,

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

$\mathbb{P}(\bigcap_{j=1}^n \bar{A_j})\geqslant\prod_{j=1}^n(1-\gamma_j)$

Wnioski

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

Wniosek

Niech G będzie grafem zależności dla zdarzeń $A_1,A_2,\ldots,A_n\$ takim, że:

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

Wtedy $\mathbb{P}(\bigcap_{j=1}^n \bar{A_j})>0\$.

Wniosek ten otrzymuje się, podstawiając $\gamma_1=\gamma_2=\ldots=\gamma_n=\frac{1}{d+1}$, gdzie $d\geqslant 2\$

Zastosowania

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 $A_i\;$ i np. stosując powyższe twierdzenia pokazuje, że nie pokrywają one całej przestrzeni.

Bibliografia

• Zbigniew Palka, Andrzej Ruciński: Niekonstruktywne metody matematyki dyskretnej. Wyd. I. Warszawa: WNT, 1996. ISBN 83-204-1930-1. 

Zobacz też

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