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.

Twierdzenie

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

$\mathbb{P}(A_i)⩽{\gamma }_i\prod _{j\in J(i)}(1-{\gamma }_j),$

to

$\mathbb{P}(\bigcap _{j=1}^n\overline{A_j})⩾\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,\dots ,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 ${\mathrm{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,\dots ,A_n.$ Jeżeli istnieją ${\gamma }_1,{\gamma }_2,\dots ,{\gamma }_n,$ $0<{\gamma }_i<1,$ takie, że dla każdego $i$

$\mathbb{P}(A_i)⩽{\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\overline{A_j})⩾\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,\dots ,A_n$ takim, że:

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

Wtedy $\mathbb{P}(\bigcap _{j=1}^n\overline{A_j})>0.$

Wniosek ten otrzymuje się, podstawiając ${\gamma }_1={\gamma }_2=\dots ={\gamma }_n=\frac{1}{d+1},$ gdzie $d⩾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.

Zobacz też

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

Bibliografia

• Szablon:Cytuj książkę