Feltételes valószínűségi módszer

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2017. június 19-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A matematikában bizonyos kombinatorikus tulajdonságokkal rendelkező matematikai objektumok létezésének bizonyítására a valószínűségi módszert alkalmazzák , amelyben kimutatják, hogy valamely valószínűségi mintából kiválasztott véletlen objektum pozitív valószínűséggel rendelkezik a kívánt tulajdonsággal. Ezért ezek a létezési bizonyítások nem építő jellegűek – nem írnak le kifejezetten módszert ilyen objektumok létrehozására vagy kiszámítására.

A feltételes valószínűségek módszere [1] [2] [3] egy ilyen bizonyítást "egészen pontos értelemben" alakít át hatékony determinisztikus algoritmussá , amely garantálja a kívánt tulajdonságokkal rendelkező objektum felfedezését. Vagyis a módszer derandomizálja a bizonyítást. Az alapötlet az, hogy egy véletlenszerű kísérletben minden véletlenszerű választást lecserélünk egy determinisztikus választásra oly módon, hogy a választás miatti sikertelenség feltételes elvárása 1-nél kisebb legyen.

A módszer részben releváns a valószínűségi kerekítéssel összefüggésben (amely valószínűségi módszert használ közelítő algoritmusok kidolgozásához ).

A feltételes valószínűségek módszerének alkalmazásakor a pesszimista becslő szakkifejezés az eredeti bizonyítás feltételes valószínűsége (vagy feltételes átlaga) helyett használt értékekre utal .

Áttekintés

Raghavan [3] a következő leírást adja a módszerről:

Először egy bizonyíthatóan jó közelítő megoldás létezését mutatjuk be valószínűségi módszerrel ... [Ezután] megmutatjuk, hogy a valószínűségi létezésigazolás nagyon pontos értelemben determinisztikus közelítő algoritmussá alakítható.

(Raghavan a valószínűségi kerekítés kontextusában tárgyalja a módszert , de a módszer az általános valószínűségi módszerrel működik.)

Ahhoz, hogy a módszert valószínűségi bizonyításra alkalmazzuk, az eredeti bizonyításban véletlenszerűen kiválasztott objektumnak kiválaszthatónak kell lennie véletlenszerű kísérletekkel, amelyek "kis" véletlenszerű választások sorozatából állnak.

Van egy triviális példa az elv illusztrálására.

Lemma: Lehetőség van három érme felfedésére (rejteni) úgy, hogy a farok száma legalább 2 legyen. Valószínűség bizonyítása. Ha véletlenszerűen három érmét dobunk fel, a farok várható száma 1,5. Így kell lennie olyan megoldásnak (az érmék kinyitásának módja), hogy a rudak száma legalább 1,5 legyen. Mivel a farok száma egy egész szám , ebben a megoldásban legalább 2 farok van. QED

Ebben a példában egy véletlenszerű kísérlet három szimmetrikus érme feldobásából áll. A kísérletet az ábrán egy fa illusztrálja. Nyolc eredmény van, amelyek mindegyike egy-egy levélnek felel meg a fában. A véletlenszerű kísérletben a teszt egy véletlenszerű átmenet kiválasztásának felel meg a gyökértől (a fa legfelső csomópontjától, ahol nincsenek érmék) a levélre. Sikeres döntések azok, amelyeknél legalább két érme felbukkan. A fa belső csomópontjai olyan részben meghatározott megoldásoknak felelnek meg, amelyekben 0, 1, 2 stb. érmék nyitva vannak.

A feltételes valószínűségek módszerének alkalmazásához a hangsúly a meghibásodás feltételes valószínűségén van, amelyet a kísérlet lépésről lépésre haladva hozott egymást követő választás adja. A diagramban minden csomópont ezzel a feltételes valószínűséggel van felcímkézve. (Például, ha csak az első érme derül ki, és a kísérlet eredménye farok, akkor ez a gyökér második gyermekének felel meg. Ennél a köztes állapotnál a meghibásodás valószínűsége 0,25.)

A feltételes valószínűségi módszer a véletlenszerű kísérletben a gyökértől a levélig terjedő véletlenszerű átmenetet egy determinisztikus lépéssel helyettesíti, amelyben minden lépést a következő invariancia-feltétel szabályozására választanak ki:

az aktuális állapot által meghatározott feltételes meghibásodási elvárás kisebb, mint 1.

Ez biztosítja a 0-val jelölt levél elérését, vagyis a sikeres megoldást.

Az invariancia feltétele kezdetben (a gyökérnél) teljesül, mert az eredeti bizonyítás azt mutatja, hogy a meghibásodás (feltétel nélküli) valószínűsége kisebb, mint 1. A feltételes valószínűség bármely belső csomópontnál a csomópont örököseinek feltételes valószínűségeinek számtani átlaga . Ez a tulajdonság azért fontos, mert azt jelenti, hogy minden 1-nél kisebb feltételes valószínűségű belső csomópontnak van legalább egy utódja, amelynek feltételes valószínűsége kisebb, mint 1. Így bármelyik belső csomóponton mindig választhatunk olyan utódokat, amelyeknek átadásakor fenntartotta az invariancia feltételt. Mivel az invariancia feltétele a legvégéig megmarad, amikor a kísérlet eléri a levelet és minden választási lehetőség meg van határozva, az így kapott megoldásnak sikeresnek kell lennie.

Hatékonyság

Egy tipikus módszeralkalmazásban az a cél, hogy az eredményül kapott determinisztikus folyamatot egy kellően hatékony algoritmussal (a „hatékony” szó általában olyan algoritmust jelent, amelynek futási ideje polinomiálisan függ a bemenet méretétől) valósítható legyen, még akkor is, ha a szám A lehetséges megoldások száma óriási (exponenciálisan növekszik). Vegyük például az érmék kinyitásának problémáját nagy n esetén .

Ideális esetben egy köztes állapot (csomópont a fában) esetén a meghibásodás feltételes valószínűsége (csomópontcímke) hatékonyan és pontosan kiszámítható. (A fenti példa ehhez hasonló.) Ha ez a helyzet, akkor az algoritmus kiválaszthatja a következő csomópontot, amelyhez az aktuális csomópont minden utódjához tartozó feltételes valószínűségeket számítja ki, majd az algoritmus bármely utódhoz lép, amelynek feltételes valószínűsége kevesebb, mint 1. Amint fentebb tárgyaltuk, egy ilyen csomópont megléte garantált.

Sajnos a meghibásodás feltételes valószínűségét nem könnyű hatékonyan kiszámítani. Két szabványos bezárási technika létezik ennek kezelésére:

Feltételes elvárás használata: Sok valószínűségi bizonyítás úgy működik, hogy explicit módon definiál egy Q valószínűségi változót , ami azt mutatja, hogy (i) a Q elvárása nem nagyobb (vagy nem kisebb, mint) valamilyen küszöbérték, és (ii) minden olyan megoldásban, ahol Q igen nem haladja meg (nem kevesebb, mint) a küszöbértéket, a megoldás sikeres. Ekkor az (i)-ből következik, hogy van olyan megoldás, amelyben Q nem lépi túl a küszöböt, ebből és (ii)-ből pedig az következik, hogy van sikeres megoldás. (A fenti példában a Q egyenlő a végek számával, és ennek az értéknek legalább 1,5-ös küszöbnek kell lennie. Sok alkalmazásban Q a „rossz” események (nem feltétlenül független) száma, amelyek egy adott területen fordulnak elő. megoldás, ahol minden rossz esemény egy útnak felel meg, amely szerint a kísérlet sikertelen lehet, és a rossz események számának matematikai elvárása 1-nél kisebb.)

Ebben az esetben ahhoz, hogy a meghibásodás feltételes valószínűsége 1 alatt maradjon, elegendő Q feltételes várható értékét a küszöb alatt (vagy felette) tartani. Ehhez a hiba feltételes valószínűségének kiszámítása helyett az algoritmus kiszámítja a Q feltételes matematikai elvárást , és a kapott érték szerint viselkedik - minden belső csomópontban van egy bizonyos utód, amelynek feltételes matematikai elvárása nem több (nem kisebb, mint) a csomópont feltételes matematikai elvárása, és az algoritmus az aktuális csomópontról arra az örökösre lép, amelyben a feltételes matematikai elvárás kisebb (nagyobb, mint a küszöb).

Pesszimista becslő használata: Bizonyos esetekben a Q érték pontos feltételes elvárása helyett egy meglehetősen közeli korlát, az úgynevezett pesszimista becslés használható . A pesszimista becslő az aktuális állapot függvénye. A becslőnek felső (vagy alsó) korlátnak kell lennie az adott pillanatnyi állapot feltételes Q átlagához, és a kísérlet minden véletlenszerű lépésében nem növekvő (vagy nem csökkenő) átlaggal kell rendelkeznie. Általában jó pesszimista becslőt kaphatunk, ha gondosan szétszedjük az eredeti bizonyítás logikáját.

Példa a feltételes elvárás használatára

Ez a példa a feltételes valószínűség módszerét mutatja be feltételes várakozással.

A maximális vágási lemma

Tetszőleges irányítatlan G = ( V , E ) gráf esetén a maximális vágási probléma az, hogy a gráf minden csúcsát két szín valamelyikével színezzük (mondjuk fekete és fehér), hogy maximalizáljuk azon élek számát, amelyek végcsúcsai különböző színűek. . (Az ilyen élekről vágásként fogunk beszélni .)

Maximum Cut Lemma (Max-Cut): Bármely gráfban G = ( V , E ) legalább | E |/2 él vágható.

Valószínűség bizonyítása. Az egyes csúcsokat egy szimmetrikus érme feldobása szerint feketére vagy fehérre festjük. E bármely e élére 1/2 annak a valószínűsége, hogy az élt a vágáshoz választjuk. Ekkor a matematikai elvárás linearitása szerint a vágott élek számának matematikai elvárása egyenlő | E |/2. Így létezik olyan színezés, amely legalább | E |/2 él. QED

Feltételes valószínűségek módszere feltételes matematikai elvárásokkal

A feltételes valószínűségek módszerének alkalmazásához egy véletlenszerű kísérletet először kis véletlenszerű lépések láncaként modellezünk. Ebben az esetben természetes, hogy minden lépést egy adott csúcs színválasztásának tekintünk (így vannak | V | lépések).

Az egyes lépésekben a véletlenszerű választást ezután egy determinisztikus választás váltja fel, amely a csúcsszínezés által megadott feltételes meghibásodási valószínűséget 1-nél kisebb értéken tartja. (Itt a hiba azt jelenti, hogy a vágás kevesebb, mint | E |/2 élből áll. )

Ebben az esetben a meghibásodás feltételes valószínűségét nem könnyű kiszámítani. Valójában az eredeti bizonyíték nem számolja ki kifejezetten a meghibásodás valószínűségét. Ehelyett a bizonyítás azt mutatja, hogy a vágott élek várható száma legalább | E |/2.

Legyen a Q valószínűségi változó egyenlő a vágott élek számával. Ahhoz, hogy a meghibásodás feltételes valószínűsége 1-nél kisebb legyen, elegendő a Q feltételes várakozást a küszöbértéken vagy a felett tartani | E |/2. (Amíg a Q feltételes elvárás legalább | E |/2, addig kell lennie olyan elérhető megoldásnak, ahol Q legalább | E |/2, tehát az ilyen megoldás elérésének feltételes valószínűsége pozitív.) A feltételes elvárás Q at | E |/2 vagy magasabb, az algoritmus minden lépésben úgy színezi a csúcsot, hogy maximalizálja a Q eredő feltételes elvárását . Ez elegendő, hiszen kell lennie egy csomópontutódnak, amelynek feltételes elvárása nem kisebb, mint az aktuális állapot feltételes elvárása (tehát nem kisebb, mint | E |/2).

Ha a csúcsok egy része már színezett, mi a feltételes elvárás? Az eredeti bizonyítás logikája szerint a vágott élek számának feltételes elvárása az

azoknak az éleknek a száma, amelyek végcsúcsai különböző színekkel vannak színezve + (1/2)*( legalább egy színtelen csúcsot tartalmazó élek száma ).

Algoritmus

Az algoritmus minden csúcsot kiszínez annak érdekében, hogy maximalizálja a feltételes elvárás eredő értékét. Ez biztosítja, hogy a feltételes elvárás a | szinten maradjon E |/2 vagy magasabb, és ez biztosítja, hogy a hiba feltételes elvárása 1-nél kisebb legyen, ami viszont garantálja a sikeres eredményt. Az algoritmus a következőkre egyszerűsíthető:

1. Minden V - ből származó u csúcshoz (bármilyen sorrendben): 2. Tekintsük a már kiszínezett szomszédos u csúcsokat. 3. Ha ezen csúcsok között több fekete is van, fesd u fehérre. 4. Ellenkező esetben fesd feketére .

Ez a determinisztikus algoritmus konstrukcióval garantálja, hogy az adott gráf éleinek legalább a felét levágja. (Ez teszi az algoritmust 0,5-ös közelítési algoritmussá a Max-cut számára .)

Példa a pesszimista becslések használatára

A következő példa a pesszimista becslések használatát mutatja be.

Turan-tétel

A Turan-tétel egyik megfogalmazása a következő:

Bármely G = ( V , E ) gráf egy legalább | méretű független halmazt tartalmaz V |/( D +1), ahol D = 2| E |/| V | a gráf átlagos foka .

A Turan-tétel valószínűségi bizonyítása

Tekintsük a következő véletlenszerű folyamatot egy független S halmaz felépítéséhez :

1. Állítsa üresre az S készletet.2. V - ből minden u csúcsra véletlenszerű sorrendben:3. Ha u egyik szomszédja sincs S -ben, add hozzá u -t S -hez 4. Adja vissza S -t .

Nyilvánvaló, hogy a folyamat független halmazt ad. Bármely u csúcs , amelyet minden szomszédja előtt vettünk figyelembe, hozzáadódik S -hez . Így, ha d ( u ) u hatványát jelenti , annak a valószínűsége, hogy u hozzáadódik S -hez , legalább 1/( d ( u )+1). A matematikai elvárás linearitása szerint a várható S méret nem kisebb, mint

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

(A fenti egyenlőtlenség abból adódik, hogy az 1/( x +1) függvény konvex x - ben , így ha a kifejezés bal oldalát az összeg előjele alatt minimalizáljuk, az értékek 2| E |, ha minden d ( u ) = D = 2| E | /| V |.) QED

A feltételes valószínűségek módszere pesszimista becslésekkel

Ebben az esetben a véletlenszerű folyamat | v | lépések. Minden lépés figyelembe vesz néhány még nem figyelembe vett u csúcsot , és hozzáadja S -hez, ha a szomszédos csúcsok közül még egyik sem került hozzáadásra. Legyen a Q valószínűségi változó egyenlő az S -hez hozzáadott csúcsok számával . A bizonyítás azt mutatja, hogy E [ Q ] ≥ | V |/( D +1).

Minden véletlenszerű lépést lecserélünk egy determinisztikus lépésre, amely megőrzi a Q feltételes elvárását | V |/( D +1). Ez biztosítja a sikeres eredményt, vagyis olyan eredményt, amelyben az S független halmaz mérete nem kisebb, mint | V |/( D +1), ami a Turan-tételben szereplő határnak felel meg.

Ha az első lépés megtörtént, jelölje S ( t ) a korábban hozzáadott csúcsokat. Jelölje R ( t ) azokat a nem figyelembe vett csúcsokat, amelyeknek nincs szomszédjuk S ( t ) -ben . Az első lépés után az eredeti bizonyításban szereplő további érvelés, miszerint R ( t ) bármely w csúcsa legalább 1/( d ( w )+1) feltételes valószínűséggel hozzáadódik S - hez , azt jelenti, hogy Q feltételes elvárása nem kisebb .

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

Jelölje Q ( t ) a fenti várható értéket, amelyet a feltételes átlag pesszimista becslőjének nevezünk.

A bizonyítás azt mutatja, hogy a pesszimista becslő kezdetben legalább | V |/( D +1). (Azaz Q (0) ≥ | V |/( D +1).) Az algoritmus minden választást úgy választ, hogy elkerülje a pesszimista becslő redukcióját, vagyis úgy, hogy Q ( t +1 ) ≥ Q ( t ) mindegyik t . Mivel a pesszimista becslő a feltételes átlag alsó határa, ez biztosítja, hogy a feltételes átlag mindig magasabb legyen, mint | V |/( D +1), ami viszont biztosítja, hogy a meghibásodás feltételes elvárása 1 alatt legyen.

Legyen u az algoritmus által a ( t + 1) lépésben figyelembe vett csúcs.

Ha u -nak már van szomszédja S -ben, akkor u -t nem adjuk hozzá S -hez, és ( Q ( t ) ellenőrzése után ) a pesszimista becslő változatlan marad. Ha u -nak nincsenek szomszédai S -ben, akkor u -t hozzáadjuk S -hez .

Ha u -t véletlenszerűen választjuk ki a fennmaradó csúcsok közül, akkor a pesszimista becslő várható növekedése nem negatív. [ Számítás. Annak a valószínűsége, hogy az R ( t ) -ből egy csúcsot választottunk , annak a valószínűsége, hogy egy adott 1/( d ( w )+1) tag kiesik a pesszimista becslő összegéből, nem haladja meg a ( d ( w )+1) értéket. /| R ( t ) |, hogy az egyes tagokban várható csökkenés ne haladja meg az 1/| -t R ( t ) |. Az összegben R ( t ) tagok vannak. Így az összeg várható csökkenése nem haladja meg az 1-et. Eközben S mérete 1-gyel nő.]

Így kell lennie valamilyen u -nak, amely nem csökkenti a pesszimista becslőt.

Algoritmus a pesszimista becslés maximalizálására

Az alábbi algoritmus kiválasztja az egyes u csúcsokat , hogy maximalizálja a kapott pesszimista becslőt. A fenti érvelés szerint ez megakadályozza a pesszimista becslő csökkenését, és garantálja a sikeres kilépést.

Az alábbiakban N ( t ) ( u ) u szomszédjait jelenti R ( t ) -ben (vagyis olyan u szomszédait, amelyek nincsenek S -ben és nincs szomszédjuk S -ben ).

1. Állítsa üresre az S -t. 2. Mindaddig, amíg van egy figyelembe nem vett u csúcs , amelynek nincs szomszédja S -ben :3. Adjunk hozzá egy u csúcsot S -hez , amely minimalizálja a .

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

4. S visszaküldése .

Algoritmusok, amelyek nem maximalizálják a pesszimista becslést

A feltételes valószínűségek módszerének működéséhez elegendő, ha az algoritmus nem csökkenti a pesszimista becslést (vagy nem növeli, helyzettől függően). Az algoritmus nem feltétlenül maximalizálja (vagy minimalizálja) a pesszimista becslést. Ez némi szabadságot ad az algoritmus fejlesztésében.

1. Állítsa üresre az S -t. 2. Amíg van egy u csúcs egy gráfban szomszédok nélkül S -ben :3. Adjunk hozzá egy ilyen u csúcsot S -hez , ha u minimalizálja d ( u )-t ( u kezdeti fokát ).4. S visszaküldése . 1. Állítsa üresre az S -t. 2. Amíg a fennmaradó grafikon nem üres:3. Adjunk hozzá egy u csúcsot S -hez , ha u -nak van minimális foka a fennmaradó gráfban. 4. Távolítsa el u -t és a csúcs összes szomszédját a gráfból.5. S visszaküldése .

Mindegyik algoritmust ugyanazzal a pesszimista becslővel elemezzük, mint korábban. Az algoritmus minden lépésében a pesszimista becslő teljes növekedése az

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

ahol N ( t ) ( u ) az u csúcs szomszédjait jelenti a fennmaradó gráfban (azaz R ( t ) -ben ).

Az első algoritmusban a növekedés nem negatív az u választása miatt ,

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

ahol d ( u ) az u csúcs fokszáma az eredeti gráfban.

A második algoritmusban a növekedés nem negatív az u választása miatt ,

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

ahol d′ ( u ) az u csúcsok foka a fennmaradó gráfban.

Lásd még

Irodalom

Paul Erdős , JL Selfridge. Kombinatorikus játékról // Journal of Combinatorial Theory, A sorozat . - 1973. - T. 14 , sz. 3 . – S. 298–301 . - doi : 10.1016/0097-3165(73)90005-8 .
Joel H. Spencer. Tíz előadás a valószínűségi módszerről . - SIAM, 1987. - ISBN 978-0-89871-325-1 .
Prabhakar Raghavan. Determinisztikus algoritmusok valószínűségi felépítése: egészszámú programok közelítése // Journal of Computer and System Sciences . - 1988. - T. 37 , sz. 2 . – S. 130–143 . - doi : 10.1016/0022-0000(88)90003-7 .

Olvasás további olvasáshoz

Noga Alon , Joel Spencer. A valószínűségi módszer . — Harmadik. – Hoboken, NJ: John Wiley and Sons, 2008. – 250. és azt követő oldalak. (2. kiadás, ISBN 9780471653981 ). - (Wiley-Interscience Series in Discrete Mathematics and Optimization). — ISBN 978-0-470-17020-5 .

Rajeev Motwani , Prabhakar Raghavan. Véletlenszerű algoritmusok . — Cambridge University Press . - S. 120-. - ISBN 978-0-521-47465-8 .
Vijay Vazirani. Közelítő algoritmusok . — Springer Verlag . - S. 130-. - ISBN 978-3-540-65367-7 .

Linkek

A valószínűségi módszer — a feltételes valószínűségek módszere , Neal E. Young blogbejegyzése, Hozzáférés dátuma: 2012.04.19.