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ászaP. 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..
Twierdzenie 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 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 W zastosowaniach najczęściej stosuje się poniższy wniosek.
Wniosek Niech będzie grafem zależności dla zdarzeń takim, że: dla każdego dla każdego ( jest tutaj podstawą logarytmu naturalnego).
Wtedy
Wniosek ten otrzymuje się, podstawiając gdzie
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 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
Przypisy
Bibliografia
Lovásza, lemat Lovásza, lemat