Lovasovo místní lemma

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 19. června 2020; kontroly vyžadují 2 úpravy .

Místní Lovasovo lemma je lemma teorie pravděpodobnosti . Pokud je určitý počet událostí na sobě nezávislý a pravděpodobnost každé z nich je menší než 1, pak je pravděpodobnost, že nenastane žádná z událostí, kladná. Lovasovo lokální lemma umožňuje oslabení podmínky nezávislosti: pokud na sobě události nejsou „silně závislé“ a nejsou jednotlivě příliš pravděpodobné, pravděpodobnost, že nenastane žádná z nich, je pozitivní. Tento výsledek se nejčastěji používá v pravděpodobnostní metodě , zejména pro prokázání existence .

Existuje několik verzí lemmatu. Níže uvedená symetrická verze je nejjednodušší a nejčastěji používaná. Slabší verzi prokázali v roce 1975 Laszlo Lovas a Pal Erdős v článku "Problémy a výsledky 3-chromatických hypergrafů a některé související otázky [1] ". Viz ( Alon & Spencer 2000 ) pro další verze .

V roce 2020 obdrželi Robin Moser a Gabor Tardos Gödelovu cenu za algoritmickou verzi Lovasova lokálního lemmatu [2] [3] .

Symetrická verze lemmatu

Nechť A 1 , A 2 ,..., Ak je posloupnost událostí. Každá událost nastane s pravděpodobností nejvýše p a závisí na nejvýše d dalších událostech.

Lemma 1 (Lovas a Erdős 1973; publikováno 1975).

Nechte _ $4pd\leq 1$

Pak je pravděpodobnost, že nenastane žádná z událostí, kladná.

Lemma 2 (Lovas 1977; vydal Joel Spencer [4] ).

Nechat $ep(d+1)\leq 1,$

kde e = 2,718... je základ přirozených logaritmů.

Pak je pravděpodobnost, že nenastane žádná z událostí, kladná.

Právě Lemma 2 se obvykle nazývá „Lovas Local Lemma“.

Lemma 3 (Shearer, 1985 [5] ).

Nechat

${\begin{cases}p<{\frac {(d-1)^{d-1}}{d^{d}}},&d>1\\p<{\tfrac {1}{ 2}},&d=1\end{cases}}.$

Pak je pravděpodobnost, že nenastane žádná z událostí, kladná.

Podmínky stanovené lemmatem 3 jsou optimální, a tedy i podmínka

epd\leq 1

je také dost.

Asymetrická verze lemmatu

Formulace asymetrické verze, která bere v úvahu události s různými odhady pravděpodobnosti:

Lemma (asymetrická verze) [4] .

Nechť je konečná množina událostí v pravděpodobnostním prostoru Ω. Pro any , nechejte určit vrchol, který k němu sousedí v grafu závislosti (v grafu závislosti vrchol nesousedí s událostmi, které jsou na něm vzájemně nezávislé). Pokud existuje mapování takové, že ${\mathcal {A}}=\{A_{1},\ldots ,A_{n}}\}$ $A\in {\mathcal {A}}$ $\Gamma (A)$ $A$ $A$ $x:{\mathcal {A}}\to [0,1)$

\forall A\in {\mathcal {A}}:P(A)\leq x(A)\prod _{B\in \Gamma (A)}(1-x(B)),

pak pravděpodobnost, že nenastane žádná z událostí, je kladná a nerovnost ${\mathcal {A}}$

P\left({\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right)\geq \prod _{i\in \{1,\ cdot \cdot \cdot ,n\}}(1-x(A_{i})).

Symetrická verze bezprostředně navazuje na asymetrickou verzi. K tomu stačí dát

\forall A\in {\mathcal {A}}:x(A)={\frac {1}{d+1}}

Pak postačující podmínka

p\leq {\frac {1}{d+1}}\cdot {\frac {1}{e}}

protože

{\frac {1}{e}}\leq \left(1-{\frac {1}{d+1}}\right)^{d}.

Konstruktivní versus nekonstruktivní

Jako mnoho výroků o pravděpodobnostech je toto lemma nekonstruktivní a neobsahuje metodu pro explicitní definování pravděpodobnostního prostoru , ve kterém se žádná z událostí nevyskytuje. Jsou však známy algoritmické verze lokálního lemmatu se silnějšími podmínkami (Beck 1991; Czumaj a Scheideler 2000) [6] [7] . V roce 2009 Robin Moser a Gabor Tardos formulovali konstruktivní verzi místního lemmatu [8] [9] , která nevyžaduje silnější podmínky. Navrhli také distribuovanou verzi algoritmu. V roce 2016 Kai-Ming Chung, Seth Petty, Shin-Ha Su navrhli dva efektivnější distribuované algoritmy v článku "Distribuované algoritmy pro místní Lovasovo lemma a vybarvování grafů " [10] .

Nekonstruktivní důkaz

Dokažme asymetrickou verzi lemmatu, ze které lze získat symetrickou verzi.

Dokažme indukcí o mohutnosti , že pro všechny a pro všechny : platí nerovnost . $S$ $A\in$ $\mathcal{A}$ $S\subset {\mathcal {A}}$ $A\not \in {\mathcal {A}}$ $P\left(A\mid \bigwedge _{B\in S}{\overline {B))\right)\leq x(A)$

základ indukce. Neboť tvrzení je pravdivé, protože nerovnost je splněna podmínkou lemmatu. $S=\emptyset$ $P(A_{i})\leq x\left(A_{i}\right)$

krok indukce. Je třeba ukázat, že nerovnost platí pro všechny , pokud platí pro všechny : . $S\subset {\mathcal {A}}$ $S_{i}\subset {\mathcal {A}}$ $|S_{i}|<|S|$

Nechte _ Aplikujme Bayesovu větu a dostaneme ${\displaystyle S_{1}=S\cap \Gamma (A),S_{2}=S\setminus S_{1))$

P\left(A\mid \bigwedge _{B\in S}{\overline {B))\right)={\frac {P\left(A\bigwedge _{B\in S_{1} }{\overline {B}}\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right)}{P\left(\bigwedge _{B\in S_{1}} {\overline {B}}\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right))).

Čitatele a jmenovatele odhadujeme samostatně. Nechte _ Protože nezávisí na událostech z , $S_{1}=\{B_{j1},B_{j2},\ldots ,B_{jl}\}$ $A$ $S_{2}$

{\text{Numerator}}\leq P\left(A\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right)=P(A)\leq x( A)\prod _{B\in \Gamma (A)} (1-x(B)).\qquad (1)

Rozšiřujeme jmenovatele pomocí Bayesovy věty a poté použijeme indukční hypotézu. Můžeme použít induktivní předpoklad, protože každá událost závisí na podmnožině množiny a každá z těchto podmnožin má mohutnost menší než . Dostat ${\mathcal {A}}$ $|S|$

{\begin{aligned}&{\text{Denominator}}=P\left({\overline {B}}_{j1}\mid \bigwedge _{t=2}^{l}{\overline {B}}_{jt}\wedge \bigwedge _{B\in S_{2}}{\overline {B}}\right)\cdot P\left({\overline {B}}_{j2}\ střední \bigwedge _{t=3}^{l}{\overline {B}}_{jt}\wedge \bigwedge _{B\in S_{2}}{\overline {B}}\right)\cdot \ldots \cdot P\left({\overline {B}}_{jl}\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right)\geq \prod _{B \in S_{1}}(1-x(B)).\qquad (2)\end{aligned}}

Od a dostáváme $(jeden)$ $(2)$

P\left(A\mid \bigwedge _{B\in S}{\overline {B))\right)\leq x(A)\prod _{B\in \Gamma (A)-S_{ 1}}(1-x(B))\leq x(A)

protože hodnota vždy patří do . To jsme dokázali . $X$ $[0,1)$ $P\left({\overline {A}}\mid \bigwedge _{B\in S}{\overline {B}}\right)\geq 1-x(A)$

Zapišme si požadovanou pravděpodobnost opakovaným použitím definice podmíněné pravděpodobnosti . Dostat

{\begin{aligned}P\left({\overline {A_{1))}\wedge \ldots \wedge {\overline {A_{n))}\right)=P\left({\overline {A_{1}}}\mid {\overline {A_{2}}}\wedge \ldots \wedge {\overline {A_{n}}}\right)\cdot P\left({\overline {A_{ 2))\mid {\overline {A_{3))}\wedge \ldots \wedge {\overline {A_{n))}\right)\cdot \ldots \cdot P\left({\overline {A_ { n}}}\right)\geq \prod _{A\in {\mathcal {A}}}(1-x(A)),\end{aligned}}

Q.E.D.

Příklad

Předpokládejme, že 11 n bodů je umístěno na kruhu a jsou obarveny n různými barvami tak, že každá barva obarví přesně 11 bodů. Každé takové zbarvení musí mít sadu n bodů obsahujících jeden bod každé barvy, ale neobsahující pár sousedních bodů.

Abyste to viděli, představte si, že náhodně vyberete bod každé barvy. Všechny body jsou navíc vybírány stejně pravděpodobně, tedy s pravděpodobností 1/11. Existuje 11 n různých událostí, kterým se chceme vyhnout, odpovídají 11 n dvojicím sousedních bodů na kružnici. Pro každý pár je pravděpodobnost výběru 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 nastavíme p = 1/121 .

Zda bude zvolena konkrétní dvojice bodů (a, b) , závisí pouze na volbě bodů barvy a a barvy b a nezávisí na volbě jiné sady bodů v dalších n - 2 barvách. To znamená, že událost „ a a b jsou vybrány“ závisí pouze na těch párech sousedních bodů, které sdílejí barvu s a nebo b .

Na kruhu je 11 bodů, které sdílejí barvu s a (včetně samotného bodu a ), z nichž každý se skládá ze dvou párů. To znamená , že existuje 21 párů jiných než ( a , b ) , které obsahují stejnou barvu jako a , a totéž platí pro b . V nejhorším případě se tyto dvě množiny neprotínají, takže v podmínce lemmatu můžeme vzít d = 42. Dostaneme

ep(d+1)\cca 0,966<1.

Podle lokálního lemmatu existuje kladná pravděpodobnost, že k žádné z nežádoucích událostí nedojde, tedy že naše množina neobsahuje dvojici sousedních bodů. To znamená, že musí existovat množina splňující naše podmínky.

Poznámky

↑ Paul Erdős, Lászlo Lovász. Problémy a výsledky na 3-chromatických hypergrafech a některé související otázky // North-Holland Pub. spol. - 1975. Archivováno 4. března 2016.
↑ Bývalý doktorand Robin Moser přebírá prestižní Gödelovu cenu . ethz.ch. _ Získáno 20. dubna 2020. Archivováno z originálu dne 31. října 2021.
↑ ACM SIGACT - Gödelova cena . sigact.org . Staženo 20. dubna 2020. Archivováno z originálu 9. ledna 2020. (neurčitý)
↑ 1 2 Spencer, J. Asymptotické dolní odhady pro Ramseyovy funkce // Diskrétní matematika. - 1977. - T. 20 . - S. 69-76 . - doi : 10.1016/0012-365x(77)90044-9 .
↑ Shearer, J. O problému Spencera (neurčitý) // Combinatorica. - 1985. - V. 5 , č. 3 . - S. 241-245 . - doi : 10.1007/BF02579368 .
↑ Jozsef Beck. Algoritmický přístup k Lovászově lokálnímu lemmatu. I (anglicky) // Random Structures & Algorithms. - 1991. - Sv. 2 , iss. 4 . - str. 343-365 . — ISSN 1098-2418 . - doi : 10.1002/rsa.3240020402 . Archivováno z originálu 10. prosince 2019.
↑ Artur Czumaj, Christian Scheideler. Barvení neuniformních hypergrafů: Nový algoritmický přístup k obecnému Lovászovu lokálnímu lemmatu // Random Structures & Algorithms. - 2000. - Sv. 17 , iss. 3-4 . - str. 213-237 . — ISSN 1098-2418 . - doi : 10.1002/1098-2418(200010/12)17:3/43.0.CO;2-Y .
↑ Robin A. Moser, Gábor Tardos. Konstruktivní důkaz obecného lovászova místního lemmatu (anglicky) // Journal of the ACM. - 2009. Archivováno 14. června 2020.
↑ Robin A. Moser, Gábor Tardos. Konstruktivní důkaz obecného lovászova místního lemmatu (anglicky) // Journal of the ACM. - 2010. - únor Archivováno z originálu 8. března 2022.
↑ Kai-Min Chung, Seth Pettie & Hsin-Hao Su. Distribuované algoritmy pro Lovászovo lokální lemma a barvení grafů . Springer Link (21. listopadu 2016). Staženo 1. května 2020. Archivováno z originálu dne 3. června 2020. (neurčitý)

Odkazy

Alon, Noga; Spencer, Joel H.Pravděpodobnostní metoda (neopr.) . — 2. - New York: Wiley-Interscience , 2000. - ISBN 0-471-37046-0 .
Beck, JAlgoritmický přístup k Lovászově lokálnímu lemmatu, I (anglicky) // Random Structures and Algorithms : journal. - 1991. - Sv. 2 , ne. 4 . - str. 343-365 . - doi : 10.1002/rsa.3240020402 .
Czumaj, Artur; Scheideler, Christian. Barvení neuniformních hypergrafů: Nový algoritmický přístup k obecnému Lovászovu lokálnímu lemmatu // Random Structures & Algorithms: journal. - 2000. - Sv. 17 , č. 3-4 . - str. 213-237 . - doi : 10.1002/1098-2418(200010/12)17:3/4<213::AID-RSA3>3.0.CO;2-Y .
Moser, Robin A. (2008), konstruktivní důkaz Lovaszova místního lemmatu, arΧiv : 0810.4812 [cs.DS].