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]

Niech będą zdarzeniami pewnej przestrzeni probabilistycznej, będą podzbiorami zbioru , a będą liczbami rzeczywistymi, dla . Jeżeli jest niezależne od oraz

,

to

Interpretacja grafowa[edytuj]

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 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 stanowią indeksy zdarzeń , . Strukturę taką nazywamy grafem zależności. Jest to o tyle wygodne, że jeżeli stopnie wierzchołków w tym grafie , 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 będzie grafem zależności dla zdarzeń . Jeżeli istnieją , , takie, że dla każdego

,

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

Wnioski[edytuj]

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

Wniosek

Niech G będzie grafem zależności dla zdarzeń takim, że:

  1. dla każdego ,
  2. dla każdego ,
  3. . (e jest tutaj podstawą logarytmu naturalnego)

Wtedy .

Wniosek ten otrzymuje się, podstawiając , gdzie

Zastosowania[edytuj]

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

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

Zobacz też[edytuj]