Lovasz mahalliy lemma - Lovász local lemma

Yilda ehtimollik nazariyasi, agar ko'plab voqealar bo'lsa mustaqil har birining ehtimoli 1dan kam bo'lsa, unda hodisalarning hech biri yuz bermasligi uchun ijobiy (ehtimol kichik) ehtimollik mavjud. The Lovasz mahalliy lemma mustaqillik shartini biroz yumshatishga imkon beradi: Modomiki hodisalar bir-biridan "asosan" mustaqil bo'lib, alohida ehtimolga ega bo'lmasa, u holda ularning hech biri yuz bermaslik ehtimoli ijobiy bo'lib qoladi. Bu eng ko'p ishlatiladigan ehtimollik usuli, xususan berish mavjudlik dalillari.

Lemmaning bir necha xil versiyalari mavjud. Eng sodda va tez-tez ishlatib turadiganlar - quyida keltirilgan nosimmetrik versiya. Zaif versiyasi 1975 yilda isbotlangan Laslo Lovásh va Pol Erdos maqolada 3-xromatik gipergrafalar va shu bilan bog'liq ba'zi savollar bo'yicha muammolar va natijalar. Boshqa versiyalar uchun (ga qarang (Alon va Spenser 2000 ). 2020 yilda Robin Mozer va Gábor Tardos oldi Gödel mukofoti Lovász Local Lemma-ning algoritmik versiyasi uchun.^[1]^[2]

Lemma bayonotlari (nosimmetrik versiya)

Ruxsat bering A₁, A₂,..., A_k har bir hodisa maksimal ehtimollik bilan sodir bo'ladigan voqealar ketma-ketligi bo'lsin p va shundayki, har bir voqea eng ko'p tashqari barcha boshqa voqealardan mustaqildir d ulardan.

Lemma I (Lovásh va Erdős 1973; 1975 yilda nashr etilgan) Agar
${ displaystyle 4pd leq 1}$
unda hodisalarning hech biri sodir bo'lmasligi uchun nolga teng ehtimollik mavjud.

Lemma II (Lovász 1977; nashr etilgan Djoel Spenser^[3]) Agar
${ displaystyle ep (d + 1) leq 1,}$
qayerda e = 2.718 ... tabiiy logarifmlarning asosidir, keyin hodisalarning hech biri sodir bo'lmasligi uchun nolga teng bo'lmagan ehtimollik mavjud.

Lemma II bugungi kunda odatda "Lovázz local lemma" deb nomlanadi.

Lemma III (Shearer 1985)^[4]) Agar
${ displaystyle { begin {case} p <{ frac {(d-1) ^ {d-1}} {d ^ {d}}} & d> 1 p <{ tfrac {1} {2 }} & d = 1 end {holatlar}}}$
unda hodisalarning hech biri sodir bo'lmasligi uchun nolga teng ehtimollik mavjud.

Lemma III-dagi chegara maqbul va u bog'langanligini anglatadi

{ displaystyle epd leq 1}

ham etarli.

Asimmetrik Lovasz mahalliy lemmasi

Asimmetrik versiyaning bayonoti (har xil ehtimollik chegaralaridagi hodisalarga imkon beradigan) quyidagicha:

Lemma (assimetrik versiya). Ruxsat bering ${ displaystyle { mathcal {A}} = {A_ {1}, ldots, A_ {n} }}$ ehtimollik fazosidagi hodisalarning cheklangan to'plami bo'ling. Uchun ${ displaystyle A in { mathcal {A}}}$ ruxsat bering ${ displaystyle Gamma (A)}$ ning qo'shnilarini belgilang ${ displaystyle A}$ bog'liqlik grafigida (bog'liqlik grafasida, voqea ${ displaystyle A}$ o'zaro mustaqil bo'lgan voqealarga qo'shni emas). Agar u erda reals tayinlangan bo'lsa ${ displaystyle x: { mathcal {A}} dan [0,1)} gacha$ shunday voqealarga
${ displaystyle forall A in { mathcal {A}}: Pr (A) leq x (A) prod _ {B in Gamma (A)} (1-x (B))}$
unda barcha voqealardan qochish ehtimoli ${ displaystyle { mathcal {A}}}$ ijobiy, xususan
${ displaystyle Pr left ({ overline {A_ {1}}} wedge cdots wedge { overline {A_ {n}}} o'ng) geq prod _ {i in {1, cdot cdot cdot, n }} (1-x (A_ {i})).}$

Nosimmetrik versiya darhol assimetrik versiyadan o'rnatib o'rnatiladi

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

etarli shartni olish uchun

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

beri

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

Konstruktiv va konstruktiv bo'lmaganlarga nisbatan

E'tibor bering, ehtimol ehtimoliy dalillarda bo'lgani kabi, bu teorema ham mavjud konstruktiv bo'lmagan va hech qanday hodisa yuz bermaydigan ehtimollik makonining aniq elementini aniqlashning biron bir uslubini bermaydi. Shu bilan birga, mahalliy lemmaning old shartlari kuchliroq bo'lgan algoritmik versiyalari ham ma'lum (Bek 1991; Czumaj va Scheideler 2000). Yaqinda, a mahalliy lemmaning konstruktiv versiyasi tomonidan berilgan Robin Mozer va Gábor Tardos yanada kuchli old shartlarni talab qilmaydi.

Konstruktiv bo'lmagan dalil

Biz simmetrik versiyani olish mumkin bo'lgan lemmaning assimetrik versiyasini isbotlaymiz. Yordamida matematik induktsiya printsipi biz buni hamma uchun isbotlaymiz ${ displaystyle A}$ yilda ${ displaystyle { mathcal {A}}}$ va barcha kichik to'plamlar ${ displaystyle S}$ ning ${ displaystyle { mathcal {A}}}$ o'z ichiga olmaydi ${ displaystyle A}$ , ${ displaystyle Pr left (A mid bigwedge _ {B in S} { overline {B}} right) leq x (A)}$ . Bu erda induksiya to'plamning kattaligida (kardinalligi) qo'llaniladi ${ displaystyle S}$ . Asosiy ish uchun ${ displaystyle S = emptyset}$ bayonot aniq beri mavjud ${ displaystyle Pr (A_ {i}) leq x chap (A_ {i} o'ng)}$ . Biz har qanday kichik to'plam uchun tengsizlik mavjudligini ko'rsatishimiz kerak ${ displaystyle { mathcal {A}}}$ aniq kardinallik u pastki kardinallikning barcha kichik to'plamlari uchun mavjudligini hisobga olgan holda.

Ruxsat bering ${ displaystyle S_ {1} = S cap Gamma (A), S_ {2} = S setminus S_ {1}}$ . Bizda Bayes teoremasi

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

Yuqoridagi ifoda raqamini va maxrajini alohida bog'ladik. Buning uchun ruxsat bering ${ displaystyle S_ {1} = {B_ {j1}, B_ {j2}, ldots, B_ {jl} }}$ . Birinchidan, bu haqiqatdan foydalanish ${ displaystyle A}$ har qanday hodisaga bog'liq emas ${ displaystyle S_ {2}}$ .

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

Bayes teoremasidan foydalanib, induktiv faraz yordamida maxrajni kengaytiramiz

{ displaystyle { begin {aligned} & { text {Denominator}} = {} & Pr left ({ overline {B}} _ {j1} mid bigwedge _ {t = 2} ^ {l} { overline {B}} _ {jt} wedge bigwedge _ {B in S_ {2}} { overline {B}} right) cdot Pr left ({ overline {B }} _ {j2} mid bigwedge _ {t = 3} ^ {l} { overline {B}} _ {jt} wedge bigwedge _ {B in S_ {2}} { overline {B }} o'ng) cdots Pr chap ({ overline {B}} _ {jl} mid bigwedge _ {B in S_ {2}} { overline {B}} right) geq pro_ _ {B in S_ {1}} (1-x (B)) qquad (2) end {hizalangan}}}

Induktiv taxminni bu erda qo'llash mumkin, chunki har bir hodisa boshqa hodisalarning kamroq soniga, ya'ni kardinallikning pastki qismiga bog'liq ${ displaystyle | S |}$ . (1) va (2) dan olamiz

{ displaystyle Pr 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)}

Ning qiymati beri x har doim ichida ${ displaystyle [0,1)}$ . E'tibor bering, biz aslida isbotladik ${ displaystyle Pr left ({ overline {A}} mid bigwedge _ {B in S} { overline {B}} right) geq 1-x (A)}$ . Istalgan ehtimollikni olish uchun biz uni Bayes teoremasini takroran qo'llagan holda shartli ehtimolliklar nuqtai nazaridan yozamiz. Shuning uchun,

{ displaystyle { begin {aligned} & Pr left ({ overline {A_ {1}}} wedge cdots wedge { overline {A_ {n}}} right) = {} & Pr chap ({ overline {A_ {1}}} mid { overline {A_ {2}}} wedge cdots { overline {A_ {n}}} o'ng) cdot Pr chap ({ overline {A_ {2}}} mid { overline {A_ {3}}} wedge cdots { overline {A_ {n}}} o'ng) cdots Pr chap ({ overline {A_ {n}}} o'ng) geq {} & prod _ {A in { mathcal {A}}} (1-x (A)), end {hizalangan}}}

biz buni isbotlamoqchi edik.

Misol

11 deylikn nuqtalar aylana atrofida joylashtirilgan va bo'yalgan n har xil rang to'liq 11 punktga qo'llaniladigan tarzda turli xil ranglar. Bunday har qanday rangda to'plam bo'lishi kerak n har bir rangning bitta nuqtasini o'z ichiga olgan, lekin qo'shni nuqtalarning juftligini o'z ichiga olmagan nuqtalar.

Buni ko'rish uchun har bir rangning bir nuqtasini tasodifiy tanlashni tasavvur qiling, barcha nuqtalar teng darajada ehtimol (ya'ni, ehtimol, 1/11 ga teng) tanlanadi. 11n biz qochishni istagan turli hodisalar 11 ga to'g'ri keladin doira bo'yicha qo'shni nuqtalarning juftliklari. Har bir juftlik uchun bu juftlikdagi ikkala ochkoni olish imkoniyatimiz eng ko'pi bilan 1/121 (agar ikkala nuqta har xil rangda bo'lsa, aniq 1/121, aks holda 0), shuning uchun biz olamiz p = 1/121.

Berilgan juftlik (a, b) ochkolar faqat ranglarda sodir bo'ladigan narsalarga bog'liq a va bVa boshqasida boshqa biron bir ball to'plami bor-yo'qligi haqida emas n - 2 ta rang tanlangan. Bu voqeani nazarda tutadi "a va b ikkalasi ham tanlangan "faqat bitta rangni ulashgan qo'shni nuqtalarning juftlariga bog'liq a yoki bilan b.

Rangni baham ko'radigan doirada 11 nuqta mavjud a (shu jumladan a o'zi), ularning har biri 2 juftlik bilan bog'liq. Demak, (dan tashqari 21 juftlik mavjud)a, bbilan bir xil rangni o'z ichiga oladi a, va xuddi shu narsa uchun amal qiladi b. Vujudga kelishi mumkin bo'lgan eng yomoni shundaki, bu ikkita to'plam bir-biridan ajralib turadi, shuning uchun biz olishimiz mumkin d Lemmada = 42. Bu beradi

{ displaystyle ep (d + 1) taxminan 0.966 <1.}

Mahalliy lemma bo'yicha, yomon hodisalarning hech biri yuz bermasligi ehtimoli ijobiy, ya'ni bizning to'plamimizda qo'shni nuqtalarning juftligi yo'q. Bu bizning shartlarimizni qondiradigan to'plam mavjud bo'lishi kerakligini anglatadi.

Izohlar

^ "Sobiq doktorant Robin Mozer nufuzli Gödel mukofotiga sazovor bo'ldi". dilbar. Olingan 2020-04-20.
^ "ACM SIGACT - Gödel mukofoti". sigact.org. Olingan 2020-04-20.
^ Spenser, J. (1977). "Ramsey funktsiyalari uchun asimptotik pastki chegaralar". Diskret matematika. 20: 69–76. doi:10.1016 / 0012-365x (77) 90044-9.
^ Shearer, J (1985). "Spenser muammosi to'g'risida". Kombinatorika. 5 (3): 241–245. doi:10.1007 / BF02579368.

Adabiyotlar

Alon, Noga; Spenser, Joel H. (2000). Ehtimollik usuli (2-nashr). Nyu-York: Wiley-Interscience. ISBN 0-471-37046-0.CS1 maint: ref = harv (havola)
Bek, J. (1991). "Lovásh mahalliy lemmasiga algoritmik yondashuv, men". Tasodifiy tuzilmalar va algoritmlar. 2 (4): 343–365. doi:10.1002 / rsa.3240020402.
Tsumaj, Artur; Scheideler, Christian (2000). "Bir xil bo'lmagan gipergraflarni bo'yash: umumiy Lovash mahalliy lemmasiga yangi algoritmik yondashuv". Tasodifiy tuzilmalar va algoritmlar. 17 (3–4): 213–237. doi:10.1002 / 1098-2418 (200010/12) 17: 3/4 <213 :: AID-RSA3> 3.0.CO; 2-Y.
Erdos, Pol; Lovash, Laslo (1975). "3-xromatik gipergrafalar bo'yicha muammolar va natijalar va ularga tegishli ba'zi savollar" (PDF). A. Xajnalda; R. Rado; V. T. Sós (tahr.). Cheksiz va cheklangan to'plamlar (Pol Erdosga 60 yoshida). II. Shimoliy-Gollandiya. 609-627 betlar.
Moser, Robin A. (2008). "Lovasz mahalliy lemmasining konstruktiv isboti". arXiv:0810.4812 [cs.DS ].

[1] "Sobiq doktorant Robin Mozer nufuzli Gödel mukofotiga sazovor bo'ldi". dilbar. Olingan 2020-04-20.

[2] "ACM SIGACT - Gödel mukofoti". sigact.org. Olingan 2020-04-20.

[3] Spenser, J. (1977). "Ramsey funktsiyalari uchun asimptotik pastki chegaralar". Diskret matematika. 20: 69–76. doi:10.1016 / 0012-365x (77) 90044-9.

[4] Shearer, J (1985). "Spenser muammosi to'g'risida". Kombinatorika. 5 (3): 241–245. doi:10.1007 / BF02579368.

[1]

[2]

[3]

[4]