Lokalny lemat Lovásza

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Twierdzenie[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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.

Przypisy

  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, 609-627

Bibliografia[edytuj | edytuj kod]

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

Zobacz też[edytuj | edytuj kod]