582421 Satunnaisalgoritmit
kev¨at 2009 Jyrki Kivinen
Kurssin asema opetuksessa
• laajuus 8 op
• kelpaa syvent¨aviin opintoihin algoritmien ja koneoppimisen (ja vanhalla algoritmien) erikoistumislinjalla.
• esitietoina perustiedot todenn¨ak¨oisyyslaskennasta sek¨a algoritmien suunnittelusta ja analyysista
• aiheena todenn¨ak¨oisyyslaskennan soveltaminen algoritmien suunnittelussa ja analyysissa
• todenn¨ak¨oisyyslaskennan sovelluksia koneoppimiseen k¨asitell¨a¨an
lukuisilla muilla erikoistumislinjan kursseilla (Johdatus koneoppimiseen, Todenn¨ak¨oisyysmallit, Unsupervised Machine Learning jne.)
• todenn¨ak¨oisyyslaskennan teoriaa k¨asitell¨a¨an matematiikan kursseilla
• todenn¨ak¨oisyyslaskennan kannalta soveltavaa, tietojenk¨asittetieteen
Kurssin suorittaminen ja arvostelu
Maksimipistem¨a¨ar¨a 60 pistett¨a:
• kaksi kurssikoetta 24 + 24 = 48 pistett¨a
• laskuharjoitukset 12 pistett¨a
L¨apip¨a¨asyraja noin 30 pistett¨a, arvosanan 5/5 raja noin 50 pistett¨a.
Laskuharjoitukset alkavat toisella luentoviikolla. Harjoitusteht¨avien ratkaisut palautetaan kirjallisesti ennen laskuharjoitustilaisuutta. Menettelyn
yksityiskohdat ja m¨a¨ar¨aajat ilmoitetaan kurssin verkkosivulla. Kunkin teht¨av¨an ratkaisu arvostellaan asteikolla 0–3:
1 jotain j¨arkev¨a¨a yrityst¨a
2 oikeansuuntainen melko pitk¨alle viety yritys 3 silm¨am¨a¨ar¨aisesti suunnilleen oikea ratkaisu
Laskuharjoitusteht¨avien kokonaispisteet skaalataan kurssipisteiksi seuraavasti:
• 0 % maksimipisteist¨a antaa 0 pistett¨a
• 80 % (tai yli) maksimipisteist¨a antaa 12 pistett¨a
Oppimateriaali
Opiskelijoilla oletetaan olevan k¨ayt¨oss¨a¨an kurssikirja
M. Mitzenmacher, E. Upfal: Probability and Computing.
Viittaukset kurssikirjaan n¨aiss¨a muistiinpanoissa on esitetty tyyliin [M&U Thm 3.2].
Luentomateriaali ilmestyy kurssin kotisivulle, mutta ei ole tarkoitettu itseopiskeluun (yksityiskohtia sivuutetaan jne.).
My¨os laskuharjoitusteht¨avin¨a k¨aytet¨a¨an kirjan harjoitusteht¨avi¨a.
Miksi satunnaisuutta
Satunnaisuus on t¨arke¨a v¨aline luonnonilmi¨oiden ym. mallintamisessa.
Satunnaisuutta tarvitaan algoritmien suunnittelussa ja analyysissa:
• satunnaisalgoritmit (randomized): algoritmin toiminta samalla sy¨otteell¨a vaihtelee riippuen algoritmin sis¨aisest¨a satunnaisuudesta (”rahanheitoista”)
• algoritmin toimintaymp¨arist¨o voi olla satunnainen (keskim¨a¨ar¨aisen tapauksen (average case) analyysi, tietoliikenne, . . . )
Todenn¨ak¨oisyyslaskenta on voimakas yleisty¨okalu kaikkiin t¨allaisiin tilanteisiin.
Satunnaisuuden avulla voidaan saada algoritmi, joka on deterministiseen algoritmiin verrattuna
• nopeampi tai muistinkulutukseltaan pienempi tai
• helpompi toteuttaa.
Perustekniikoita/tilanteita:
• satunnaisotanta, Monte Carlo -menetelm¨at
• satunnaishaku, simuloitu j¨a¨ahdytys
• sormenj¨alkitekniikat.
Tietyiss¨a tilanteissa satunnaisuus on v¨altt¨am¨at¨ont¨a ett¨a saadaan ylip¨a¨ans¨a hyv¨aksytt¨av¨a ratkaisu:
• vastustajan h¨am¨a¨aminen (kryptografia, pelit)
• hajautetut j¨arjestelm¨at: kuorman tasapainotus, johtajan valinta jne.
Satunnaistamalla voidaan v¨ahent¨a¨a algoritmin herkkyytt¨a “h¨airi¨oille”:
Tyypillisi¨ a kysymyksi¨ a
Yleens¨a satunnaisalgoritmit antavat jollain todenn¨ak¨oisyydell¨a v¨a¨ar¨an vastauksen.
• jos vastaus on kyll¨a/ei: mik¨a on virhetodenn¨ak¨oisyys
• jos vastaus on numeerinen tms.: mik¨a on suuren virheen todenn¨ak¨oisyys.
Jotkin satunnaisalgoritmit (ns. Las Vegas -algoritmit) antavat aina oikean vastauksen, mutta suoritusaika on satunnainen.
• Mik¨a on suoritusajan odotusarvo?
• Mik¨a on todenn¨ak¨oisyys, ett¨a suoritusaika ylitt¨a¨a tietyn rajan?
Kurssin sis¨ alt¨ oluonnos
1. Todenn¨ak¨oisyys (kertausta)
2. Diskreetit satunnaismuuttujat (kertausta) 3. Satunnaismuuttujan momentit
4. Chernoffin rajat 5. Pallot ja uurnat
6. ”Probabilistinen menetelm¨a”
7. Markovin ketjut
8. Jatkuvat satunnaismuuttujat, Poisson-prosessit 9. Monte Carlo -menetelm¨at
1. Todenn¨ ak¨ oisyys
Olkoon Ω mielivaltainen joukko ja F ⊆ P(Ω) jokin kokoelma sen
osajoukkoja. (T¨ass¨a P(Ω) on siis joukon Ω potenssijoukko.) Kuvaus Pr : F → R on todenn¨ak¨oisyysmitta [M&U Def. 1.2], jos
1. Pr(E) ≥ 0 kaikilla E ∈ F (positiivisuus), 2. Pr(Ω) = 1 ja
3. jos E1, E2, E3, . . . on jono erillisi¨a joukkoja (eli Ei ∩ Ej = ∅ kun i 6= j) ja Ei ∈ F kaikilla i, niin
Pr
[∞
i=1
Ei
!
= X∞
i=1
Pr(Ei) (numeroituva additiivisuus).
Jotta todenn¨ak¨oisyysmitalle juuri asetetut ehdot ylip¨a¨ans¨a olisivat mielekk¨ait¨a, sen m¨a¨arittelyjoukolla F t¨aytyy olla tiettyj¨a
sulkeumaominaisuuksia.
Osajoukkokokoelma F ⊆ P(Ω) on σ-algebra, jos 1. Ω ∈ F
2. jos A ∈ F niin A ∈ F, miss¨a A = Ω − A
3. jos jonolla A1, A2, A3, . . . p¨atee Ai ∈ F kaikilla i ∈ {1,2,3, . . .}, niin [∞
i=1
Ai ∈ F.
Huom. t¨ass¨a ei oleteta mit¨a¨an joukkoperheen {Ai | i ∈ I } yhdisteest¨a
∪i∈IAi, jos I on ylinumeroituva.
Todenn¨ak¨oisyysavaruus on nyt kolmikko (Ω,F,Pr), miss¨a 1. otosavaruus Ω on mielivaltainen joukko
2. F ⊆ P(Ω) on σ-algebra perusjoukkona Ω 3. Pr : F → R on todenn¨ak¨oisyysmitta.
Otosavaruutta kutsutaan my¨os perusjoukoksi.
Perusjoukon Ω osajoukot E ⊆ Ω ovat tapahtumia ja joukot E ∈ F erityisesti alkeistapahtumia eli mitallisia joukkoja.
Jos φ on jokin perusjoukon alkioiden ominaisuus, merkit¨a¨an lyhyesti Pr(φ(x)) = Pr({x ∈ Ω | φ(x)}); esim. Pr(g(x) = 3) tarkoittaa
todenn¨ak¨oisyytt¨a Pr({x ∈ Ω | g(x) = 3}).
Esimerkki 1.1: Jos Ω on ¨a¨arellinen, |Ω| = n ∈ N, niin joukon Ω symmetrinen (eli tasainen) todenn¨ak¨oisyysavaruus on kolmikko (Ω,P(Ω),Pr), miss¨a Pr(E) = |E|/n kaikilla E ⊆ Ω.
Yleisemmin jos todenn¨ak¨oisyysavaruus on muotoa (Ω,P(Ω),Pr), miss¨a Ω on
¨
a¨arellinen tai numeroituvasti ¨a¨aret¨on, sit¨a sanotaan diskreetiksi. Diskretti todenn¨ak¨oisyysavaruus voidaan m¨a¨aritell¨a antamalla kaikki yksitt¨aisten alkioiden todenn¨ak¨oisyydet Pr({x}), x ∈ Ω. 2
Jatkossa tarvitaan l¨ahinn¨a diskreettej¨a tn-avaruuksia. Sen takia j¨at¨amme yleens¨a my¨os mainitsematta muotoa ”jos E ∈ F” olevia oletuksia (joiden pit¨aisi muutenkin olla yleens¨a asiayhteydest¨a selvi¨a).
Toisinaan on kuitenkin hy¨odyllist¨a tarkastella numeroituvassakin Ω muitakin σ-algebroja kuin P(Ω).
Esimerkki 1.2: Olkoon Ω = R ja F suppein σ-algebra, joka sis¨alt¨a¨a kaikki suljetut v¨alit [a, b], a, b ∈ R. T¨am¨an σ-algebran alkioita sanotaan
Borel-joukoiksi.
M¨a¨aritell¨a¨an v¨alin [a, b] todenn¨ak¨oisyydeksi v¨alin [a, b] ∩[0,1] pituus. Muiden Borel-joukkojen todenn¨ak¨oisyydet seuraavat todenn¨ak¨oisyysmitan
m¨a¨aritelm¨ast¨a. T¨am¨a on osav¨alin [0,1] symmetrinen todenn¨ak¨oisyysmitta.
Huom. kaikilla x ∈ R p¨atee Pr({x}) = 0, joten mink¨a tahansa numeroituvan joukon todenn¨ak¨oisyys on 0. T¨ast¨a ei seuraa mit¨a¨an ylinumeroituvien
joukkojen todenn¨ak¨oisyyksille. 2
Tuntuisi ehk¨a yksinkertaisemmalta, jos t¨ass¨a voitaisiin valita F = P(R), eli kaikkien reaalilukujoukkojen todenn¨ak¨oisyydet olisivat m¨a¨ariteltyj¨a. T¨am¨a ei kuitenkaan ole mahdollista: jos em. funktio Pr yritet¨a¨an laajentaa koko
joukkoon P(R), niin kaikkia todenn¨ak¨oisyysmitan ehtoja ei saada pysym¨a¨an voimassa. K¨ayt¨ann¨oss¨a ei juuri ole tarvetta muille kuin Borel-joukoille.
Yhdisteen todenn¨ ak¨ oisyys
M¨a¨aritelmist¨a seuraa suoraan, ett¨a mille tahansa kahdelle alkeistapahtumalle p¨atee
Pr(E ∪ F) = Pr(E) + Pr(F) − Pr(E ∩ F).
Samoin mille tahansa numeroituvalle I ja jonolle alkeistapahtumia Ei, i ∈ I p¨atee
Pr [
i∈I
Ei
!
≤ X
i∈I
Pr(Ei).
(”union bound”; [M&U Lemma 1.2]). T¨am¨a ep¨ayht¨al¨o on eritt¨ain yleisk¨aytt¨oinen, mutta toisinaan turhan l¨oys¨a.
Kun |I| = n ∈ N, niin yhdisteen tarkka todenn¨ak¨oisyys saadaan kaavasta Pr [
Ei
!
=
n
X(−1)k+1 X
Pr
\ Ej
Laskemalla edellisen kaavan summaa vain johonkin rajaan k < n saakkaa saadaan vuorotellen yl¨a- ja alarajoja:
Jos ℓ on pariton, niin Pr [
i∈I
Ei
!
≤
ℓ
X
k=1
(−1)k+1 X
J⊆I,|J|=k
Pr
\
j∈J
Ej
.
Jos ℓ on parillinen, niin Pr [
i∈I
Ei
!
≥
ℓ
X
k=1
(−1)k+1 X
J⊆I,|J|=k
Pr
\
j∈J
Ej
(Bonferronin ep¨ayht¨al¨ot).
Riippumattomuus
Kaksi alkeistapahtumaa E ja F ovat riippumattomia [M&U Def. 1.3], jos Pr(E ∩ F) = Pr(E) Pr(F).
Yleisemmin alkeistapahtumat E1, . . . , Ek ovat riippumattomia, jos kaikilla I ⊆ {1, . . . , k} p¨atee
Pr \
i∈I
Ei
!
= Y
i∈I
Pr(Ei).
Alkeistapahtumat E1, . . . , Ek ovat pareittain riippumattomia, jos kaikilla i 6= j alkeistapahtumat Ei ja Ej ovat riippumattomia
Huom. riippumattomuus on aidosti vahvempi vaatimus kuin pareittainen riippumattomuus.
Jos Pr(F) > 0, niin tapahtuman E todenn¨ak¨oisyys ehdolla F on Pr(E | F) = Pr(E ∩F)
.
Kahden todenn¨ak¨oisyysavaruuden (Ω1,F1,Pr1) ja (Ω2,F2,Pr2) tulo on (Ω1,F1,Pr1) × (Ω2,F2,Pr2) = (Ω1 × Ω2,F1 × F2,Pr1×Pr2) miss¨a
F1 × F2 = {E × F | E ∈ F1, F ∈ F2 } ja
(Pr1×Pr2)(E × F) = Pr1(E) × Pr2(F).
T¨arke¨a erikoistapaus on tn-avaruuden n-kertainen tulo itsens¨a kanssa (Ω,F,Pr)n = (Ωn,Fn,Prn). Jos alkuperainen tn-avaruus esitt¨a¨a jotain
satunnaiskoetta, sen n-kertainen tulo itsens¨a kanssa esitt¨a¨a n riippumatonta toistoa samasta kokesta. T¨all¨oin usein my¨os tulomitasta Prn k¨aytet¨a¨an
yksinkertaisesti (ja ep¨at¨asm¨allisesti) merkint¨a¨a Pr.
Esimerkki 1.3: Oletetaan annetuksi kaksi aliohjelmaa F ja G, jotka laskevat kokonaislukufunktiot f ja g. Funktioista f ja g tiedet¨a¨an vain, ett¨a ne ovat korkeintaan d-asteisia polynomeja. Teht¨av¨an¨a on p¨a¨atell¨a, p¨ateek¨o f = g.
Jos f = g, niin f(x) − g(x) = 0 kaikilla x.
Jos f 6= g, niin f − g on korkeintaan d-asteinen polynomi joka ei ole
identtisesti nolla, joten f(x) − g(x) = 0 p¨atee korkeintaan d arvolla x ∈ N. Erityisesti joukossa {1, . . . , rd} mill¨a tahansa r ∈ N on ainakin (r − 1)d alkiota x, joilla f(x) − g(x) 6= 0.
Saadaan seuraava perusalgoritmi:
1. Valitse satunnainen x ∈ {1, . . . , rd}. 2. Jos f(x) − g(x) 6= 0, tulosta ”eri”.
3. Muuten tulosta ”samat”.
Edell¨a olevan perusteella
• jos f = g, algoritmi tulostaa aina ”samat” ja
• jos f 6= g, algoritmi tulostaa ”eri” ainakin todenn¨ak¨oisyydell¨a (r − 1)d/(rd) = 1 − 1/r.
Algoritmilla on siis yksipuolinen virhetodenn¨ak¨oisyys korkeintaan 1/r.
Tehd¨a¨an nyt k riippumatonta toistokoetta seuraavasti:
1. Valitse toisistaan riippumatta satunnaiset x1, . . . , xk joukosta {1, . . . , rd}.
2. Jos f(xi) − g(xi) 6= 0 ainakin yhdell¨a i, tulosta ”eri”.
3. Muuten tulosta ”sama”.
Jos f = g, saadaan taas aina vastaus ”sama”. Jos f 6= g ja vastaus on
”sama”, on k kertaa toisistaan riippumatta sattunut tapahtuma, jonka todenn¨ak¨oisyys on kork. 1/r. T¨am¨an todenn¨ak¨oisyys on siis korkeintaan (1/r)k.
Toistokokeita suorittamalla virhetodenn¨ak¨oisyys saadaan siis eksponentiaalista vauhtia kohti nollaa. 2
Kokonaistodenn¨ ak¨ oisyys
[M&U Thm. 1.6]Olkoot Ei, i ∈ I, numeroituva kokoelma erillisi¨a tapahtumia s.e. ∪i∈IEi = Ω.
Suoraan m¨a¨aritelmist¨a saadaan kokonaistodenn¨ak¨oisyydelle kaava Pr(B) = X
i∈I
Pr(B ∩Ei) = X
i∈I
Pr(B | Ei) Pr(Ei). T¨at¨a voidaan soveltaa esim. viivytetyn valinnan tekniikalla:
Halutaan osoittaa esim. Pr(x ∈ B) ≤ ǫ.
Jaetaan x sopivalla tavalla kahteen komponenttiin x = (x1, x2). Ajatellaan, ett¨a ”ensin” valitaan x1, ja ”vasta my¨ohemmin” x2.
Osoitetaan, ett¨a miten tahansa x1 valitaankin, niin aina todenn¨ak¨oisyys valita x2 siten, ett¨a (x1, x2) ∈ B p¨atee, on korkeintaan ǫ.
Sovelletaan kokonaistodenn¨ak¨oisyyden kaavaa valitsemalla I = komponentin x1 arvojoukko Ei = {(x1, x2) | x1 = i}.
Esimerkki 1.4: [M&U Thm. 1.4] On annettu n × n-matriisit A, B ja C. Halutaan tarkistaa, p¨ateek¨o AB = C, ilman ett¨a tarvitsee laskea
matriisituloa AB.
Menetell¨a¨an samaan tapaan kuin edellisess¨a esimerkiss¨a:
1. Valitse satunnainen r ∈ {0,1}n. 2. Jos ABr 6= Cr, tulosta ”erisuuret”.
3. Muuten tulosta ”yht¨asuuret”.
Olkoon D = AB − C. V¨aitet¨a¨an, ett¨a jos D ei ole nollamatriisi, niin Dr 6= 0 p¨atee ainakin todenn¨ak¨oisyydell¨a 1/2.
Merkit¨a¨an D = (dij). Oletetaan, ett¨a D 6= 0; olkoon dpq 6= 0.
Jos Dr = 0, p¨atee siis erityisesti
n
X
j=1
dpjrj = 0, mist¨a voidaan ratkaista
rq = −d−pq1X
j6=q
dpjrj.
Ajatellaan ensin valituksi r′ = (r1, . . . , rq−1, rq+1, . . . , rn) ja tarkastellaan sitten puuttuvan komponentin rq valintaa. Koska vektorin r′ valinta kiinnitt¨a¨a
lausekkeelle
−d−pq1 X
j6=q
dpjrj
jonkin arvon v, niin todenn¨ak¨oisyys tapahtumalle rq = v on korkeintaan 1/2 (koska rq ∈ {0,1}). Lyk¨atyn valinnan periaatteella siis n¨ahd¨a¨an, ett¨a
Pr(Dr = 0) ≤ 1 2.
Bayesin s¨ a¨ ant¨ o
[M&U Thm. 1.7]Edelleen suoraan m¨a¨aritelmist¨a saadaan Pr(Ej | B) = Pr(Ej ∩ B)
Pr(B) = Pr(B | Ej) Pr(Ej) P
iPr(B | Ei) Pr(Ei) miss¨a j¨alleen (Ei) ovat erillisi¨a.
Tyypillinen tulkinta on, ett¨a kaavan mukaan p¨aivitet¨a¨an uskomuksia kun on saatu uutta dataa:
• Tapahtumat Ej esitt¨av¨at erilaisia toisensa poissulkevia hypoteeseja tyyliin Ei = ”teoria numero i on tosi”.
• Tapahtuma B kuvaa jotain havaintoa, mittausdataa tms.
• Pr(Ej) on a priori -todenn¨ak¨oisyys, joka mittaa uskoamme hypoteesiin Ej ennen kuin mit¨a¨an dataa on havaittu.
• Pr(B | Ej) mittaa, kuinka hyvin hypoteesi Ej ”selitt¨a¨a” datan B.
Esimerkki 1.5: On annettu kolme kolikkoa, joista kaksi on tasapainoisia ja yhdell¨a (emme tied¨a mill¨a) kruunan todenn¨ak¨oisyys on 2/3.
Laitamme kolikot satunnaiseen j¨arjestykseen ja heit¨amme niit¨a. Saamme tulokset (1: kruuna, 2: kruuna, 3: klaava).
Mill¨a todenn¨ak¨oisyydell¨a kolikko 1 on ep¨atasapainoinen?
Soveltamalla Bayesin kaavaa saadaan vastaus 2/5. 2
Huom. Kaavan nimitt¨aj¨a ei riipu hypoteesista Ej. Jos halutaan vain verrata eri hypoteesien a posteriori -todenn¨ak¨oisyyksi, voidaan unohtaa vakio Pr(B) ja kirjoittaa
Pr(Ej | B) ∝ Pr(B | Ej) Pr(Ej).
Toisaalta monissa koneoppimissovelluksissa nimenomaan tekij¨an Pr(B) laskeminen on kriittinen laskennallinen ongelma.
Satunnainen minimileikkausalgoritmi
[M&U luku 1.4]Olkoon G = (V, E) yhten¨ainen suuntaamaton moniverkko (multigraph).
Tavallisesta verkosta poiketen moniverkossa kahden solmun v¨alill¨a saa olla useita kaaria.
Kaarijoukko C ⊆ E on (moni)verkon leikkaus, jos (V, E − C) ei ole yhten¨ainen. Minimileikkaus on pienimm¨an mahdollisen m¨a¨ar¨an kaaria sis¨alt¨av¨a leikkaus.
Kaaren (u, v) kutistaminen korvaa solmut u ja v yhdell¨a uudella solmulla.
Kaari (u, v) (tai kaikki n¨am¨a kaaret, jos niit¨a on useita) poistuvat verkosta.
Muut kaaret s¨ailyv¨at, ja solmuihin u tai v liittyv¨at kaaret liitet¨a¨an uuteen niit¨a korvaavaan solmuun.
Jos C on leikkaus alkuper¨aisess¨a verkossa ja (u, v) 6∈ C, niin C on leikkaus my¨os kutistamisen j¨alkeen. Toisaalta miss¨a¨an tapauksessa kutistaminen ei
Tarkastellaan seuraavaa algoritmia:
1. Valitse verkosta jokin kaari (u, v) siten, ett¨a kunkin kaaren todenn¨ak¨oisyys tulla valituksi on sama.
2. Kutista kaari (u, v).
3. Jos verkossa on v¨ahint¨a¨an kolme solmua, palaa kohtaan 1.
4. Muuten tulosta verkossa j¨aljell¨a olevat kaaret.
Olkoon C jokin minimileikkaus. Edell¨a esitetyst¨a seuraa, ett¨a jos algoritmi ei koskaan valitse joukon C kaarta kutistettavaksi, se tuottaa oikean
lopputuloksen.
Mik¨a on t¨am¨an suotuisan tapauksen todenn¨ak¨oisyys?
Olkoon Ei tapahtuma, ett¨a iteraatiossa i kutistettava kaari ei ole joukossa C, ja Fi = ∩ij=1Ei. Haluamme siis alarajan todenn¨ak¨oisyydelle Pr(Fn−2), miss¨a n = |V |.
Olkoon k = |C| minimileikkauksen koko. T¨all¨oin erityisesti jokaisen solmun aste on ainakin k, joten verkossa on v¨ahint¨a¨an kn/2 kaarta. Siis
Pr(E1) = |E| − |C|
|E| ≥ 1 − k
nk/2 = 1 − 2 n.
Yleisemmin jos vaiheeseen i − 1 asti on mennyt hyvin, niin C on edelleen verkon minimileikkaus, koska kutistaminen ei luo uusia leikkauksia. Solmujen m¨a¨ar¨a on kuitenkin v¨ahentynyt, joten ¨askeinen argumentti antaa
Pr(Ei | Fi−1) ≥ 1 − 2
n − i + 1.
Saadaan
Pr(Fn−2) = Pr(En−2 ∩Fn−3)
= Pr(En−2 | Fn−3) Pr(Fn−3)
= . . .
= Pr(En−2 | Fn−3) Pr(En−3 | Fn−4). . .Pr(E2 | F1) Pr(F1)
≥
n−2
Y
i=1
1 − 2
n − i+ 1
=
n − 2 n
n − 3 n − 1
. . .
3 5
2 4
1 3
= 2
n(n − 1).
Joka tapauksessa algoritmi siis tuottaa leikkauksen, ja ainakin todenn¨ak¨oisyydell¨a 2/(n(n − 1)) minimileikkauksen.
Toistetaan algoritmia m kertaa ja valitaan saaduista leikkauksista pienin.
Todenn¨ak¨oisyys, ett¨a ei saatu minimileikkausta, on korkeintaan
1 − 2
n(n − 1) m
≤ exp
− 2m n(n − 1)
miss¨a on arvioitu 1 − x ≤ e−x.
Jos valitaan esim. m = n(n − 1) lnn, rajaksi virhetodenn¨ak¨oisyydelle tulee 1/n2. 2
2. Satunnaismuuttujat
Olkoon (Ω,F,Pr) todenn¨ak¨oisyysavaruus. Reaaliarvoinen funktio X: Ω → R on satunnaismuuttuja, jos {s ∈ Ω | X(s) ≤ a} ∈ F kaikilla a ∈ R.
Satunnaismuuttuja on diskreetti, jos sen arvojoukko on numeroituva.
My¨ohemmin tarkastelemme my¨os jatkuvia satunnaismuuttujia, joiden arvoalue on ylinumeroituva. T¨ass¨a luvussa kuitenkin oletataan aina, ett¨a tarkasteltavat satunnaismuuttujat ovat diskreettej¨a.
Yleens¨a todenn¨ak¨oisyytt¨a Pr({s ∈ Ω | X(s) = a}) merkit¨a¨an lyhyesti Pr(X = a) jne. Diskreetin satunnaismuuttujan jakauma (joka sis¨alt¨a¨a kaiken, mit¨a satunnaismuuttujasta voisi haluta k¨ayt¨ann¨oss¨a tiet¨a¨a) tulee m¨a¨ar¨atyksi, kun annetaan luvut Pr(X = a) kaikilla a ∈ R.
Jono satunnaismuuttujia (X1, . . . , Xk) on riippumaton, jos kaikilla I ⊆ {1, . . . , k} ja kaikilla x1, . . . , xk ∈ R p¨atee
Pr(∩i∈I(Xi = xi)) = Y
i∈I
Pr(Xi = xi).
Olkoon V satunnaismuuttujan X arvoalue. Jos summa P
x∈V |x|Pr(X = x) suppenee, niin satunnaismuuttujan odotusarvo on
E[X] = X
x∈V
xPr(X = x).
Muuten odotusarvo ei ole m¨a¨aritelty, mit¨a usein merkit¨a¨an E[X] = ∞.
Odotusarvo on lineaarinen [M&U Thm. 2.1]: kaikilla a, b ∈ R ja satunnaismuuttujilla X, Y p¨atee
E[aX + bY] = aE[X] +bE[Y ].
Lineaarisuus ei suoraan yleisty ¨a¨arett¨omiin summauksiin. Milloin p¨atee E
" ∞ X
i=1
Xi
#
= X∞
i=1
E[Xi]
on ei-triviaali ongelma. Er¨as riitt¨av¨a ehto on, ett¨a kaikki odotusarvot E[|Xi|] ovat m¨a¨ariteltyj¨a ja P∞
i=1E[|Xi|] suppenee.
Jos X ja Y ovat riippumattomia, p¨atee lis¨aksi E[XY ] = E[X]E[Y ].
Jensenin ep¨ ayht¨ al¨ o
[M&U luku 2.1.2]M¨a¨aritelmist¨a seuraa suoraan t¨arke¨a perusominaisuus E[X2] ≥ (E[X])2.
(Yht¨asuuruus ei yleens¨a p¨ade, koska X ei ole riippumaton itsest¨a¨an.) T¨am¨a on erikoistapaus Jensenin ep¨ayht¨al¨ost¨a.
Funktio f : [a, b] → R on konveksi jos
f(λx1 + (1 − λ)x2) ≤ λf(x1) + (1 − λ)f(x2) kaikilla a ≤ x1, x2 ≤ b ja 0 ≤ λ ≤ 1.
Jos f on kahdesti derivoituva, se on konveksi joss f′′(x) ≥ 0 kaikilla x.
Lause 3.1 [Jensen]: Jos f on konveksi, niin E[f(X)] ≥ f(E[X]) kaikilla satunnaismuuttujilla X. 2
Binomijakauma
[M&U luku 2.2]Satunnaismuuttuja Y noudattaa Bernoulli-jakaumaa parametrilla p jos Pr(Y = 1) = p ja Pr(Y = 0) = 1 − p.
Selv¨asti E[Y ] = p.
Satunnaismuuttuja X noudattaa binomijakaumaa parametreilla n ja p, merkit¨a¨an X ∼ Bin(n, p), jos se on n riippumattoman Bernoulli-muuttujan summa:
Pr(X = j) = n j
pj(1 − p)n−j, j = 0, . . . , n.
Odotusarvon lineaarisuudesta seuraa
E[X] = np.
Ehdollinen odotusarvo
[M&U luku 2.3]Kun Y ja Z ovat satunnaismuuttujia, Y :n arvojoukko on V , ja z ∈ R, merkit¨a¨an
E[Y | Z = z] = X
y∈V
yPr(Y = y | Z = z).
Esimerkki 2.2: Olkoot X1 ja X2 riippumattomien nopanheittojen tulokset ja X = X1 + X2. T¨all¨oin E[X | X1 = 3] = 61
2 ja E[X1 | X = 4] = 1 · 1
3 + 2 · 1
3 + 3 · 1
3 = 2.
2 Kaikille satunnaismuuttujille X ja Y p¨atee
E[X] = X
y∈V
E[X | Y = y] Pr(Y = y)
Ehdollinen odotusarvo E[Y | Z] on satunnaismuuttuja joka m¨a¨aritell¨a¨an seuraavasti:
Olkoot Y ja Z satunnaismuuttujia otosavaruudessa Ω (eli funktioita Ω → R).
Nyt E[Y | Z] : Ω → R on satunnaismuuttuja, jolla
E[Y | Z](ω) = E[Y | Z = Z(ω)]
kaikilla ω ∈ Ω.
Esimerkki 2.3: Olkoon taas X = X1 + X2, miss¨a X1 ja X2 ovat riippumattomia nopanheittoja. Nyt
E[X | X1] = X1 + 31 2.
2 Ehdollinen odotusarvo noudattaa tavallisen odotusarvon perusominaisuuksia:
E[X1 + X2 | Z] = E[X1 | Z] + E[X2 | Z] jne. Lis¨aksi E[Y ] = E[E[Y | Z]].
Esimerkki 2.4: Haarautuvat prosessit.
Tarkastellaan tilannetta, jossa prosessi suorittaa jotain tietty¨a aliohjelmaa.
T¨am¨a aliohjelma voi puolestaan luoda uusia samanlaisia prosesseja.
Oletetaan, ett¨a yhden prosessin elinaikanaan luomien uusien prosessien lukum¨a¨ar¨a on Bin(n, p)-jakautunut. Kun l¨ahdet¨a¨an liikkeelle yhdest¨a prosessista, niin odotusarvoisesti kuinka monta prosessia kaikkiaan k¨aynnistyy?
Olkoon Yi prosessien lukum¨a¨ar¨a ”sukupolvessa” i. Siis Y0 = 1 ja
Y1 ∼ Bin(n, p). Kiinnitet¨a¨an nyt i, ja merkit¨a¨an sukupolven i prosessin numero k j¨alkel¨aisten lukum¨a¨ar¨a¨a Zk. Siis Zk ∼ Bin(n, p).
Tarkastellaan ehdollisia odotusarvoja:
E[Yi | Yi−1 = yi−1] = E
"yi−1 X
k=1
Zk | Yi−1 = yi−1
#
= E
"yi−1 X
k=1
Zk
#
= yi−1np
koska Zk ja Yi−1 ovat riippumattomia. Siis E[Yi | Yi−1] = npYi−1, joten E[Yi] = E[E[Yi | Yi−1]] = E[npYi−1] = npE[Yi−1].
Koska Y0 = 1, induktiolla saadaan E[Yi] = (np)i. Prosessien kokonaism¨a¨ar¨an odotusarvo on
E
X
i≥0
Yi
= X
i≥0
(np)i joka on ¨a¨arellinen joss np < 1. 2
Geometrinen jakauma
[M&U luku 2.4]Satunnaismuuttuja X noudattaa geometrista jakaumaa parametrilla p, merkit¨a¨an X ∼ Geom(p), jos
Pr(X = n) = (1 − p)n−1p, n = 1,2, . . . .
Siis X ilmaisee tarvittavien yritysten m¨a¨ar¨a¨a, ett¨a riippumattomassa
toistokokeessa saadaan ensimm¨ainen onnistuminen, kun yksitt¨aisen kokeen onnistumistodenn¨ak¨oisyys on p.
Geometrisella jakaumalla on unohdusominaisuus
Pr(X = n + k | X > k) = Pr(X = n). Jakauman odotusarvo on
E[X] = 1 p.
Tapa 1: K¨aytet¨a¨an kaavaa
E[X] =
∞
X
i=1
Pr(X ≥ i),
joka p¨atee olettaen, ett¨a X saa vain ei-negatiivisia kokonaislukuarvoja.
Kun X ∼ Geom(p), niin
Pr(X ≥ i) =
∞
X
n=i
(1− p)n−1p = (1 − p)i−1. Siis
E[X] = X∞
i=1
(1 − p)i−1 = 1 p.
Tapa 2: K¨aytet¨a¨an unohdusominaisuutta. Olkoon X = min{i | Yi = 1}, miss¨a satunnaismuuttujat Yi, i = 1,2, . . ., ovat riippumattomia
Bernoulli(p)-jakautuneita.
Tunnetun perusominaisuuden mukaan
E[X] = E[X | Y1 = 0] Pr(Y1 = 0) + E[X | Y1 = 1] Pr(Y1 = 1).
Nyt Pr(Y1 = 1) = p, ja X = 1 aina kun Y1 = 1. Toisaalta Y1 = 0 tarkoittaa samaa kuin X > 1. Unohdusominaisuuden mukaan
Pr(X = n + 1 | X > 1) = Pr(X = n) eli, kun merkit¨a¨an Z = X + 1,
Pr(X = m | X > 1) = Pr(X = m − 1) = Pr(Z = m), m ≥ 2. Siis E[X | X > 1] = E[Z] = E[X] + 1. Saadaan
E[X] = (1 − p)(E[X] + 1) + p,
Esimerkki 2.5: Kortinker¨a¨aj¨an ongelma [M&U luku 2.4.1]
Muropakkauksessa on aina yksi ker¨ailykortti. Kortteja on n erilaista. Kuinka monta muropakettia pit¨a¨a ostaa, ett¨a saadaan koko sarja?
Olkoon kyseinen satunnaismuuttuja X. Olkoon Xi niiden pakkausten m¨a¨ar¨a, jotka ostettiin sin¨a aikana, kun tasan i−1 erilaista korttia oli jo l¨oydetty. Siis
X =
n
X
i=1
Xi.
Kun i − 1 korttia on l¨oydetty, todenn¨ak¨oisyys saada uusi kortti seuraavasta pakkauksesta on pi = (n − i + 1)/n. Siis Xi ∼ Geom(pi).
Saadaan
E[X] =
n
X
i=1
E[Xi]
=
n
X
i=1
1 pi
=
n
X
i=1
n n− i + 1
= n
n
X
j=1
1 j
= nH(n), miss¨a H(n) = Pn
i=1(1/i). Tunnetusti [M&U Lemma 2.10]
lnn ≤ H(n) ≤ lnn + 1, n¨ahd¨a¨an
Esimerkki 2.6: Pikaj¨arjest¨aminen (quicksort) [M&U luku 2.5]
Tarkastellaan algoritmin satunnaistettua versiota:
Quicksort(S[1..n])
Jos n ≤ 1, niin palauta S.
Valitse satunnainen i ∈ {1, . . . , n}. Olkoon x = S[i].
Jaa S kahteen osalistaan:
Listaan L alkiot, jotka ovat pienempi¨a kuin x. Listaan H alkiot, jotka ovat suurempia kuin x.
Palauta [Quicksort(L), x,Quicksort(H)].
Alkiota x sanotaan jakoalkioksi (pivot).
Pahin tapaus: jakoalkio aina listan suurin tai pienin alkio. Tarvitaan n(n − 1)/2 = Θ(n2) vertailua.
Keskim¨a¨ar¨ainen tapaus: Olkoon X satunnaisen Quicksortin tekemien vertailujen lukum¨a¨ar¨a.
Olkoot taulukon S luvut suuruusj¨arjestyksess¨a y1, . . . , yn. Merkit¨a¨an Xij = 1, jos suorituksen aikana alkioita yi ja yj verrataan, muuten Xij = 0. Koska mit¨a¨an alkioparia ei verrata kahdesti, niin
X =
n−1
X
i=1 n
X
j=i+1
Xij.
Kiinnitet¨a¨an i < j. Hetken miettiminen osoittaa, ett¨a Xij = 1, jos ja vain jos joko yi tai yj on ensimm¨ainen joukosta Y ij = {yi, yi+1, . . . , yj−1, yj } valittu jakoalkio. Koska kaikki jakoalkiot ovat yht¨a todenn¨ak¨oisi¨a,
E[Xij] = Pr(Xij = 1) = 2
j − i + 1.
Nyt voidaan laskea
E[X] =
n−1
X
i=1 n
X
j=i+1
2 j − i + 1
=
n−1
X
i=1
n−i+1
X
k=2
2 k
=
n
X
k=2
n+1−k
X
i=1
2 k
=
n
X
k=2
(n + 1 − k)2 k
= (n + 1)
n
X
k=2
2
k − 2(n − 1)
= (2n + 2)H(n) − 4n.
Siis vertailuja tehd¨a¨an odotusarvoisesti E[X] = 2nlnn + Θ(n).
Tarkastellaan viel¨a yksinkertaista deterministist¨a versiota: jakoalkioksi valitaan aina listan ensimm¨ainen alkio x = S[1].
Jos nyt oletetaan, ett¨a sy¨ote on satunnaisessa j¨arjestyksess¨a (ja kaikkien j¨arjestysten todenn¨ak¨oisyydet samat) niin algoritmi tekee keskim¨a¨arin samat 2nlnn + Θ(n) vertailua kuin edell¨a.
T¨am¨a n¨ahd¨a¨an kuten yll¨a. Nyt alkiot yi ja yj tulevat vertailluksi, jos jompi kumpi niist¨a on sy¨otteess¨a ennen muita joukon Y ij alkioita.
Huom. t¨ass¨a siis keskiarvo on sy¨otteiden, ei algoritmin satunnaisvalintojen yli. T¨am¨a edellytt¨a¨a oletusta sy¨otteen jakaumasta. Haluttaessa voidaan
tietysti lis¨at¨a algoritmiin esiprosessointi, joka sekoittaa listan satunnaisesti. 2
3. Momentit ja poikkeamat
Pelkk¨a odotusarvo ei yleens¨a ole kovin tyhjent¨av¨a kuvaus
satunnaismuuttujan jakaumasta. Seuraava askel jakauman kuvaamisessa on tyypillisesti keskihajonnan laskeminen.
Hajontalukujen avulla voidaan my¨os todistaa ”h¨ant¨arajoja” eli arvioida todenn¨ak¨oisyytt¨a, ett¨a saadaan hyvin suuri (tai pieni) arvo. N¨am¨a ovat etenkin tietojenk¨asittelyss¨a (mutta my¨os tilastotieteess¨a) usein juuri ne suureet, joista ollaan ensisijaisesti kiinnostuneita.
Yksinkertaisin arviointitekniikka perustuu Markovin ep¨ayht¨al¨o¨on [M&U Thm. 3.1]: jos X ei saa negatiivisia arvoja, niin
Pr(X ≥ a) ≤ E[X] a . Todistus:
E[X] = X
x
xPr(X = x)
= X
x<a
xPr(X = x) + X
x≥a
xPr(X = x)
≥ 0 + aX
x≥a
Pr(X = x)
miss¨a summaukset rajoitetaan X:n arvoalueeseen. 2
Esimerkki 3.1: Heitet¨a¨an symmetrist¨a rahaa n kertaa. Mill¨a todenn¨ak¨oisyydell¨a tulee ainakin 3n/4 kruunaa?
Jos X on kruunien lukum¨a¨ar¨a, niin X ≥ 0 ja E[X] = n/2. Siis Pr(X ≥ 3n/4) ≤ n/2
3n/4 = 2 3.
T¨am¨a on eritt¨ain karkea arvio, jossa siis ei viel¨a k¨aytetty lainkaan hyv¨aksi tietoja jakauman hajonnasta. (Jo yksinkertaisella symmetriatarkastelulla n¨akee, ett¨a kyseinen todenn¨ak¨oisyys on alle 1/2.) 2
Momentit ja varianssi
[M&U luku 3.2]Satunnaismuuttujan X k:s momentti on E[Xk].
Satunnaismuuttujan X varianssi on
Var[X] = E[(X − E[X])2] ja keskihajonta
σ[X] = p
Var[X]. Satunnaismuuttujien X ja Y kovarianssi on
Cov(X, Y ) = E[(X − E[X])(Y − E[Y ])].
M¨a¨aritelmist¨a ja odotusarvon lineaarisuudesta seuraa suoraan Var[X] = E[X2] − (E[X])2
Var[X + Y ] = Var[X] +Var[Y ] + 2Cov[X, Y ].
Jos X ja Y ovat riippumattomia niin
E[XY ] = E[X]E[Y ] Cov(X, Y) = 0
Var[X + Y ] = Var[X] + Var[Y ]
N¨am¨a yleistyv¨at induktiolla useamman satunnaismuuttujan summalle ja tulolle.
Esimerkki 3.2: Jos Xi ∼ Bernoulli(p), niin suoraan laskemalla saadaan Var[Xi] = p(1− p).
Siis jos X on n riippumattoman Bernoulli(p)-satunnaismuuttujan summa eli X ∼ Bin(n, p), niin
Var[X] = np(1− p).
2
Tˇ sebyˇ sevin ep¨ ayht¨ al¨ o
[M&U luku 3.3]Lause 3.3: Mille tahansa a > 0 p¨atee
Pr(|X − E[X]| ≥ a) ≤ Var[X]
a2 .
Todistus: Kirjoitetaan arvioitava todenn¨ak¨oisyys muotoon Pr(|X − E[X]| ≥ a) = Pr((X − E[X])2 ≥ a2)
ja sovelletaan ei-negatiiviseen satunnaismuuttujaan Y = (X − E[X])2 Markovin ep¨ayht¨al¨o¨a:
Pr(Y ≥ a2) ≤ E[Y ]
a2 = Var[X] a2 .
2
Esimerkki 3.4: Tarkastellaan samaa tilannetta kuin Markovin ep¨ayht¨al¨on yhteydess¨a: Symmetrist¨a rahaa heitet¨a¨an n kertaa. Mill¨a todenn¨ak¨oisyydell¨a kruunien lukum¨a¨ar¨a X on ainakin 3n/4?
Koska X on binomijakautunut, saadaan E[X] = n/2 ja Var[X] = n1
2(1 − 12) = n/4. Siis Pr(
X −
n 2 ≥
n
4) ≤ Var[X]
(n/4)2 = 4 n. Tilanteen symmetrisyyden takia
Pr(
X −
n 2 ≥
n
4) = 2 Pr(X − n
2 ≥ n 4), joten
Pr(X ≥ 3n
4 ) ≤ 2 n.
(T¨am¨akin on itse asiassa eritt¨ain l¨oys¨a raja, paljon parempi saadaan pian k¨aytt¨am¨all¨a Chernoffin rajoja.) 2
Esimerkki 3.5: Kortinker¨a¨aj¨an ongelma (jatkoa Esimerkkiin 2.5).
Tarvittavien muropakkausten lukum¨a¨ar¨an X odotusarvoksi saatiin nH(n).
Siis Markovin ep¨ayht¨al¨ost¨a seuraa
Pr(X ≥ 2nH(n)) ≤ 1 2.
Tˇsebyˇsevin ep¨ayht¨al¨on laskemiseksi tarvitaan varianssi Var[X]. Muistetaan ett¨a X = Pn
i=1Xi miss¨a Xi ∼ Geom(pi) ja pi = (n − i + 1)/n.
Satunnaismuuttujan X ∼ Geom(p) varianssi on tunnetusti Var[X] = 1 − p
p2 .
Satunnaismuuttujat Xi ovat riippumattomia, joten Var[X] =
n
X
i=1
Var[Xi].
Arvioimalla Var[Xi] ≤ 1/p2
i saadaan
n
X
i=1
Var[Xi] ≤
n
X
i=1
n n − i+ 1
2
≤ n2
∞
X
i=1
1
i2 = π2n2 6 . Siis Tˇsebyˇsevin ep¨ayht¨al¨ost¨a seuraa
Pr(|X − nH(n)| ≥ nH(n)) ≤ π2n2/6
(nH(n))2 = O
1 (logn)2
.
T¨am¨ak¨a¨an ei ole kovin tiukka arvio. Todenn¨ak¨oisyys ett¨a askeleeseen n(c + lnn) menness¨a ei ole l¨oydetty korttia i on
1 − 1 n
n(c+lnn)
≤ exp(−(c + lnn)).
Todenn¨ak¨oisyys ett¨a jotakin korttia ei ole l¨oydetty askeleeseen n(c + lnn) menness¨a on siis korkeintaan nexp(−(c + lnn)) = e−c. Sijoittamalla c = lnn saadaan
Pr(X ≥ 2nlnn) ≤ 1 n.
Satunnaistettu mediaanialgoritmi
[M&U luku 3.4]Tarkastellaan yksinkertaisuuden vuoksi tapausta, jossa joukossa S on pariton m¨a¨ar¨a erisuuria lukuja. Joukon S mediaani on siis joukon S j¨arjestyksess¨a (⌈n/2⌉):s alkio, miss¨a n = |S|.
Mediaani voidaan m¨a¨aritt¨a¨a yksinkertaisesti j¨arjest¨am¨all¨a joukko ajassa O(nlogn). Ongelmalle tunnetaan my¨os (monimutkaisehko) ajassa O(n) toimiva deterministinen algoritmi. Seuraavassa esitell¨a¨an yksinkertainen ajassa O(n) toimiva satunnaisalgoritmi.
Ideana on valita sopivalla satunnaismenetelm¨all¨a ”alaraja” d ∈ S ja ”yl¨araja”
u ∈ S siten, ett¨a suurella todenn¨ak¨oisyydell¨a 1. mediaani on lukujen d ja u v¨aliss¨a ja
2. lukujen d ja u v¨aliss¨a on vain v¨ah¨an joukon S lukuja.
Kun sivuutetaan toistaiseksi lukujen d ja u valintaperusteet, saadaan seuraava algoritmi:
1. Valitse d ja u.
2. Muodosta joukko C = {x ∈ S | d ≤ x ≤ u} sek¨a laske ℓd = |{x ∈ S | x < d}| ja ℓu = |{x ∈ S | u < x}|.
3. Jos ℓd > n/2 tai ℓu > n/2 niin ep¨aonnistu.
4. Jos |C| > 4n3/4 niin ep¨aonnistu.
5. Muuten j¨arjest¨a joukko C ja palauta sen (⌊n/2⌋ − ℓd + 1):s alkio.
Jos alkioiden d ja u valinta tapahtuu ajassa O(n), niin koko algoritmin aikavaatimus on selv¨asti O(n).
Jos algoritmi ei ep¨aonnistu, se tuottaa selv¨asti oikean vastauksen.
Toistamalla sit¨a kunnes onnistutaan saadaan siis Las Vegas -algoritmi, joka antaa aina oikea lopputuloksen mutta toisinaan vie paljon aikaa.
Analyysin mielenkiintoinen kohta on m¨a¨ar¨at¨a d ja u siten, ett¨a ep¨aonnistumistodenn¨ak¨oisyys on pieni.
(J¨atet¨a¨an jatkossa py¨oristys merkitsem¨att¨a.)
Lukujen d ja u valintamenetelm¨a on seuraava:
1. Valitse (moni)joukko R ⊆ S poimimalla tasaisesta jakaumasta (takaisinpanolla) n3/4 alkiota.
2. J¨arjest¨a joukko R.
3. Nyt d on j¨arjestyksess¨a (12n3/4 − n1/2):s joukon R alkio ja u j¨arjestyksess¨a (12n3/4 + n1/2):s.
Intuitiivisesti joukon R mediaani, eli j¨arjestyksess¨a (12n3/4):s alkio, on samalla estimaatti koko joukon S mediaanille. Ensimm¨ainen ep¨aonnistumishaara
vastaa tilannetta, jossa t¨am¨a estimaatti on mennyt pahasti pieleen.
Alkioiden d ja u v¨alill¨a on 2n1/2 joukon R alkiota, joten jos otanta on ollut
”tasaista”, niiden v¨alill¨a on 2n1/2(n/n3/4) = 2n3/4 joukon S alkiota. Toinen ep¨aonnistumishaara vastaa tilannetta, ett¨a otos on sattunut ep¨atasaisesti.
Luvut n3/4, n1/2 jne. m¨a¨ar¨aytyv¨at siit¨a, millaisia arvioita otantatarkkuudelle tunnetaan. (Toisin sanoen ne on valittu siten, ett¨a seuraavat todistukset menev¨at l¨api.)
Analysoidaan nyt ep¨aonnistumistodenn¨ak¨oisyys t¨asm¨allisesti. Olkoon m joukon S mediaani ja k = |R| = n3/4. Muodostetaan kolme tapahtumaa:
E1 : |{r ∈ R | r ≤ m}| < k
2 − n1/2 E2 : |{r ∈ R | r ≥ m}| < k
2 − n1/2 E3 : |C| > 4k.
Tapahtuma E3 vastaa selv¨asti toista ep¨aonnistumisehtoa.
Tapahtumat E1 ja E2 vastaavat tilanteita m < d ja m > u eli yhdess¨a kattavat ensimm¨aisen ep¨aonnistumisvaihtoehdon.
Todenn¨ak¨oisyyden Pr(E1) arvioimiseksi merkit¨a¨an Y1 = |{r ∈ R | r ≤ m}|. Siis Y1 = Pk
i=1Xi miss¨a Xi =
1 jos i:s otos on korkeintaan m 0 muuten.
Korkeintaan mediaanin kokoisia alkioita joukossa S on (n− 1)/2 + 1
kappaletta, joten Y1 ∼ Bin(k, p) miss¨a p = 1/2 + 1/(2n). Siis E[Y1] ≥ k/2 ja Var[Y1] = k
1
2 + 1 2n
1
2 − 1 2n
< k 4. Sovelletaan Tˇsebyˇsevin ep¨ayht¨al¨o¨a:
Pr(E1) ≤ Pr(|Y1 − E[Y1]| > n1/2) ≤ Var[Y1]
n ≤ 1
4n−1/4.
Samoin n¨ahd¨a¨an
Pr(E2) ≤ 1
4n−1/4.
Tapahtumaa E3 varten erotellaan kaksi osatapausta:
E3,1 : |{c ∈ C | c > m}| ≥ 2k E3,2 : |{c ∈ C | c < m}| ≥ 2k.
Jos |C| > 4k, niin ainakin toinen n¨aist¨a p¨atee. Tapaukset ovat symmetriset.
Tarkastellaan tapausta E3,1. T¨all¨oin alkion u j¨arjestysnumero joukossa S on ainakin n/2 + 2k. Siis alkio u ja sit¨a suuremmat otoksen R alkiot kuuluvat n/2 − 2k suurimman alkion joukkoon joukossa S. Alkion u m¨a¨aritelm¨an perusteella n¨ait¨a on k/2 − n1/2 kappaletta.
Merkit¨a¨an Xi =
1 jos i:s otos kuuluu n/2 − 2k suurimman alkion joukkoon joukossa S 0 muuten
ja X = Pk
i=1Xi. Taas X on binomijakautunut, E[X] = k
2 − 2n1/2 ja
Var[X] = k 1
2 − 2n−1/4 1
2 + 2n−1/4
< k 4 joten
Pr(E3,1) ≤ Pr(|X − E[X]| ≥ n1/2) ≤ Var[X]
n < 1
4n−1/4. Siis kaikkiaan ep¨aonnistumistodenn¨ak¨oisyys on korkeintaan
Pr(E1) + Pr(E2) + Pr(E31) + Pr(E3 1) < n−1/4.
4. Chernoffin rajat
”Chernoffin raja” on yleisnimi joukolle ep¨ayht¨al¨oit¨a, jotka kertovat satunnaismuuttujan keskittymisest¨a odotusarvonsa ymp¨arille.
Perusesimerkki: Kun X ∼ Bin(n, p), niin kaikilla 0 < δ ≤ 1 p¨atee Pr
X − np np ≥ δ
≤ exp
−1
3npδ2
. T¨ast¨a seuraa esim. ett¨a todenn¨ak¨oisyydell¨a 1/2
X ≤ np + p
3npln 2.
T¨at¨a rajaa voidaan (a) tarkentaa ja (b) yleist¨a¨a.
Seuraavassa k¨ayd¨a¨an l¨api t¨am¨antyyppisi¨a rajoja, niiden todistuksia ja sovelluksia.
Momenttigeneroiva funktio
[M&U luku 4.1]Satunnaismuuttujan X momenttigeneroiva funktio on MX(t) = E[etX]
(mik¨ali t¨am¨a odotusarvo on ¨a¨arellinen). Derivoimalla momenttigeneroiva funktio origossa n kertaa saadaan satunnaismuuttujan n:s momentti:
Lause 4.1: Jos MX(t) on m¨a¨aritelty jossain origon ymp¨arist¨oss¨a t ∈ (−δ, δ), niin
E[Xn] = M(n)
X (0) kun n = 1,2, . . ..
Todistus: Momenttigeneroiva funktio on siis MX(t) = X
x
Pr(X = x) exp(tx).
Annettujen ehtojen vallitessa se voidaan derivoida termeitt¨ain:
M(n)(t) = X
Pr(X = x)xnexp(tx).
Esimerkki 4.2: Kun X ∼ Geom(p), niin E[etX] =
X∞
k=1
(1 − p)k−1petk
= p
1 − p X∞
k=1
((1 − p)et)k
= p
1 − p
1
1 − (1− p)et − 1
mist¨a derivoimalla saadaan
MX′ (t) = pet
(1− (1− p)et)2 MX′′(t) = 2p(1 − p)e2t
(1− (1− p)et)3 + pet
(1 − (1 − p)et)2.
Sijoittamalla t = 0 saadaan tutut tulokset E[X] = 1/p ja E[X2] = (2 − p)/p2.
Voidaan osoittaa (mutta t¨all¨a kurssilla ei osoiteta), ett¨a momenttigeneroiva funktio (tai kaikki momentit) spesifioi todenn¨ak¨oisyysmuuttujan jakauman yksik¨asitteisesti:
Lause 4.3: Jos X ja Y ovat satunnaismuuttujia, joille jollain δ > 0 p¨atee MX(t) = MY(t) kaikilla −δ < t < δ, niin satunnaismuuttujilla X ja Y on sama jakauma. 2
T¨at¨a voidaan k¨aytt¨a¨a esim. kahden satunnaismuuttujan tulon jakauman m¨a¨aritt¨amiseen yhdess¨a seuraavan kanssa:
Lause 4.4: Jos X ja Y ovat riippumattomia, niin MX+Y(t) = MX(t)MY(t).
Todistus: T¨all¨oin my¨os etX ja etY ovat riippumattomia, joten E[et(X+Y)] = E[etXetY] = E[etX]E[etY].
Chernoffin rajojen johto
[M&U luku 4.2.1]Idea on soveltaa Markovin ep¨ayht¨al¨o¨a satunnaismuuttujaan etX sopivalla t. Siis
Pr(X ≥ a) = Pr(etX ≥ eta) ≤ E[etX] eta mill¨a tahansa t > 0, eli erityisesti
Pr(X ≥ a) ≤ min
t>0
E[etX] eta .
Valitsemalla negatiivinen t ep¨ayht¨al¨on suunta vaihtuu, joten Pr(X ≤ a) ≤ min
t<0
E[etX] eta .
Idean soveltamiseen tarvitaan arvio momenttigeneroivalle funktiolle E[etX] ja sopiva t:n arvo.
Usein esitet¨a¨an rajoja, joissa t on hieman ep¨aoptimaalinen, jolloin saadaan ymm¨arrett¨av¨ampi¨a kaavoja.
Yleisimmin k¨aytetyss¨a versiossa X = Pn
i=1Xi, miss¨a Xi ∼ Bernoulli(pi) ovat riippumattomia. Satunnaismuuttujia Xi sanotaan Poisson-toistokokeiksi. Jos jakaumat ovat identtiset, pi = p kaikilla i, puhutaan Bernoulli-toistokokeista.
Merkit¨a¨an µ = E[X] = Pn
i=1pi. Yrit¨amme arvioida todenn¨ak¨oisyyksi¨a Pr(X ≥ (1 + δ)µ) ja Pr(X ≤ (1 − δ)µ).
Arvioidaan ensin yksitt¨aisten toistokokeiden momenttigeneroivaa funktiota:
MXi(t) = piet·1 + (1 − pi)et·0 = 1 + pi(et − 1) ≤ exp(pi(et − 1)), miss¨a on taas sovellettu ep¨ayht¨al¨o¨a 1 + z ≤ ez. T¨ast¨a saadaan
MX(t) =
n
Y
i=1
MXi(t) ≤ exp
n
X
i=1
pi(et − 1)
!
= exp (et − 1)µ .
Johdamme seuraavaksi erikseen rajat todenn¨ak¨oisyyksille, ett¨a X on hyvin suuri tai hyvin pieni.
Todistetaan ensin perusraja, joka on (suhteellisen) tiukka mutta hankala.
T¨ast¨a voidaan sitten johtaa yhsinkertaistettuja (ja l¨oysempi¨a) versioita.
Lause 4.5: Kaikille δ > 0 p¨atee
Pr(X ≥ (1 + δ)µ) <
eδ
(1 + δ)1+δ µ
.
Todistus: Kuten edell¨a todettiin, kun t > 0, Markovin ep¨ayht¨al¨ost¨a saadaan Pr(X ≥ (1 + δ)µ) = Pr(etX ≥ et(1+δ)µ) ≤ E[etX]
exp(t(1 + δ)µ). Valitaan t = ln(1 + δ), jolloin
E[etX] ≤ exp((et − 1)µ) = eδµ ja
exp(t(1 + δ)µ) = (1 + δ)(1+δ)µ. 2
Seuraava on usein k¨aytetty yksinkertaistus:
Lause 4.6: Kun 0 < δ ≤ 1, niin
Pr(X ≥ (1 + δ)µ) ≤ exp(−µδ2/3).
Todistus: Riitt¨a¨a siis osoittaa
eδ
(1 + δ)1+δ ≤ e−δ2/3
eli yht¨apit¨av¨asti (ottamalla logaritmi puolittain) f(δ) ≤ 0, miss¨a f(δ) = δ − (1 + δ) ln(1 + δ) + 1
3δ2.
Derivoidaan:
f(δ) = δ − (1 + δ) ln(1 + δ) + 1 3δ2 f′(δ) = −ln(1 + δ) + 2
3δ f′′(δ) = − 1
1 + δ + 2 3.
Nyt f′′(δ) < 0 v¨alill¨a 0 ≤ δ < 1/2, eli f′(δ) pienenee. Toisaalta f′′(δ) > 0 v¨alill¨a 1/2 < δ < 1, eli f′(δ) kasvaa.
Koska f′(0) = 0 ja f′(1) = 2/3 − ln 2 ≈ 2/3 − 0,69 < 0, p¨atee f′(δ) ≤ 0 v¨alill¨a 0 ≤ δ ≤ 1.
Koska f(0) = 0, p¨atee f(δ) ≤ 0 kaikilla 0 < δ < 1. 2
Toinen tapa yksinkertaistaa rajaa on seuraava:
Lause 4.7: Kun R ≥ 6µ, niin
Pr(X ≥ R) ≤ 2−R.
Todistus: Merkit¨a¨an R = (1 + δ)µ, jolloin δ = R/µ − 1 ≥ 5. Saadaan eδ
(1 + δ)1+δ µ
≤
e 1 + δ
(1+δ)µ
≤ e 6
R
≤ 2−R. 2
Tarkastellaan sitten todenn¨ak¨oisyytt¨a, ett¨a X on hyvin pieni.
Lause 4.8: Kaikilla 0 < δ < 1 p¨atee
Pr(X ≤ (1− δ)µ) ≤
e−δ (1 − δ)1−δ
µ
.
Todistus: Kuten aiemmin, kaikilla t < 0 p¨atee Pr(X ≤ (1− δ)µ) ≤ E[etX]
et(1−δ)µ ≤ exp((et − 1)µ) exp(t(1− δ)µ). Haluttu arvio saadaan sijoittamalla t = ln(1 − δ). 2
T¨at¨a voidaan arvioida kuten toisessakin tapauksessa:
Lause 4.9: Kaikilla 0 < δ < 1 p¨atee
Pr(X ≤ (1− δ)µ) ≤ exp(−µδ2/2).
Todistus: Samalla tekniikalla kuin tapaus ”(1 +δ)”, yksityiskohdat sivuutetaan. 2
Arviot voidaan yhdist¨a¨a:
Korollaari 4.10: Kaikilla 0 < δ < 1 p¨atee
Pr(|X − µ| ≤ δµ) ≤ 2 exp(−µδ2/3).
2
Rahanheitto
[M&U luku 4.2.2]Heitet¨a¨an symmetrist¨a rahaa n kertaa. Siis µ = n/2. Millainen raja p¨atee todenn¨ak¨oisyydell¨a 2/n (siis hyvin todenn¨ak¨oisesti)?
Halutaan exp(−(n/2)δ2/3) = 1/n, mist¨a δ = p
(6 lnn)/n. Sijoittamalla t¨am¨a rajaan saadaan
Pr
X −
n 2 ≥
1 2
√6nlnn
≤ 2 n. Siis melko varmasti poikkeamat ovat O(√
nlogn).
Verrataan Tˇsebyˇsevin ep¨ayht¨al¨oll¨a saatuun arvioon Pr
X −
n 2 ≥
n 4
≤ 4 n.
Jos otetaan Chernoff-arvio samalle virheen suuruudelle, saadaan Pr
X −
n 2 ≥
n 4
≤ 2e−n/24
Sovellus: parametrin estimointi
[M&U luku 4.2.3]Suoritetaan riippumattomia toistoja tuntemattomasta (mutta samana pysyv¨ast¨a) jakaumasta Bernoulli(p). Halutaan arvioida parametria p.
Olkoon X = Pn
i=1Xi onnistumisten lukum¨a¨ar¨a n toistossa ja ˜p = X/n. Selv¨asti E[˜p] = µ/n = p. Mit¨a voidaan sanoa virhetodenn¨ak¨oisyyksist¨a?
V¨ali [˜p − δ,p˜+ δ] on (1− γ)-luottamusv¨ali parametrille p, jos Pr(p ∈ [˜p − δ,p˜+ δ]) ≥ 1 − γ.
Tulkinta: N¨ahty¨amme koesarjan, jonka onnistumisfrekvenssi on ˜p, meill¨a on
”luottamus” 1 − γ siihen, ett¨a oikea parametri p on v¨alill¨a [˜p − δ,p˜+ δ]. Jos n¨ain ei olisi, niin havaitunlaisten koesarjojen todenn¨ak¨oisyys olisi alle γ.
Huom. p on vakio, sill¨a ei ole mit¨a¨an todenn¨ak¨oisyytt¨a (ellemme sitten oleta jotain priorijakaumaa ja tee bayeslaista analyysia).
