Villkorlig sannolikhetsmetod

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 19 juni 2017; verifiering kräver 1 redigering .

Inom matematiken , för att bevisa förekomsten av matematiska objekt med vissa kombinatoriska egenskaper, används den probabilistiska metoden , där det visas att ett slumpmässigt objekt valt från något probabilistiskt urval har den nödvändiga egenskapen med en positiv sannolikhet. Därför är dessa existensbevis icke -konstruktiva – de beskriver inte uttryckligen en metod för att konstruera eller beräkna sådana objekt.

Metoden med villkorade sannolikheter [1] [2] [3] förvandlar ett sådant bevis i "ganska exakt mening" till en effektiv deterministisk algoritm som garanterar upptäckten av ett objekt med önskade egenskaper. Det vill säga metoden avrandomiserar beviset. Grundidén är att ersätta varje slumpmässigt val i ett slumpmässigt experiment med ett deterministiskt val på ett sådant sätt att den villkorade förväntan om misslyckande på grund av val hålls mindre än 1.

Metoden är delvis relevant i samband med probabilistisk avrundning (som använder en probabilistisk metod för att utveckla approximationsalgoritmer ).

När metoden för villkorade sannolikheter tillämpas, hänvisar den tekniska termen pessimistisk estimator till de värden som används i stället för den villkorliga sannolikheten (eller villkorliga medelvärdet) för det ursprungliga beviset.

Översikt

Raghavan [3] ger följande beskrivning av metoden:

Vi visar först förekomsten av en bevisligen bra ungefärlig lösning med hjälp av en probabilistisk metod ... [Vi visar då] att det probabilistiska existensbeviset kan omvandlas, i en mycket exakt mening, till en deterministisk approximationsalgoritm.

(Raghavan diskuterar metoden i samband med probabilistisk avrundning , men metoden fungerar med den generella probabilistiska metoden.)

För att tillämpa metoden på ett probabilistiskt bevis måste ett slumpmässigt valt objekt i originalbeviset vara valbart genom slumpmässiga experiment bestående av en sekvens av "små" slumpmässiga val.

Det finns ett trivialt exempel för att illustrera principen.

Lemma: Det är möjligt att avslöja (dolda) tre mynt så att antalet svansar är minst 2. Sannolikhetsbevis. Om tre mynt kastas slumpmässigt är det förväntade antalet svansar 1,5. Det måste alltså finnas en lösning (ett sätt att öppna mynten), så att antalet staplar blir minst 1,5. Eftersom antalet svansar är ett heltal finns det minst 2 svansar i denna lösning. QED

I det här exemplet består ett slumpmässigt experiment av att kasta tre symmetriska mynt. Experimentet illustreras med ett träd i figuren. Det finns åtta resultat som var och en motsvarar ett löv i trädet. Testet i slumpexperimentet motsvarar att välja en slumpmässig övergång från roten (trädets översta nod där inga mynt är exponerade) till bladet. Framgångsrika beslut är de där minst två mynt kommer upp. De interna noderna i trädet motsvarar delvis definierade lösningar där 0, 1, 2 och så vidare mynt är öppna.

För att tillämpa metoden för villkorade sannolikheter ligger fokus på den villkorade sannolikheten för misslyckande, givet av det successiva valet som görs när experimentet går från steg till steg. I diagrammet är varje nod märkt med denna villkorade sannolikhet. (Till exempel, om bara det första myntet avslöjas, och resultatet av experimentet är svansar, motsvarar detta det andra barnet av roten. För detta mellantillstånd är sannolikheten för misslyckande 0,25.)

Den villkorliga sannolikhetsmetoden ersätter den slumpmässiga övergången från rot till blad i ett slumpmässigt experiment med ett deterministiskt pass där varje steg väljs för att kontrollera följande invariansvillkor:

den villkorade förväntningen på misslyckande, bestämd av det aktuella tillståndet, är mindre än 1.

Detta säkerställer att bladet märkt 0 nås, det vill säga en framgångsrik lösning.

Invariansvillkoret är initialt (vid roten) uppfyllt eftersom det ursprungliga beviset visar att den (ovillkorliga) sannolikheten för misslyckande är mindre än 1. Den villkorliga sannolikheten vid vilken intern nod som helst är det aritmetiska medelvärdet av de villkorade sannolikheterna för nodens arvingar. Denna egenskap är viktig eftersom den antyder att varje intern nod med en villkorad sannolikhet mindre än 1 har minst en efterföljare vars villkorade sannolikhet är mindre än 1. Således kan man vid vilken intern nod som helst välja någon efterföljare så att när man går över till han bibehöll invarianstillståndet. Eftersom invariansvillkoret bibehålls till slutet, när experimentet når bladet och alla val är bestämda, måste den lösning som erhålls på detta sätt vara framgångsrik.

Effektivitet

I en typisk metodapplikation är målet att kunna implementera den resulterande deterministiska processen med en tillräckligt effektiv algoritm (ordet "effektiv" betyder vanligtvis en algoritm vars körtid beror polynomiellt på storleken på inmatningen), även om antalet av möjliga lösningar är enorm (växer exponentiellt). Tänk till exempel på problemet med att öppna mynt för stora n .

Idealiskt, givet ett mellantillstånd (nod i trädet), kan den villkorade sannolikheten för fel (nodetikett) beräknas effektivt och korrekt. (Exemplet ovan liknar detta.) Om så är fallet kan algoritmen välja nästa nod att gå till genom att beräkna de villkorade sannolikheterna för varje efterföljare av den aktuella noden, sedan flyttar algoritmen till valfri efterföljare vars villkorade sannolikhet är mindre än 1. Som diskuterats ovan finns det garanti för att det finns en sådan nod.

Tyvärr är den villkorade sannolikheten för misslyckande inte lätt att beräkna effektivt. Det finns två vanliga stängningstekniker för att hantera detta:

Använda villkorlig förväntan: Många probabilistiska bevis fungerar genom att explicit definiera en slumpvariabel Q , som visar att (i) förväntan på Q inte är större än (eller inte mindre än) något tröskelvärde, och att (ii) i alla lösningar där Q gör det inte överstiga (inte mindre än) tröskelvärdet, är lösningen framgångsrik. Sedan följer det av (i) att det finns en lösning där Q inte överskrider tröskeln, och av detta och (ii) följer att det finns en framgångsrik lösning. (I exemplet ovan är Q lika med antalet svansar, och detta värde måste vara minst ett tröskelvärde på 1,5. I många applikationer är Q antalet "dåliga" händelser (inte nödvändigtvis oberoende) som inträffar i en given given lösning, där varje dålig händelse motsvarar en väg, enligt vilken experimentet kan misslyckas, och den matematiska förväntningen på antalet dåliga händelser är mindre än 1.)

I detta fall, för att hålla den villkorade sannolikheten för misslyckande under 1, är det tillräckligt att hålla det villkorade förväntade värdet för Q under (eller över) tröskeln. För att göra detta, istället för att beräkna den villkorade sannolikheten för misslyckande, beräknar algoritmen den villkorliga matematiska förväntan Q och beter sig enligt det erhållna värdet - i varje intern nod finns det en viss efterföljare, vars villkorliga matematiska förväntan inte är mer (inte mer) mindre än) nodens villkorliga matematiska förväntan och algoritmen flyttas från den aktuella noden till den arvtagare där den villkorliga matematiska förväntan är mindre (större än) tröskeln.

Användning av en pessimistisk estimator: I vissa fall, istället för den exakta villkorade förväntan på värdet av Q , kan en ganska nära gräns, kallad en pessimistisk estimator , användas . Den pessimistiska estimatorn är en funktion av det aktuella tillståndet. Estimatorn måste vara en övre (eller nedre) gräns på det villkorliga medelvärdet Q för det givna aktuella tillståndet, och den måste ha ett icke-ökande (eller icke-minskande) medelvärde vid varje slumpmässigt steg i experimentet. Som regel kan en bra pessimistisk skattare erhållas genom att noggrant demontera logiken i det ursprungliga beviset.

Ett exempel på användning av villkorlig förväntan

Detta exempel visar den villkorade sannolikhetsmetoden med villkorad förväntan.

Det maximala skärlemmat

Med tanke på alla oriktade grafer G = ( V , E ), är det maximala skärningsproblemet att färga varje vertex i grafen med en av två färger (säg, svart och vitt) för att maximera antalet kanter vars ändhörn har olika färger . (Vi kommer att prata om sådana kanter som ett snitt .)

Maximum Cut Lemma (Max-Cut): I valfri graf G = ( V , E ) minst | E |/2 kanter kan skäras.

Sannolikhetsbevis. Vi målar varje vertex svart eller vitt enligt hur ett symmetriskt mynt kastas. För varje kant e av E är sannolikheten att kanten väljs för skärningen 1/2. Sedan, enligt linjäriteten hos den matematiska förväntan , är den matematiska förväntan av antalet skurna kanter lika med | E |/2. Det finns alltså en färgning som skär ut åtminstone | E |/2 kanter. QED

Metod för betingade sannolikheter med villkorade matematiska förväntningar

För att tillämpa metoden med betingade sannolikheter modelleras först ett slumpmässigt experiment som en kedja av små slumpmässiga steg. I det här fallet är det naturligt att betrakta varje steg som ett val av färg för en viss vertex (så det finns | V | steg).

Det slumpmässiga valet vid varje steg ersätts sedan av ett deterministiskt val som håller den villkorade sannolikheten för fel, given av vertexfärgningen, mindre än 1. (Här betyder misslyckande att snittet består av mindre än | E |/2 kanter. )

I det här fallet är den villkorade sannolikheten för misslyckande inte lätt att beräkna. Faktum är att det ursprungliga beviset inte explicit beräknar sannolikheten för misslyckande. Istället visar beviset att det förväntade antalet avskurna kanter är minst | E |/2.

Låt den slumpmässiga variabeln Q vara lika med antalet skurna kanter. För att hålla den villkorade sannolikheten för misslyckande mindre än 1, räcker det att hålla den villkorade förväntan Q vid eller över tröskeln | E |/2. (Så länge den villkorade förväntan Q är minst | E |/2 måste det finnas en uppnåbar lösning där Q är minst | E |/2, så den villkorade sannolikheten för att nå en sådan lösning är positiv.) För att behålla villkorlig förväntan Q vid | E |/2 eller högre, kommer algoritmen vid varje steg att färga vertexet på ett sådant sätt att den resulterande villkorliga förväntan på Q maximeras . Detta är tillräckligt, eftersom det måste finnas en nodefterträdare vars villkorliga förväntan inte är mindre än den villkorade förväntan för det aktuella tillståndet (och därför inte mindre än | E |/2).

Om några av hörnen redan är färgade, vad är den villkorade förväntan? Enligt logiken i det ursprungliga beviset är den villkorade förväntan på antalet skurna kanter

antalet kanter vars ändtoppar är färgade i olika färger + (1/2)*( antal kanter med minst en ofärgad vertex ).

Algoritm

Algoritmen färgar varje vertex för att maximera det resulterande värdet av den villkorliga förväntan. Detta säkerställer att den villkorade förväntningen förblir på nivån | E |/2 eller högre, och detta säkerställer att den villkorade förväntningen på misslyckande är mindre än 1, vilket i sin tur garanterar ett framgångsrikt resultat. Algoritmen kan förenklas till följande:

1. För varje hörn u från V (i valfri ordning): 2. Betrakta redan färgade angränsande u -hörn. 3. Om det finns fler svarta bland dessa hörn, måla u vit. 4. Annars målar du svart.

Genom konstruktion garanterar denna deterministiska algoritm att minst hälften av kanterna på den givna grafen skärs bort. (Detta gör algoritmen till en 0,5-approximationsalgoritm för Max-cut .)

Ett exempel på att använda pessimistiska uppskattningar

Följande exempel visar användningen av pessimistiska uppskattningar.

Turans sats

En av formuleringarna av Turans sats är följande:

Varje graf G = ( V , E ) innehåller en oberoende uppsättning av storlek åtminstone | V |/( D +1), där D = 2| E |/| V | är den genomsnittliga graden av grafen .

Probabilistiskt bevis för Turans sats

Betrakta följande slumpmässiga process för att konstruera en oberoende mängd S :

1. Ställ in setet S tom. 2. För varje hörn u från V i slumpmässig ordning: 3. Om ingen av grannarna till u är i S , lägg till u till S 4. Returnera S .

Det är tydligt att processen ger en självständig uppsättning. Varje vertex u som har beaktats före alla dess grannar kommer att läggas till S . Således, om d ( u ) betyder potensen av u , kommer sannolikheten att u adderas till S vara minst 1/( d ( u )+1). Enligt linjäriteten hos den matematiska förväntan är den förväntade storleken S inte mindre än

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

(Ojämlikheten ovan följer av att funktionen 1/( x +1) är konvex i x , så att vid minimering av vänster sida av uttrycket under summatecknet är värdena 2| E | om varje d ( u ) = D = 2| E |/| V |.) QED

Metoden för villkorade sannolikheter med hjälp av pessimistiska uppskattningar

I det här fallet har den slumpmässiga processen | v | steg. Varje steg tar hänsyn till en del som ännu inte anses vara hörn u och lägger till den till S om ingen av de angränsande hörnen har lagts till ännu. Låt slumpvariabeln Q vara lika med antalet hörn adderade till S . Beviset visar att E [ Q ] ≥ | V |/( D +1).

Vi kommer att ersätta varje slumpmässigt steg med ett deterministiskt steg som bevarar den villkorade förväntan på Q ovanför | V |/( D +1). Detta kommer att säkerställa ett framgångsrikt resultat, det vill säga ett resultat där den oberoende uppsättningen S har en storlek som inte är mindre än | V |/( D +1), vilket motsvarar gränsen i Turans sats.

Om det första steget är gjort, låt S ( t ) beteckna de hörn som lagts till innan. Låt R ( t ) beteckna de oövervägda hörnen som inte har några grannar i S ( t ) . Efter det första steget, det efterföljande resonemanget i det ursprungliga beviset att varje vertex w från R ( t ) med betingad sannolikhet minst 1/( d ( w )+1) läggs till S innebär att den villkorade förväntan på Q inte är mindre

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

Låt Q ( t ) beteckna ovanstående förväntade värde, som kallas den pessimistiska skattaren för det betingade medelvärdet.

Beviset visar att den pessimistiska estimatorn initialt är minst | V |/( D +1). (Det vill säga Q (0) ≥ | V |/( D +1).) Algoritmen gör att varje val undviker reduktionen av den pessimistiska estimatorn, det vill säga så att Q ( t +1) ≥ Q ( t ) för varje t . Eftersom den pessimistiska skattaren är en nedre gräns för det villkorliga medelvärdet, kommer detta att säkerställa att det villkorliga medelvärdet alltid är högre än | V |/( D +1), vilket i sin tur säkerställer att den villkorade förväntan om misslyckande är under 1.

Låt u vara det hörn som algoritmen betraktar i steg ( t + 1).

Om u redan har en granne i S läggs inte u till S och (efter kontroll av Q ( t ) ) förblir den pessimistiska skattaren oförändrad. Om u inte har några grannar i S läggs u till S .

Om u väljs slumpmässigt från de återstående hörnen är den förväntade tillväxten av den pessimistiska skattaren icke-negativ. [ Beräkning. Sannolikheten, på grund av valet av ett vertex från R ( t ) , att en given term 1/( d ( w )+1) faller utanför summan av den pessimistiska skattaren överstiger inte ( d ( w )+1) /| R ( t ) |, så att den förväntade minskningen i varje term inte överstiger 1/| R ( t ) |. Det finns R ( t ) termer i summan. Den förväntade minskningen av summan överstiger alltså inte 1. Samtidigt ökar storleken på S med 1.]

Det måste alltså finnas något val av u som gör att den pessimistiska skattaren inte minskar.

Algoritm för att maximera den pessimistiska uppskattningen

Algoritmen nedan väljer varje hörn u för att maximera den resulterande pessimistiska skattaren. Enligt ovanstående resonemang förhindrar detta den pessimistiska skattaren från att minska och garanterar en framgångsrik exit.

Nedan betyder N ( t ) ( u ) grannarna till u i R ( t ) (det vill säga grannar till u som inte är i S och inte har några grannar i S ).

1. Ställ in S tom. 2. Så länge det finns en oövervägd vertex u som inte har några grannar i S : 3. Lägg till ett hörn u till S som minimerar .

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

4. Återgå S .

Algoritmer som inte maximerar den pessimistiska uppskattningen

För att metoden med villkorade sannolikheter ska fungera räcker det att algoritmen inte minskar den pessimistiska uppskattningen (eller inte ökar den, beroende på situationen). Algoritmen maximerar (eller minimerar) inte nödvändigtvis den pessimistiska uppskattningen. Detta ger en viss frihet i utvecklingen av algoritmen.

1. Ställ in S tom. 2. Så länge det finns ett hörn u i en graf utan grannar i S : 3. Lägg till en sådan vertex u till S om u minimerar d ( u ) (initialgraden av u ). 4. Återgå S . 1. Ställ in S tom. 2. Medan den återstående grafen inte är tom: 3. Lägg till en vertex u till S om u har minsta graden i den återstående grafen. 4. Ta bort u och alla grannar till vertexet i grafen. 5. Återgå S .

Varje algoritm analyseras med samma pessimistiska estimator som tidigare. Vid varje steg i algoritmen är den totala ökningen av den pessimistiska skattaren

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

där N ( t ) ( u ) betyder grannarna till vertex u i den återstående grafen (det vill säga i R ( t ) ).

I den första algoritmen är ökningen icke-negativ på grund av valet av u ,

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

där d ( u ) är graden av vertex u i den ursprungliga grafen.

I den andra algoritmen är ökningen icke-negativ på grund av valet av u ,

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

där d′ ( u ) är graden av hörn u i den återstående grafen.

Se även

Litteratur

Paul Erdős , JL Selfridge. Om ett kombinatoriskt spel // Journal of Combinatorial Theory, Series A . - 1973. - T. 14 , nr. 3 . — S. 298–301 . - doi : 10.1016/0097-3165(73)90005-8 .
Joel H. Spencer. Tio föreläsningar om probabilistisk metod . - SIAM, 1987. - ISBN 978-0-89871-325-1 .
Prabhakar Raghavan. Probabilistisk konstruktion av deterministiska algoritmer: approximering av heltalsprogram // Journal of Computer and System Sciences . - 1988. - T. 37 , nr. 2 . — S. 130–143 . - doi : 10.1016/0022-0000(88)90003-7 .

Läsning för vidare läsning

Noga Alon , Joel Spencer. Den probabilistiska metoden . — Tredje. — Hoboken, NJ: John Wiley and Sons, 2008. — s. 250 och följande. (i 2:a upplagan, ISBN 9780471653981 ). - (Wiley-Interscience-serien i diskret matematik och optimering). — ISBN 978-0-470-17020-5 .

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

Länkar

The probabilistic method — method of conditional probabilities , blogginlägg av Neal E. Young, tillgänglig 2012-04-19.