Metoda probabilității condiționate

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 19 iunie 2017; verificarea necesită 1 editare .

În matematică , pentru a demonstra existența unor obiecte matematice cu unele proprietăți combinatorii, se folosește metoda probabilistică , în care se arată că un obiect aleatoriu selectat dintr-un eșantion probabilistic are proprietatea cerută cu o probabilitate pozitivă. Prin urmare, aceste dovezi de existență sunt non -constructive - nu descriu în mod explicit o metodă pentru construirea sau calcularea unor astfel de obiecte.

Metoda probabilităților condiționate [1] [2] [3] transformă o astfel de demonstrație într-un „sens destul de precis” într-un algoritm determinist eficient care garantează descoperirea unui obiect cu proprietățile dorite. Adică metoda derandomizează demonstrația. Ideea de bază este de a înlocui fiecare alegere aleatorie într-un experiment aleatoriu cu o alegere deterministă, astfel încât să se păstreze așteptarea condiționată a eșecului din cauza alegerii mai mică de 1.

Metoda este parțial relevantă în contextul rotunjirii probabilistice (care folosește o metodă probabilistică pentru a dezvolta algoritmi de aproximare ).

Când se aplică metoda probabilităților condiționate, termenul tehnic estimator pesimist se referă la valorile utilizate în locul probabilității condiționate (sau mediei condiționate) a dovezii originale.

Prezentare generală

Raghavan [3] oferă următoarea descriere a metodei:

Mai întâi arătăm existența unei soluții aproximative dovedit bune folosind o metodă probabilistică ... [Apoi] arătăm că demonstrația existenței probabilistice poate fi convertită, într-un sens foarte precis, într-un algoritm de aproximare deterministă.

(Raghavan discută metoda în contextul rotunjirii probabilistice , dar metoda funcționează cu metoda probabilistică generală.)

Pentru a aplica metoda unei demonstrații probabilistice, un obiect ales aleatoriu în demonstrația originală trebuie să fie selectabil prin experimente aleatorii constând dintr-o secvență de alegeri aleatoare „mici”.

Există un exemplu banal pentru a ilustra principiul.

Lema: Este posibil să dezvăluiți (ascunse) trei monede, astfel încât numărul de cozi să fie de cel puțin 2. Dovada probabilității. Dacă trei monede sunt aruncate aleatoriu, numărul așteptat de cozi este de 1,5. Astfel, trebuie să existe o soluție (o modalitate de a deschide monedele), astfel încât numărul de lingouri să fie de cel puțin 1,5. Deoarece numărul de cozi este un întreg , există cel puțin 2 cozi în această soluție. QED

În acest exemplu, un experiment aleatoriu constă în aruncarea a trei monede simetrice. Experimentul este ilustrat cu un copac din figură. Există opt rezultate, fiecare corespunzând unei frunze din copac. Testul din experimentul aleatoriu corespunde alegerii unei tranziții aleatorii de la rădăcină (nodul superior al arborelui unde nu sunt expuse monede) la frunză. Deciziile reușite sunt cele în care cel puțin două monede ies coada. Nodurile interne ale arborelui corespund soluțiilor parțial definite în care monede 0, 1, 2 și așa mai departe sunt deschise.

Pentru a aplica metoda probabilităților condiționate, accentul este pus pe probabilitatea condiționată de eșec, dată de alegerea succesivă făcută pe măsură ce experimentul trece de la pas la pas. În diagramă, fiecare nod este etichetat cu această probabilitate condiționată. (De exemplu, dacă este dezvăluită doar prima monedă, iar rezultatul experimentului este cozi, aceasta corespunde celui de-al doilea copil al rădăcinii. Pentru această stare intermediară, probabilitatea de eșec este de 0,25.)

Metoda probabilității condiționate înlocuiește trecerea aleatorie de la rădăcină la frunză într-un experiment aleator cu o trecere deterministă în care fiecare pas este ales pentru a controla următoarea condiție de invarianță:

așteptarea condiționată de eșec, determinată de starea curentă, este mai mică de 1.

Acest lucru asigură atingerea frunzei marcate cu 0, adică o soluție de succes.

Condiția de invarianță este inițial (la rădăcină) satisfăcută deoarece demonstrația inițială arată că probabilitatea (necondiționată) de eșec este mai mică decât 1. Probabilitatea condiționată la orice nod intern este media aritmetică a probabilităților condiționate ale moștenitorilor nodului. Această proprietate este importantă deoarece implică faptul că orice nod intern cu o probabilitate condiționată mai mică de 1 are cel puțin un succesor a cărui probabilitate condiționată este mai mică de 1. Astfel, la orice nod intern, se poate alege întotdeauna un succesor astfel încât atunci când trece la el. a menținut condiția de invarianță. Întrucât condiția de invarianță se menține până la sfârșit, când experimentul ajunge la frunză și toate alegerile sunt determinate, soluția astfel obținută trebuie să aibă succes.

Eficiență

Într-o aplicație tipică a unei metode, scopul este de a putea implementa procesul determinist rezultat cu un algoritm suficient de eficient (cuvântul „eficient” înseamnă de obicei un algoritm al cărui timp de rulare depinde polinom de mărimea intrării), chiar dacă numărul de soluții posibile este uriașă (crește exponențial). De exemplu, luați în considerare problema deschiderii monedelor pentru n mare .

În mod ideal, având în vedere o stare intermediară (nod în arbore), probabilitatea condiționată de eșec (eticheta nodului) poate fi calculată eficient și precis. (Exemplul de mai sus este similar cu acesta.) Dacă acesta este cazul, algoritmul poate alege următorul nod la care să meargă calculând probabilitățile condiționate pentru fiecare succesor al nodului curent, atunci algoritmul se mută la orice succesor a cărui probabilitate condiționată este mai mic de 1. După cum sa discutat mai sus, există garanția existenței unui astfel de nod.

Din păcate, probabilitatea condiționată de eșec nu este ușor de calculat eficient. Există două tehnici standard de închidere pentru a rezolva acest lucru:

Folosind așteptarea condiționată: Multe dovezi probabilistice funcționează prin definirea explicită a unei variabile aleatoare Q , arătând că (i) așteptarea lui Q nu este mai mare decât (sau nu mai mică decât) o anumită valoare de prag și că (ii) în orice soluție în care Q nu nu depășește (nu mai puțin de) valoarea pragului, soluția este reușită. Apoi din (i) rezultă că există o soluție în care Q nu depășește pragul, iar din aceasta și (ii) rezultă că există o soluție reușită. (În exemplul de mai sus , Q este egal cu numărul de cozi, iar această valoare trebuie să fie cel puțin un prag de 1,5. În multe aplicații, Q este numărul de evenimente „rele” (nu neapărat independente) care au loc într-un anumit soluție, în care fiecare eveniment rău corespunde unei căi, conform căreia experimentul poate fi nereușit, iar așteptarea matematică a numărului de evenimente rele este mai mică de 1.)

În acest caz, pentru a menține probabilitatea condiționată de eșec sub 1, este suficient să se mențină valoarea așteptată condiționată a lui Q sub (sau peste) prag. Pentru a face acest lucru, în loc să calculeze probabilitatea condiționată de eșec, algoritmul calculează așteptarea matematică condiționată Q și se comportă în funcție de valoarea obținută - în fiecare nod intern există un anumit succesor, a cărui așteptare matematică condiționată nu este mai mare (nu mai mică decât) așteptarea matematică condiționată a nodului și algoritmul se mută de la nodul curent la acel moștenitor în care așteptarea matematică condiționată este mai mică (mai mare decât) pragul.

Utilizarea unui estimator pesimist: În unele cazuri, în loc de așteptarea condițională exactă a valorii lui Q , poate fi utilizată o limită destul de apropiată, numită estimator pesimist . Estimatorul pesimist este o funcție a stării curente. Estimatorul trebuie să fie o limită superioară (sau inferioară) a mediei condiționale Q a stării curente date și trebuie să aibă o medie necrescătoare (sau nedescrescătoare) la fiecare pas aleatoriu al experimentului. De regulă, un bun estimator pesimist poate fi obținut prin demontarea cu atenție a logicii dovezii originale.

Un exemplu de utilizare a așteptării condiționate

Acest exemplu arată metoda probabilității condiționate folosind așteptarea condiționată.

Lema de tăiere maximă

Având în vedere orice grafic nedirecționat G = ( V , E ), problema de tăiere maximă este de a colora fiecare vârf al graficului cu una dintre cele două culori (să zicem, alb și negru) pentru a maximiza numărul de muchii ale căror vârfuri de capăt au culori diferite. . (Vom vorbi despre astfel de margini ca o tăietură .)

Maximum Cut Lema (Max-Cut): În orice grafic G = ( V , E ) cel puțin | E |/2 margini pot fi tăiate.

Dovada probabilității. Vopsim fiecare vârf în negru sau alb în funcție de aruncarea unei monede simetrice. Pentru orice muchie e a lui E , probabilitatea ca muchia să fie aleasă pentru tăiere este 1/2. Apoi, conform liniarității așteptării matematice , așteptarea matematică a numărului de muchii tăiate este egală cu | E |/2. Astfel, există o colorare care decupează cel puțin | E |/2 muchii. QED

Metoda probabilităților condiționate cu așteptări matematice condiționate

Pentru a aplica metoda probabilităților condiționate, un experiment aleator este mai întâi modelat ca un lanț de pași mici aleatori. În acest caz, este firesc să considerăm fiecare pas ca o alegere de culoare pentru un anumit vârf (deci există | V | pași).

Alegerea aleatorie la fiecare pas este apoi înlocuită cu o alegere deterministă care menține probabilitatea condiționată de eșec, dată de colorarea vârfurilor, mai mică decât 1. (Aici , eșecul înseamnă că tăierea constă din mai puțin de | E |/2 muchii. )

În acest caz, probabilitatea condiționată de eșec nu este ușor de calculat. De fapt, dovada originală nu calculează probabilitatea de eșec în mod explicit. În schimb, dovada arată că numărul așteptat de muchii tăiate este de cel puțin | E |/2.

Fie variabila aleatoare Q egală cu numărul de muchii tăiate. Pentru a menține probabilitatea condiționată de eșec mai mică de 1, este suficient să se mențină așteptarea condiționată Q la sau peste pragul | E |/2. (Atâta timp cât așteptarea condiționată Q este cel puțin | E |/2, trebuie să existe o soluție realizabilă în care Q este cel puțin | E |/2, astfel încât probabilitatea condiționată de a ajunge la o astfel de soluție este pozitivă.) Pentru a menține așteptarea condiționată Q la | E |/2 sau mai mare, algoritmul de la fiecare pas va colora vârful în așa fel încât să maximizeze așteptarea condiționată rezultată a lui Q. Acest lucru este suficient, deoarece trebuie să existe un succesor de nod a cărui așteptare condiționată nu este mai mică decât așteptarea condiționată a stării curente (și, prin urmare, nu mai mică de | E |/2).

Dacă unele dintre vârfuri sunt deja colorate, care este așteptarea condiționată? Conform logicii dovezii originale, așteptarea condiționată a numărului de muchii tăiate este

numărul de muchii ale căror vârfuri de capăt sunt colorate în culori diferite + (1/2)*( numărul de muchii cu cel puțin un vârf necolorat ).

Algoritm

Algoritmul colorează fiecare vârf pentru a maximiza valoarea rezultată a așteptării condiționale. Acest lucru asigură că așteptarea condiționată rămâne la nivelul | E |/2 sau mai mare, iar acest lucru asigură că așteptarea condiționată a eșecului este mai mică de 1, ceea ce, la rândul său, garantează un rezultat de succes. Algoritmul poate fi simplificat astfel:

1. Pentru fiecare vârf u din V (în orice ordine):2. Luați în considerare vârfurile u vecine deja colorate . 3. Dacă există mai multe negre printre aceste vârfuri, vopsește- te în alb. 4. În caz contrar, vopsește- te în negru.

Prin construcție, acest algoritm determinist garantează tăierea a cel puțin jumătate din muchiile graficului dat. (Acest lucru face din algoritm un algoritm de aproximare de 0,5 pentru Max-cut .)

Un exemplu de utilizare a estimărilor pesimiste

Următorul exemplu demonstrează utilizarea estimărilor pesimiste.

Teorema lui Turan

Una dintre formulările teoremei lui Turan este următoarea:

Orice grafic G = ( V , E ) conține o mulțime independentă de mărime cel puțin | V |/( D +1), unde D = 2| E |/| V | este gradul mediu al graficului .

Dovada probabilistica a teoremei lui Turan

Luați în considerare următorul proces aleatoriu pentru construirea unei mulțimi independente S :

1. Setați setul S gol. 2. Pentru fiecare vârf u din V în ordine aleatorie: 3. Dacă niciunul dintre vecinii lui u nu este în S , adăugați u la S 4. Returnați S .

Este clar că procesul oferă un set independent. Orice vârf u care a fost luat în considerare înaintea tuturor vecinilor săi va fi adăugat la S . Astfel, dacă d ( u ) înseamnă puterea lui u , probabilitatea ca u să fie adăugat la S va fi de cel puțin 1/( d ( u )+1). Conform liniarității așteptărilor matematice , mărimea așteptată S nu este mai mică decât

\sum _{u\in V}{\frac {1}{d(u)+1}}~\geq ~{\frac {|V|}{D+1}}.

(Inegalitatea de mai sus rezultă din faptul că funcția 1/( x +1) este convexă în x , astfel încât la minimizarea părții stângi a expresiei sub semnul sumei, valorile sunt 2 | E | dacă fiecare d ( u ) = D = 2| E | /| V |.) QED

Metoda probabilităților condiționate folosind estimări pesimiste

În acest caz, procesul aleatoriu are | v | trepte. Fiecare pas ia în considerare un vârf u care nu este încă considerat și îl adaugă la S dacă niciunul dintre vârfurile învecinate nu a fost adăugat încă. Fie variabila aleatoare Q egală cu numărul de vârfuri adăugate la S . Demonstrarea arată că E [ Q ] ≥ | V |/( D +1).

Vom înlocui fiecare pas aleatoriu cu un pas determinist care păstrează așteptarea condiționată a lui Q de mai sus | V |/( D +1). Acest lucru va asigura un rezultat de succes, adică un rezultat în care mulțimea independentă S are o dimensiune nu mai mică de | V |/( D +1), care corespunde limitei din teorema lui Turan.

Dacă primul pas este făcut, fie S ( t ) să desemneze vârfurile adăugate înainte. Fie R ( t ) vârfurile neconsiderate care nu au vecini în S ( t ) . După primul pas, raționamentul ulterioar din demonstrația inițială că orice vârf w din R ( t ) cu probabilitate condiționată de cel puțin 1/( d ( w )+1) este adăugat la S înseamnă că așteptarea condiționată a lui Q nu este mai mică

|S^{(t)}|~+~\sum _{w\in R^{(t))){\frac {1}{d(w)+1)).

Fie Q ( t ) să desemneze valoarea așteptată de mai sus, care este numită estimatorul pesimist pentru media condiționată.

Dovada arată că estimatorul pesimist este inițial cel puțin | V |/( D +1). (Adică Q (0) ≥ | V |/( D +1).) Algoritmul face fiecare alegere evitând reducerea estimatorului pesimist, adică astfel încât Q ( t +1) ≥ Q ( t ) pentru fiecare t . Deoarece estimatorul pesimist este o limită inferioară a mediei condiționate, aceasta va asigura că media condiționată este întotdeauna mai mare decât | V |/( D +1), care, la rândul său, asigură că așteptarea condiționată a eșecului este sub 1.

Fie u vârful considerat de algoritm la pasul ( t + 1).

Dacă u are deja un vecin în S , atunci u nu se adaugă la S și (după verificarea Q ( t ) ) estimatorul pesimist rămâne neschimbat. Dacă u nu are vecini în S , atunci u se adaugă la S .

Dacă u este ales aleatoriu dintre vârfurile rămase, creșterea așteptată a estimatorului pesimist este nenegativă. [ Calcul. Probabilitatea, datorită alegerii unui vârf din R ( t ) , ca un termen dat 1/( d ( w )+1) să iasă din suma estimatorului pesimist nu depășește ( d ( w )+1) /| R ( t ) |, astfel încât scăderea preconizată în fiecare termen să nu depășească 1/| R ( t ) |. Există R ( t ) termeni în sumă. Astfel, scăderea așteptată a sumei nu depășește 1. Între timp, dimensiunea lui S crește cu 1.]

Astfel, trebuie să existe o alegere a u care să mențină estimatorul pesimist nedescrescător.

Algoritm pentru maximizarea estimării pesimiste

Algoritmul de mai jos selectează fiecare vârf u pentru a maximiza estimatorul pesimist rezultat. Conform raționamentului de mai sus, aceasta împiedică estimatorul pesimist să scadă și garantează o ieșire cu succes.

Mai jos , N ( t ) ( u ) înseamnă vecinii lui u din R ( t ) (adică vecinii lui u care nu sunt în S și nu au vecini în S ).

1. Setați S gol. 2. Atâta timp cât există un vârf u neconsiderat care nu are vecini în S : 3. Adăugați un vârf u la S care minimizează .

\sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}

4. Întoarce S .

Algoritmi care nu maximizează estimarea pesimistă

Pentru ca metoda probabilităților condiționate să funcționeze, este suficient ca algoritmul să nu scadă estimarea pesimistă (sau să nu o mărească, în funcție de situație). Algoritmul nu maximizează (sau minimizează) neapărat estimarea pesimistă. Acest lucru oferă o oarecare libertate în dezvoltarea algoritmului.

1. Setați S gol. 2. Atâta timp cât există un vârf u într-un graf fără vecini în S : 3. Adăugați un astfel de vârf u la S dacă u minimizează d ( u ) (gradul inițial al lui u ). 4. Întoarce S . 1. Setați S gol. 2. În timp ce graficul rămas nu este gol: 3. Adăugați un vârf u la S dacă u are gradul minim în graficul rămas . 4. Îndepărtați u și toți vecinii vârfului din grafic. 5. Întoarce S .

Fiecare algoritm este analizat cu același estimator pesimist ca înainte. La fiecare pas al algoritmului, creșterea totală a estimatorului pesimist este

1-\sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1)),

unde N ( t ) ( u ) înseamnă vecinii vârfului u din graficul rămas (adică în R ( t ) ).

În primul algoritm, creșterea este nenegativă datorită alegerii lui u ,

\sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}\leq (d(u) +1){\frac {1}{d(u)+1}}=1

unde d ( u ) este gradul vârfului u din graficul original.

În al doilea algoritm, creșterea este nenegativă datorită alegerii lui u ,

\sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}\leq (d'(u) )+1){\frac {1}{d'(u)+1}}=1

unde d′ ( u ) este gradul vârfurilor u din graficul rămas.

Vezi și

Literatură

Paul Erdős , JL Selfridge. Despre un joc combinatoric // Journal of Combinatorial Theory, Seria A . - 1973. - T. 14 , nr. 3 . — S. 298–301 . - doi : 10.1016/0097-3165(73)90005-8 .
Joel H. Spencer. Zece prelegeri despre metoda probabilistică . - SIAM, 1987. - ISBN 978-0-89871-325-1 .
Prabhakar Raghavan. Construcția probabilistică a algoritmilor determiniști: aproximarea programelor întregi de ambalare // Journal of Computer and System Sciences . - 1988. - T. 37 , nr. 2 . — S. 130–143 . - doi : 10.1016/0022-0000(88)90003-7 .

Lectură pentru lecturi suplimentare

Noga Alon , Joel Spencer. Metoda probabilistică . - Al treilea. — Hoboken, NJ: John Wiley and Sons, 2008. — p. 250 și urm. (în ediția a 2-a, ISBN 9780471653981 ). - (Seria Wiley-Interscience în matematică discretă și optimizare). — ISBN 978-0-470-17020-5 .

Rajeev Motwani , Prabhakar Raghavan. Algoritmi randomizati . — Cambridge University Press . - S. 120-. - ISBN 978-0-521-47465-8 .
Vijay Vazirani. Algoritmi de aproximare . — Springer Verlag . - S. 130-. - ISBN 978-3-540-65367-7 .

Link -uri

The probabilistic method — method of conditional probabilities , intrare pe blog de Neal E. Young, accesat 19.04.2012.