582421 Satunnaisalgoritmit (kevät 2009) 1. kurssikoe 23.2., ratkaisuja (JK)
1. Katso Mitzenmacher & Upfal, s. 97.
2. OlkoonXi = 0, jos lokerooniei tule yhtään palloa, jaXi= 1muuten. OlkoonYjindikaattorimuuttuja tapahtumalle, että lokeropari numerojtulee peitetyksi; siisYj=X2j−1X2j.
(a) TapahtumalleYj= 0saadaan
Pr(Yj = 0) = Pr(X2j−1= 0taiX2j = 0)
= Pr(X2j−1= 0) + Pr(X2j= 0)−Pr(X2j−1= 0jaX2j = 0)
= (1−1/n)m+ (1−1/n)m−(1−2/n)m
= 2(1−1/n)m−(1−2/n)m.
Suurillanvoidaan approksimoida(1−x/n)n≈e−x, ja kunm=αn, saadaan Pr(Yj= 0)≈2e−α−e−2α.
Peitetyksi tulevien lokeroparien lukumäärä onY = Pn/2
j=1Yj, ja koska E[Yj] = Pr(Yj = 1), saadaan
E[Y] = n
2(2(1−1/n)m−(1−2/n)m)≈ n
2 1−2e−α+ e−2α
= n
2 1−e−α2 . (b) Käytetään Poisson-approksimaatiota. Olkoot siisZi riippumattomia Poisson(α)-jakautuneita sa-
tunnaismuuttujia, kuni= 1, . . . , n. OlkoonYˆjindikaattorimuuttuja tapahtumalle, että lokerojon Poisson-mallissa peitetty. SiisYj = 0tarkoittaa tapahtumaa tapahtumaa ”Z2j−1= 0taiZ2j = 0”.
Tämän todennäköisyys on
Pr( ˆYj= 0) = Pr(Z2j−1= 0) + Pr(Z2j= 0)−Pr(Z2j−1= 0) Pr(Z2j= 0)
= e−αα0
0! + e−αα0
0! −e−αα0
0! ·e−αα0 0!
= 2e−α−e−2α.
Siis Poisson-approksimaatiossa todennäköisyys saada lokerojpeitetyksi on Pr( ˆYj= 1) = 1−2e−α−e−2α= 1−e−α2
.
Kun sijoitetaan parametrilleαarvo, joka antaa kohdan (a) approksimatiiviseksi odotusarvoksin/4, saadaan
Pr( ˆYj) = 1/2.
Siis muuttujatYˆjovat riippumattomiaBernoulli(1/2)-jakautuneita muuttujia. Kun merkitäänYˆ = Pn/2
j=1Yjjaµ=E[ ˆY] =n/4, niin tunnetusta Chernoffin rajasta (Theorem 4.5) saadaan Pr( ˆY ≤n/8) = Pr( ˆY ≤(1−1/2)µ)≤exp(−µ(1/2)2/2) = exp(−n/32).
Tapahtuma ”Yˆ ≤n/8” on Poisson-mallin vastine alkuperäisen mallin tapahtumalle ”Y ≤n/8”, joten tunnetun tuloksen (Corollary 5.9) mukaan
Pr(Y < n/8)≤e√
mPr( ˆY ≤n/8)≤αne1−n/32=O(n−c) itse asiassa millä tahansa vakiollac >0.
3. (a) Väritetään verkon kaaret toisistaan riippumatta kukin todennäköisyydellä1/2punaiseksi (”P”) ja todennäköisyydellä1/2siniseksi (”S”). Täydellisessänsolmun verkossa on n3
kolmiota. Nume- roidaan nämä mielivaltaisesti. OlkoonXiindikaattorimuuttuja tapahtumalle, että kolmio numeroi tulee monokromaattiseksi, jaX =P
iXi. KoskaPr(Xi) = (1/2)−2 = 1/4, niinE[X] = 14 n 3
. Tunnetun tuloksen (kirjan Lemma 6.2) mukaan nytPr(X≤ 14
n 3
)>0. Siis väritys on mahdollista tehdä siten, että saadaan korkeintaan14 n3
monokromaattista kolmiota.
(b) Muodostetaan verkon kaarillee1, . . . , emväritys, jossa kaareneiväricion joko punainen (”P”) tai sininen (”S”). Käytetään ehdollisen odotusarvon menetelmää kohdan (a) tuloksen muuntamiseksi deterministiseksi algoritmiksi. Algoritmi kiinnittää väritci yksi kerrallaan. Tarkastellaan värinci
kiinnittämistä ja käytetään kaikillaj < imerkintääφjtapahtumallecj= Ptaicj = Ssen mukaan, kumpi väri kaarellejon kiinnitetty. Koska
E[X |φ1, . . . , φi−1] = 1
2E[X |φ1, . . . , φi−1, ci= P] +1
2E[X |φ1, . . . , φi−1, ci= S], niin
min{E[X |φ1, . . . , φi−1, ci= P],E[X |φ1, . . . , φi−1, ci= S]} ≤E[X |φ1, . . . , φi−1].
Merkitään nyt
∆ =E[X |φ1, . . . , φi−1, ci= P]−E[X|φ1, . . . , φi−1, ci= S].
Algoritmi valitsee nytci= P, jos∆≤0, jaci= S, jos∆>0. Siiscivalitaan niin, että E[X |φ1, . . . , φi−1, φi]≤E[X |φ1, . . . , φi−1].
Koska tapauksessai = 0pätee kohdan (a) perusteella E[X] ≤ 14 n 3
, algoritmi pitää voimassa invariantin
E[X |φ1, . . . , φi]≤ 1 4
n 3
. Erityisesti kun kaikkimväriä on kiinnitetty, pätee
E[X |φ1, . . . , φm]≤ 1 4
n 3
.
Koska tässä ei ole enää mitään satunnaista, jonoφ1, . . . , φmantaa halutun värityksen.
Tarkastellaan vielä algoritmin aikavaativuutta. Selvästi aikavaativuutta dominoi arvon∆laskemi- nenmkertaa värienc1, . . . , cmkiinnittämiseksi. Tarkastellaan nyt jollakiniarvon∆laskemista.
Kunk= 1, . . . , n3
, merkitään
∆k =E[Xk |φ1, . . . , φi−1, ci= P]−E[Xk|φ1, . . . , φi−1, ci = S].
Siis∆ = P
k∆k. Jos kaariei ei kuulu kolmioon numerok, niin selvästi∆i = 0. Tarkastellaan tilannetta, kun kaariikuuluu kolmioonk.
• Jos värityksetφ1, . . . , φi−1eivät ole kiinnittäneet yhtään kolmion numerokkaarta, niin∆i= 0.
• Jos värityksetφ1, . . . , φi−1ovat kiinnittäneet kolmion numerokkaarista yhden punaiseksi ja yhden siniseksi, niin∆i= 0.
• Jos värityksetφ1, . . . , φi−1ovat kiinnittäneet kolmion numerokkaarista yhden punaiseksi ja jättäneet kaksi kaarta vapaaksi, niin∆k = 1/2.
• Jos väritykset φ1, . . . , φi−1 ovat kiinnittäneet kolmion numerok kaarista yhden siniseksi ja jättäneet kaksi kaarta vapaaksi, niin∆k =−1/2.
• Jos värityksetφ1, . . . , φi−1ovat kiinnittäneet kolmion numerokkaksi kaarta punaiseksi, niin
∆k= 1.
2
• Jos värityksetφ1, . . . , φi−1ovat kiinnittäneet kolmion numero kkaksi kaarta siniseksi, niin
∆k=−1.
Jos kiinnitettävänä on kaarenei = (u, v)väritys, niin kaikki kaareneisisältävät kolmiot saadaan tarkastelemalla kaaria(u, w)ja(v, w)kaikilla solmuillaw. Siis∆saadaan lasketuksi ajassaO(n).
Koskam=O(n2), algoritmin aikavaativuudeksi tuleeO(n3).
3
