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].

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})\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,\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 $\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})\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},\dots ,A_{n}$ takim, że:

$\mathbb {P} (A_{i})\leqslant p$ dla każdego $i\in \{1\dots ,n\},$
$\deg _{G}(i)\leqslant d$ dla każdego $i\in \{1\dots ,n\},$
$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.

Zobacz też

Przypisy

↑ P. Erdős, L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, Colloq. Math. Soc. János Bolyai, Vol. 10, s. 609–627.

Bibliografia

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

[1] P. Erdős, L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, Colloq. Math. Soc. János Bolyai, Vol. 10, s. 609–627.

[1]