Lovászin paikallinen lemma

Lovasz paikallinen lemman (lyhennetään joskus LLL ) on seurausta todennäköisyysteoriaa erillisten vuoksi László Lovász ja Paul Erdős . Se yleistää tosiasian, että itsenäisten tapahtumien todennäköisyys samanaikaisesti on yhtä suuri kuin näiden tapahtumien todennäköisyyksien tulo. Tuloksesta on useita versioita. Paikallinen lemma käytetään useilla aloilla, erityisesti combinatorics ja teoreettisen tietojenkäsittelyopin . Näillä alueilla sanotaan toisinaan epävirallisesti seuraavasti: Kun otetaan huomioon joukko huonoja tapahtumia, joilla ei ole suurta riippuvuutta toisistaan, on mahdollista välttää kaikki nämä tapahtumat samanaikaisesti.

Johdanto

Paikallinen lemma voidaan nähdä todennäköisyysmenetelmän versiona . Tämän yhdistelmätekniikan avulla voidaan osoittaa, että tietyt objektit ovat olemassa osoittamalla, että tiettyjen satunnaisrakenteiden mukaan todennäköisyys sellaisen objektin luomiseksi ei ole nolla.

Esimerkiksi kun otetaan huomioon itsenäisten tapahtumien perhe, jonka todennäköisyydet ovat tiukasti alle 1, todennäköisyys siitä, ettei yksikään niistä ilmesty, ei ole nolla. Paikallinen lemma voi mahdollistaa saman tuloksen saamisen, jos jokainen tapahtuma on riippuvainen vain rajoitetusta määrästä muita tapahtumia.

Määritelmät

Seuraavassa merkitsemme tapahtumia mielivaltaisessa todennäköisyysavaruudessa. $(E_ {i}) _ {i}$

Näiden tapahtumien väliset riippuvuudet voidaan esittää suuntaamattomalla kuvaajalla G = (V, E) , jota kutsutaan riippuvuusgraafiksi , jonka määrittelee:

kukin solmu edustaa tapahtumaa,
reuna (u, v) kuuluu kuvaajan, jos ja vain jos tapahtumat ja ovat riippuvaisia. $E_ {u}$ $E_ {vb}$

Lausunnot

Annamme ensin yleisen lausuman, sitten symmetrisen muodon, joka on seuraus, helpommin käytettävissä.

Yleinen tapaus

Jos on olemassa reaalilukujen [0,1] perhe , joka kaikille i : $(x_ {i}) _ {i}$

Pr [E_ {i}] \ leq x_ {i} \ Pi _ {{(i, j) \ kohteessa E}} (1-x_ {j})

Joten:

Pr [\ cap _ {{i = 1}} ^ {n} {\ bar {E_ {i}}}] \ geq \ Pi _ {{i = 1}} ^ {n} (1-x_ {i} )

Symmetrinen tapaus

Jos kaikilla i , jos jokainen tapahtuma riippuu vain korkeintaan sekä muita tapahtumia, eli jos riippuvuus kuvaaja on astetta ylöspäin ja , ja jos , missä E on pohja luonnollinen logaritmi , niin . $Pr [E_ {i}] \ leq s$ $ep (d + 1) \ leq 1$ $Pr [\ cap _ {{i = 1}} ^ {n} {\ bar {E_ {i}}}]> 0$

Sovellukset

Käyttöalueet

Paikallista lemmaa on käytetty monilla combinatorics-aloilla, mukaan lukien ääripääte-teoria , Ramsey-teoria ja satunnaiskaavioiden teoria , ja teoreettisessa tietojenkäsittelytieteessä, erityisesti SAT-ongelman erikoistapauksessa , algoritmien reitittämisessä ja väritysongelmissa .

Esimerkki k-SAT-ongelmasta

SAT ongelma muodostuu,, koska looginen kaava konjunktiivisessa normaalissa muodossa , tietää, jos on tehtävä muuttujien siten, että kaava on totta, eli päättää satisfiability, jolla on kaava. Teemme kaksi oletusta: lauseketta kohti on enintään k literaalia (tämä on k -SAT- ongelma ), ja jokainen kirjaimellinen esiintyy vain enintään lauseissa. Sitten lemman avulla voidaan sanoa, että kaava on tyydyttävä. Itse asiassa, jos muuttujien arvot otetaan satunnaisesti, niin tapahtumat "lauseluku i on tyytyväinen" tyydyttävät symmetrisen lemman oletukset ja . ${\ displaystyle 2 ^ {k / 50}}$ ${\ displaystyle p = 2 ^ {- k}}$ ${\ displaystyle d = k2 ^ {k / 50}}$

Historiallinen

Paikallinen lemma julkaistiin artikkelissa Erdős ja Lovász 1975 vahvemmalla hypoteesilla . Sitä parannettiin saadaksesi tässä annetut rajat. Ensimmäiset todisteet lemmasta eivät olleet rakentavia, mutta Moser ja Tardos löysivät rakentavan todistuksen noin vuoden 2010 jälkeen. Tällä viimeisellä todisteella on myös algoritmisia seurauksia, puhutaan lisäksi algoritmisesta Lovászin paikallisesta lemmasta ( fr ) . Käytettyä menetelmää kutsutaan entropiakompressioksi (en) . $4dp \ leq 1$

Huomautuksia ja viitteitä

Nämä lausuman muodot ovat peräisin Motwani ja Raghavan 1995: stä ; muita muotoja on olemassa.
Yksi ensimmäisistä artikkeleista, joissa käytetään lemmaa, antaa alarajan Ramsey-numeroille: Joel Spencer (sisään) , " Asymptoottiset alemmat rajat Ramsey-funktioille ", Discrete Mathematics , voi. 20,1977, s. 69-76
Tämä sovellusten luettelo on peräisin Motwani ja Raghavan 1995 .
Katso esimerkki Regamey 2012 : n osasta 5.
Alkuperäinen artikkeli on: Frank Thomson Leighton, Bruce M. Maggs ja Satish Rao, ” Pakettien reititys ja työpajakauppojen aikataulutus O: n (ruuhkan + laajenemisen) vaiheissa ”, Combinatorica , voi. 14, n ° 21994, s. 167-186.
Esimerkiksi artikkeli: Daniel Marx ja Marcus Schaefer, " Moninkertaisuuden värjäytymisen monimutkaisuus ", Diskreetti sovellettu matematiikka , voi. 157, n o 1,2009, s. 13-18.
Motwani ja Raghavan 1995
Robin A. Moser ja Gabor Tardos, " Rakentava todiste yleisestä lovászin paikallisesta lemmasta ", Journal of the ACM , voi. 57, n ° 2 2010
Viesti tästä todisteesta: (in) Terence Tao , " Moserin entropian pakkausargumentti " osoitteessa terrytao.wordpress.com ,5. elokuuta 2009(käytetty 24. kesäkuuta 2014 ) .

Bibliografia

(en) Paul Erdős ja László Lovász , "Ongelmia ja tuloksia 3-kromaattisissa hypergraafeissa ja joissakin niihin liittyvissä kysymyksissä" , Infinite and Finite Sets (Paul Erdősille hänen 60-vuotispäivänään) , voi. II,1975( lue verkossa ) , s. 609–627

(en) Rajeev Motwani ja Prabhakar Raghavan , satunnaistetut algoritmit , Cambridge; New York, Cambridge University Press ( repr. 1997, 2000) ( 1 kpl toim. 1995), 476 s. ( ISBN 9780521474658 ) , luku . 5.5 (“The Lovász local lemma”) , s. 115-120

Samuel Regamey , todennäköisyysmenetelmä ja Lovászin paikallinen lemma (projektiraportti), EPFL ,tammikuu 2012( lue verkossa )