Lovász místní lemma - Lovász local lemma
v teorie pravděpodobnosti, pokud je velký počet událostí nezávislý jeden druhého a každý má pravděpodobnost menší než 1, pak existuje pozitivní (možná malá) pravděpodobnost, že nedojde k žádné z událostí. The Lovász místní lemma umožňuje člověku mírně uvolnit podmínku nezávislosti: Pokud jsou události „většinou“ nezávislé na sobě navzájem a nejsou individuálně příliš pravděpodobné, bude stále existovat pozitivní pravděpodobnost, že k žádné z nich nedojde. Nejčastěji se používá v pravděpodobnostní metoda, zejména dát důkazy o existenci.
Existuje několik různých verzí lemmatu. Nejjednodušší a nejčastěji používanou je níže uvedená symetrická verze. Slabší verze byla prokázána v roce 1975 László Lovász a Paul Erdős v článku Problémy a výsledky na 3-chromatických hypergrafech a některé související otázky. U ostatních verzí viz (Alon & Spencer 2000 ). V roce 2020 Robin Moser a Gábor Tardos obdržel Gödelova cena pro jejich algoritmickou verzi Lovász Local Lemma.[1][2]
Výroky o lemmatu (symetrická verze)
Nechat A1, A2,..., Ak být sled událostí tak, že každá událost nastane s největší pravděpodobností p a takové, že každá událost je nezávislá na všech ostatních událostech s výjimkou maximálně d z nich.
Lemma já (Lovász a Erdős 1973; publikováno 1975) If
pak je nenulová pravděpodobnost, že nedojde k žádné z událostí.
Lemma II (Lovász 1977; vyd Joel Spencer[3]) Pokud
kde E = 2,718 ... je základem přirozených logaritmů, pak je nenulová pravděpodobnost, že nedojde k žádné z událostí.
Lemma II se dnes obvykle označuje jako „Lovászovo místní lemma“.
Lemma III (Shearer 1985[4]) Pokud
pak je nenulová pravděpodobnost, že nedojde k žádné z událostí.
Prahová hodnota v Lemmě III je optimální a znamená, že vázaná
je také dostačující.
Asymetrické Lovászovo místní lemma
Prohlášení o asymetrické verzi (která umožňuje události s různými hranicemi pravděpodobnosti) je následující:
Lemma (asymetrická verze). Nechat být konečnou množinou událostí v prostoru pravděpodobnosti Ω. Pro nechat označují sousedy v grafu závislosti (V grafu závislosti, událost nesousedí s událostmi, které jsou vzájemně nezávislé). Pokud existuje přiřazení skutečností na takové události
pak pravděpodobnost vyhnutí se všem událostem v je zejména pozitivní
Symetrická verze následuje bezprostředně z asymetrické verze nastavením
získat dostatečnou podmínku
od té doby
Konstruktivní versus nekonstruktivní
Všimněte si, že jak to u pravděpodobnostních argumentů často bývá, tato věta je nekonstruktivní a neposkytuje žádnou metodu určování explicitního prvku prostoru pravděpodobnosti, ve kterém nedojde k žádné události. Algoritmické verze místního lemmatu se silnějšími předpoklady jsou však také známy (Beck 1991; Czumaj a Scheideler 2000). Více nedávno, a konstruktivní verze místního lemmatu byl dán Robin Moser a Gábor Tardos nevyžadující žádné silnější předpoklady.
Nekonstruktivní důkaz
Dokazujeme asymetrickou verzi lemmatu, ze které lze odvodit symetrickou verzi. Pomocí princip matematické indukce dokazujeme to pro všechny v a všechny podskupiny z které nezahrnují , . Indukce se zde aplikuje na velikost (mohutnost) sady . Pro základní případ prohlášení zřejmě platí od té doby . Musíme ukázat, že nerovnost platí pro jakoukoli podmnožinu jisté mohutnost vzhledem k tomu, že platí pro všechny podskupiny s nižší mohutností.
Nechat . Máme od Bayesova věta
Spojili jsme čitatele a jmenovatele výše uvedeného výrazu samostatně. Za tímto účelem . Nejprve s využitím skutečnosti, že nezávisí na žádné události v .
Rozšířením jmenovatele pomocí Bayesovy věty a následným použitím induktivního předpokladu dostaneme
Lze zde použít indukční předpoklad, protože každá událost je podmíněna menším počtem dalších událostí, tj. Podmnožinou mohutnosti menší než . Z (1) a (2) dostaneme
Od hodnoty X je vždy v . Všimněte si, že jsme to v podstatě dokázali . Abychom získali požadovanou pravděpodobnost, napíšeme ji pomocí podmíněných pravděpodobností s opakovaným použitím Bayesovy věty. Proto,
což jsme chtěli dokázat.
Příklad
Předpokládejme, že 11n body jsou umístěny kolem kruhu a vybarveny n různé barvy tak, aby každá barva byla aplikována na přesně 11 bodů. V každém takovém zbarvení musí být sada n body obsahující jeden bod každé barvy, ale neobsahující žádnou dvojici sousedních bodů.
Chcete-li to vidět, představte si, že náhodně vyberete bod každé barvy, přičemž všechny body budou stejně pravděpodobné (tj. Budou mít pravděpodobnost 1/11). 11. denn různé události, kterým se chceme vyhnout, odpovídají 11n dvojice sousedních bodů v kruhu. Pro každý pár je naše šance na výběr obou bodů v tomto páru maximálně 1/121 (přesně 1/121, pokud mají dva body různé barvy, jinak 0), takže si vezmeme p = 1/121.
Zda daný pár (A, b) bodů je vybrán záleží pouze na tom, co se stane v barvách A a b, a už vůbec ne o tom, zda existuje nějaká jiná sbírka bodů ve druhé n - Jsou vybrány 2 barvy. To znamená událost "A a b jsou oba vybrány “je závislá pouze na těch párech sousedních bodů, které sdílejí barvu buď s A nebo s b.
V kruhu je 11 bodů, které sdílejí barvu A (počítaje v to A sám), z nichž každý má 2 páry. To znamená, že existuje 21 párů jiných než (A, b), které obsahují stejnou barvu jako A, a totéž platí pro b. Nejhorší, co se může stát, je to, že tyto dvě sady jsou disjunktní, takže můžeme vzít d = 42 v lematu. To dává
Podle místního lemmatu existuje pozitivní pravděpodobnost, že nedojde k žádné ze špatných událostí, což znamená, že naše množina neobsahuje žádný pár sousedních bodů. To znamená, že musí existovat sada splňující naše podmínky.
Poznámky
- ^ „Bývalý doktorand Robin Moser získává prestižní Gödelovu cenu“. ethz.ch. Citováno 2020-04-20.
- ^ „ACM SIGACT - Gödelova cena“. sigact.org. Citováno 2020-04-20.
- ^ Spencer, J. (1977). Msgstr "Asymptotické dolní meze pro Ramseyovy funkce". Diskrétní matematika. 20: 69–76. doi:10.1016 / 0012-365x (77) 90044-9.
- ^ Shearer, J (1985). „Na problém Spencera“. Combinatorica. 5 (3): 241–245. doi:10.1007 / BF02579368.
Reference
- Alon, Noga; Spencer, Joel H. (2000). Pravděpodobnostní metoda (2. vyd.). New York: Wiley-Interscience. ISBN 0-471-37046-0.CS1 maint: ref = harv (odkaz)
- Beck, J.. (1991). "Algoritmický přístup k lokálnímu lemmu Lovász, já". Náhodné struktury a algoritmy. 2 (4): 343–365. doi:10.1002 / rsa.3240020402.
- Czumaj, Artur; Scheideler, Christian (2000). "Zbarvení nejednotných hypergrafů: Nový algoritmický přístup k obecnému Lovászovu lokálnímu lematu". Náhodné struktury a algoritmy. 17 (3–4): 213–237. doi:10.1002 / 1098-2418 (200010/12) 17: 3/4 <213 :: AID-RSA3> 3.0.CO; 2-Y.
- Erdős, Paul; Lovász, László (1975). „Problémy a výsledky na 3-chromatických hypergrafech a některé související otázky“ (PDF). V A. Hajnal; R. Rado; V. T. Sós (eds.). Nekonečné a konečné sady (Paulovi Erdősovi k jeho 60. narozeninám). II. Severní Holandsko. 609–627.
- Moser, Robin A. (2008). "Konstruktivní důkaz o místní lememě Lovasz". arXiv:0810.4812 [cs.DS ].