luennotsyksylla2005JyrkiKivinen 582421Satunnaisalgoritmit

582421 Satunnaisalgoritmit

luennot syksylla 2005 Jyrki Kivinen

Probabilistiset menetelmat algoritmien suunnittelussa ja analyysissa laudatur, 8 op / 4 ov

edellytetaan perustiedot todennakoisyyslaskennasta seka algoritmien suunnittelusta ja analyysista

Oppimateriaali

Kurssi noudattaa kirjaa

M. Mitzenmacher, E. Upfal: Probability and Computing (loytyy Kumpulan tiedekirjastosta ja Yliopistokirjakaupasta).

Opiskelijoilla oletetaan olevan kurssikirja kaytossa.

Luentorungot ilmestyvat kurssin kotisivulle, mutta ovat suppeat eivatka sovellu itseopiskeluun.

Laskuharjoitukset

Aikataulu: viikon n laskuharjoituksissa

tehtavat kasittelevat viikon n 2 perjantaina ja viikon n 1 keskiviikkona luennoitua materiaalia,

tehtavat ilmoitetaan viikon n 1 keskiviikkona ja

ratkaisut palautetaan kirjallisesti Kari Laasoselle (A321) viimeistaan viikon n tiistaina kello 12.00.

Ratkaisut arvostellaan asteikolla 0-3:

1 jotain jarkevaa yritysta

2 oikeansuuntainen melko pitkalle viety yritys

Kurssin arvostelu

Maksimipistemaara 60 pistetta:

kaksi kurssikoetta 24 + 24 = 48 pistetta laskuharjoitukset 12 pistetta

Lapipaasyraja noin 30 pistetta, arvosanan 5/5 raja 50 pistetta.

Laskuharjoituspisteet skaalataan seuraavasti:

0 % laskarisuorituksista antaa 0 pistetta

80 % (tai yli) laskarisuorituksista antaa 12 pistetta

Miksi satunnaisuutta

Satunnaisuus on tarkea valine luonnonilmioiden ym. mallintamisessa.

Satunnaisuutta tarvitaan algoritmien suunnittelussa ja analyysissa:

satunnaisalgoritmit (randomized): algoritmin toiminta samalla

syotteella vaihtelee riippuen algoritmin sisaisesta satunnaisuudesta ("rahanheitoista")

algoritmin toimintaymparisto voi olla satunnainen (keskimaaraisen tapauksen (average case) analyysi, tietoliikenne, . . . )

Todennakoisyyslaskenta on voimakas yleistyokalu kaikkiin tallaisiin tilanteisiin.

Satunnaisuuden avulla voidaan saada algoritmi joka on nopeampi kuin vastaava deterministinen algoritmi tai helpompi toteuttaa kuin vastaava det. alg.

Perustekniikoita/tilanteita:

satunnaisotanta, Monte Carlo -menetelmat satunnaishaku, simuloitu jaahdytys

sormenjalkitekniikat

Tietyissa tilanteissa satunnaisuus on valttamatonta etta saadaan ylipaansa hyvaksyttava ratkaisu:

vastustajan hamaaminen (kryptograa, pelit)

hajautetut jarjestelmat: kuorman tasapainotus, johtajan valinta jne.

Satunnaistamalla voidaan vahentaa algoritmin herkkyytta \hairioille":

esim. satunnaistettu quicksort, jolla ei ole erityista pahimman tapauksen syotetta.

Tyypillisi a kysymyksi a

Yleensa satunnaisalgoritmit antavat jollain todennakoisyydella vaaran vastauksen.

jos vastaus on kylla/ei: mika on virhetodennakoisyys jos vastaus on numeerinen tms.: mika on suuren virheen

todennakoisyys.

Jotkin satunnaisalgoritmit (ns. Las Vegas -algoritmit) antavat aina oikean vastauksen, mutta suoritusaika on satunnainen.

Mika on suoritusajan odotusarvo?

Mika on todennakoisyys, etta suoritusaika ylittaa tietyn rajan?

Kurssin sis alt oluonnos

1. Todennakoisyys (kertausta)

2. Diskreetit satunnaismuuttujat (kertausta) 3. Satunnaismuuttujan momentit

4. Chernon rajat 5. Pallot ja uurnat

6. "Probabilistinen menetelma"

7. Markovin ketjut

8. Jatkuvat satunnaismuuttuja, Poisson-prosessit 9. Monte Carlo -menetelmat

1. Todenn ak oisyys

Olkoon mielivaltainen joukko ja F P() jokin kokoelma sen

osajoukkoja. (Tassa P() on siis joukon potenssijoukko.) Kuvaus Pr: F ! R on todennakoisyysmitta, jos

1. Pr(E) 0 kaikilla E 2 F (positiivisuus), 2. Pr() = 1 ja

3. jos E1; E2; E3; : : : on jono erillisia joukkoja (eli Ei \ Ej = ; kun i 6= j) ja Ei 2 F kaikilla i, niin

Pr ([¹_i=1Ei) = X1 i=1

Pr(Ei)

Jotta todennakoisyysmitalle juuri asetetut ehdot ylipaansa olisivat mielekkaita, sen maarittelyjoukolla F taytyy olla tiettyja

sulkeumaominaisuuksia.

Osajoukkokokoelma F P() on -algebra, jos 1. 2 F,

2. jos A 2 F niin A 2 F, missa A = A, ja

3. jos A1; A2; A3; : : : on jono jolla Ai 2 F kaikilla i 2 f 1; 2; 3; : : : g, niin [¹_i=1Ai 2 F:

Huom. tassa ei oleteta mitaan joukkoperheen f Ai j i 2 I g yhdisteesta [i2IAi

jos I on ylinumeroituva.

Todennakoisyysavaruus on nyt kolmikko (; F; Pr), missa 1. otosavaruus on mielivaltainen joukko,

2. F P() on -algebra perusjoukkona , ja 3. Pr: F ! R on todennakoisyysmitta.

Otosavaruutta kutsutaan myos perusjoukoksi.

Perusjoukon osajoukot E ovat tapahtumia ja joukot E 2 F erityisesti alkeistapahtumia eli mitallisia joukkoja.

Jos on jokin perusjoukon alkioiden ominaisuus, merkitaan lyhyesti Pr((x)) = Pr(f x 2 j (x) g); esim.

Pr(g(x) = 3) = Pr(f x 2 j g(x) = 3 g).

Esimerkki 1.1: Jos on aarellinen, jj = n 2 N, niin joukon symmetrinen (eli tasainen) todennakoisyysavaruus on kolmikko (; P(); Pr), missa Pr(E) = jEj=n kaikilla E .

Yleisemmin jos todennakoisyysavaruus on muotoa (; P(); Pr), missa on

aarellinen tai numeroituvasti aareton, sita sanotaan diskreetiksi. Diskretti todennakoisyysavaruus voidaan maaritella antamalla kaikki yksittaisten alkioiden todennakoisyydet Pr(f x g), x 2 .

Jatkossa tarvitaan lahinna diskreetteja tn-avaruuksia. Sen takia jatamme yleensa myos mainitsematta muotoa "jos E 2 F" olevia oletuksia (joiden pitaisi muutenkin olla yleensa asiayhteydesta selvia).

Toisinaan on kuitenkin hyodyllista tarkastella numeroituvassakin muitakin -algebroja kuin P().

Esimerkki 1.2: Olkoon = R ja F suppein -algebra, joka sisaltaa kaikki suljetut valit [a; b], a; b 2 R. Taman -algebran alkioita sanotaan

Borel-joukoiksi.

Maaritellaan valin [a; b] todennakoisyydeksi valin [a; b] \ [0; 1] pituus:

Pr([a; b]) = min f b; 1 g max f a; 0 g. Muiden Borel-joukkojen

todennakoisyydet seuraavat todennakoisyysmitan maaritelmasta. Tama on osavalin [0; 1] symmetrinen todennakoisyysmitta.

Huom. kaikilla x 2 R patee Pr(f x g) = 0, joten minka tahansa

numeroituvan joukon todennakoisyys on 0. Tasta ei seuraa mitaan ylinumeroituvien joukkojen todennakoisyyksille.

Tuntuisi ehka yksinkertaisemmalta, jos tassa voitaisiin valita F = P(R), eli kaikkien reaalilukujoukkojen todennakoisyydet olisivat maariteltyja. Tama ei kuitenkaan ole mahdollista: jos em. funktio Pr yritetaan laajentaa koko

joukkoon P(R), niin kaikkia todennakoisyysmitan ehtoja ei saada pysymaan

Yhdisteen todenn ak oisyys

Maaritelmista seuraa suoraan, etta mille tahansa kahdelle alkeistapahtumalle patee

Pr(E [ F ) = Pr(E) + Pr(F ) Pr(E \ F ):

Samoin mille tahansa numeroituvalle I ja jonolle alkeistapahtumia Ei, i 2 I patee

Pr([i2IEi) X

i2I

Pr(Ei):

("union bound").

Kun jIj = n 2 N, niin yhdisteen tarkka todennakoisyys saadaan kaavasta Pr([i2IEi) =

Xn k=1

( 1)^k+1 X

JI;jJj=k

Pr(\j2JEj)

Laskemalla edellisen kaavan summaa vain johonkin rajaan k < n saakkaa saadaan vuorotellen yla- ja alarajoja:

Jos ` on pariton, niin

Pr([i2IEi) X` k=1

( 1)^k+1 X

JI;jJj=k

Pr(\j2JEj):

Jos ` on parillinen, niin

Pr([i2IEi) X` k=1

( 1)^k+1 X

JI;jJj=k

Pr(\j2JEj)

(Bonferronin epayhtalot).

Riippumattomuus

Kaksi alkeistapahtumaa E ja F ovat riippumattomia, jos Pr(E \ F ) = Pr(E) Pr(F ):

Yleisemmin alkeistapahtumat E1; : : : ; E_k ovat riippumattomia, jos kaikilla I f 1; : : : ; k g patee

Pr(\i2IEi) = Y

i2I

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 todennakoisyys ehdolla F on Pr(E j F ) = Pr(E \ F )

:

Kahden todennakoisyysavaruuden (1; F1; Pr1) ja (2; F2; Pr2) tulo on (1; F1; Pr1) (2; F2; Pr2) = (1 2; F1 F2; Pr1 Pr2) missa

F1 F2 = f E F j E 2 F1; F 2 F2 g ja

(Pr1 Pr2)(E F ) = Pr1(E) Pr2(F ):

Tarkea erikoistapaus on tn-avaruuden n-kertainen tulo itsensa kanssa (; F; Pr)ⁿ = (ⁿ; Fⁿ; Prⁿ). Jos alkuperainen tn-avaruus esittaa jotain

satunnaiskoetta, sen n-kertainen tulo itsensa kanssa esittaa n riippumatonta toistoa samasta kokesta. Talloin usein myos tulomitasta Prⁿ kaytetaan

yksinkertaisesti (ja epatasmallisesti) merkintaa Pr.

Esimerkki 1.3: Oletetaan annetuksi kaksi aliohjelmaa F ja G, jotka laskevat kokonaislukufunktiot f ja g. Funktioista f ja g tiedetaan vain, etta ne ovat korkeintaan d-asteisia polynomeja. Tehtavana on paatella, pateeko 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 patee korkeintaan d arvolla x 2 N. Erityisesti joukossa f 1; : : : ; rd g milla tahansa r 2 N on ainakin (r 1)d alkiota x, joilla f(x) g(x) 6= 0.

Saadaan seuraava perusalgoritmi:

1. Valitse satunnainen x 2 f 1; : : : ; rd g.

2. Jos f(x) g(x) 6= 0, tulosta "eri".

3. Muuten tulosta "samat".

Edella olevan perusteella

jos f = g, algoritmi tulostaa aina "samat" ja

jos f 6= g, algoritmi tulostaa "eri" ainakin todennakoisyydella (r 1)d=(rd) = 1 1=r.

Tehdaan nyt k riippumatonta toistokoetta seuraavasti:

1. Valitse toisistaan riippumatta satunnaiset x1; : : : ; x_k joukosta f 1; : : : ; rd g.

2. Jos f(xi) g(xi) 6= 0 ainakin yhdella 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 todennakoisyys on kork. 1=r. Taman todennakoisyys on siis korkeintaan (1=r)^k.

Toistokokeita suorittamalla virhetodennakoisyys saadaan siis eksponentiaalista vauhtia kohti nollaa.

Kokonaistodenn ak oisyys

Olkoot Ei, i 2 I, numeroituva kokoelma erillisia tapahtumia s.e. [_i2IEi = . Suoraan maaritelmista saadaan ns. kokonaistodennakoisyyden kaava

Pr(B) = X

i2I

Pr(B \ Ei) = X

i2I

Pr(B j Ei) Pr(Ei):

Tata voidaan soveltaa esim. viivytetyn valinnan tekniikalla:

Halutaan osoittaa esim. Pr(x 2 B) .

Jaetaan x sopivalla tavalla kahteen komponenttiin x = (x1; x2). Ajatellaan, etta "ensin" valitaan x1, ja "vasta myohemmin" x2.

Osoitetaan, etta miten tahansa x1 valitaankin, niin aina todennakoisyys valita x2 siten, etta (x1; x2) 2 B patee, on korkeintaan .

Sovelletaan kokonaistodennakoisyyden kaavaa valitsemalla

Esimerkki 1.4: On annettu n n-matriisit A, B ja C. Halutaan tarkistaa, pateeko AB = C, ilman etta tarvitsee laskea matriisituloa AB.

Menetellaan samaan tapaan kuin edellisessa esimerkissa:

1. Valitse satunnainen r 2 f 0; 1 gⁿ. 2. Jos ABr 6= Cr, tulosta "erisuuret".

3. Muuten tulosta "yhtasuuret".

Olkoon D = AB C. Vaitetaan, etta jos D ei ole nollamatriisi, niin Dr 6= 0 patee ainakin todennakoisyydella 1=2.

Merkitaan D = (dij). Oletetaan, etta D 6= 0; olkoon dpq 6= 0.

Jos Dr = 0, patee siis erityisesti Xn j=1

dpjrj = 0;

mista voidaan ratkaista

rq = d_pq¹X

j6=q

dpjrj:

Ajatellaan ensin valituksi r⁰ = (r1; : : : ; rq 1; r_q+1; : : : ; rn) ja tarkastellaan sitten puuttuvan komponentin rq valintaa. Koska vectorin r⁰ valinta kiinnittaa

lausekkeelle

d_pq¹ X

j6=q

dpjrj

jonkin arvon v, niin todennakoisyys etta rq = v on korkeintaan 1=2 (koska rq 2 f 0; 1 g). Lykatyn valinnan periaatteella siis nahdaan, etta

1

Bayesin s a ant o

Edelleen suoraan maaritelmista saadaan Pr(Ej j B) = Pr(Ej \ B)

Pr(B) = Pr(B j Ej) Pr(Ej) P

iPr(B j Ei) Pr(Ei) missa jalleen (Ei) ovat erillisia.

Tyypillinen tulkinta on, etta kaavan mukaan paivitetaan uskomuksia kun on saatu uutta dataa:

Tapahtumat Ej esittavat erilaisia toisensa poissulkevia hypoteeseja tyyliin Ej = "teoria numero i on tosi".

Tapahtuma B kuvaa jotain havaintoa, mittausdataa tms.

Pr(Ej) on a priori -todennakoisyys, joka mittaa uskoamme hypoteesiin Ej ennen kuin mitaan dataa on havaittu.

Pr(B j Ej) mittaa, kuinka hyvin hypoteesi Ej "selittaa" datan B.

Esimerkki 1.5: On annettu kolme kolikkoa, joista kaksi on tasapainoisia ja yhdella (emme tieda milla) kruunan todennakoisyys on 2/3.

Laitamme kolikot satunnaiseen jarjestykseen ja heitamme niita. Saamme tulokset (1: kruuna, 2: kruuna, 3: klaava).

Milla todennakoisyydella kolikko 1 on epatasapainoinen?

Soveltamalla Bayesin kaavaa saadaan vastaus 2/5.

Huom. Kaavan nimittaja ei riipu hypoteesista Ej.

Jos halutaan vain verrata eri hypoteesien a posteriori -todennakoisyyksi, voidaan unohtaa vakio Pr(B) ja kirjoittaa

Pr(Ej j B) / Pr(B j Ej) Pr(Ej):

Satunnainen minimileikkausalgoritmi

Olkoon G = (V; E) yhtenainen suuntaamaton verkko. Sallimme tassa poikkeuksellisesti, etta kahden solmun valilla saa olla useita kaaria (multigraph).

Kaarijoukko C E on leikkaus, jos (V; E C) ei ole yhtenainen.

Minimileikkaus on pienimman mahdollisen maaran kaaria sisaltava leikkaus.

Kaaren (u; v) kutistaminen korvaa solmut u ja v yhdella uudella solmulla.

Kaari (u; v) (tai kaikki nama kaaret, jos niita on useita) poistuvat verkosta.

Muut kaaret sailyvat, ja solmuihin u tai v liittyvat kaaret liitetaan uuteen niita korvaavaan solmuun.

Jos C on leikkaus alkuperaisessa verkossa ja (u; v) 62 C, niin C on leikkaus myos kutistamisen jalkeen. Toisaalta missaan tapauksessa kutistaminen ei tee verkkoon uusia leikkauksia.

Tarkastellaan seuraavaa algoritmia:

1. Valitse verkosta jokin kaari (u; v) siten, etta kunkin kaaren todennakoisyys tulla valituksi on sama.

2. Kutista kaari (u; v).

3. Jos verkossa on vahintaan kolme solmua, palaa kohtaan 1.

4. Muuten tulosta verkossa jaljella olevat kaaret.

Olkoon C jokin minimileikkaus. Edella esitetysta seuraa, etta jos algoritmi ei koskaan valitse joukon C kaarta kutistettavaksi, se tuottaa oikean

lopputuloksen.

Mika on taman suotuisan tapauksen todennakoisyys?

Olkoon Ei tapahtuma, etta iteraatiossa i kutistettava kaari ei ole joukossa C, ja Fi = \ⁱ_j=1Ei. Haluamme siis alarajan todennakoisyydelle Pr(Fn 2).

Olkoon k = jCj minimileikkauksen koko ja n = jV j. Talloin erityisesti jokaisen solmun aste on ainakin k, joten verkossa on vahintaan kn=2 kaarta. Siis

Pr(E1) = jEj jCj

jEj 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 maara on kuitenkin vahentynyt, joten askeinen argomentti antaa

Pr(Ei j Fi 1) 1 2

n i + 1:

Saadaan

Pr(Fn 2) = Pr(En 2 \ Fn 3)

= Pr(En 2 j Fn 3) Pr(Fn 3)

= : : :

= Pr(En 2 j Fn 3) Pr(En 3 j Fn 4) : : : Pr(E2 j F1) Pr(F1)

n 2Y

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 todennakoisyydella 2=(n(n 1)) minimileikkauksen.

Toistetaan algoritmia m kertaa ja valitaan saaduista leikkauksista pienin.

Todennakoisyys, etta ei saatu minimileikkausta, on korkeintaan

1 2

n(n 1) _m

exp

2m n(n 1)

missa on arvioitu 1 x e ^x.

Jos valitaan esim. m = n(n 1) ln n, rajaksi virhetodennakoisyydelle tulee 1=n².

2. Satunnaismuuttujat

Olkoon (; F; Pr) todennakoisyysavaruus. Reaaliarvoinen funktio X: ! R on satunnaismuuttuja, jos f s 2 j X(s) a g 2 F kaikilla a 2 R.

Satunnaismuuttuja on diskreetti, jos sen arvojoukko on numeroituva Myohemmin tarkastelemme myos jatkuvia satunnaismuuttujia, joiden arvoalue on ylinumeroituva. Tassa luvussa kuitenkin oletataan aina, etta tarkasteltavat satunnaismuuttujat ovat diskreetteja.

Yleensa todennakoisyytta Pr(f s 2 j X(s) = a g) merkitaan lyhyesti Pr(X = a) jne. Diskreetin satunnaismuuttujan jakauma (mika sisaltaa kaiken mita satunnaismuuttujasta voisi haluta kaytannossa tietaa) tulee maaratyksi, kun annetaan luvut Pr(X = a) kaikilla a 2 R.

Jono satunnaismuuttujia (X1; : : : ; Xk) on riippumaton, jos kaikilla I f 1; : : : ; k g ja kaikilla x1; : : : ; x_k 2 R patee

Pr(\i2I(Xi = xi)) = Y

i2I

Pr(Xi = xi):

"X ja Y ovat riippumattomia" merkitaan toisinaan X ? Y . Olkoon V satunnaismuuttujan X arvoalue. Jos summa P

x2V jxj Pr(X = x) suppenee, niin satunnaismuuttujan odotusarvo on

E[X] = X

x2V

x Pr(X = x):

Muuten odotusarvo ei ole maaritelty, mita usein merkitaan E[X] = 1.

Jos X ja Y ovat riippumattomia, patee

E[XY ] = E[X]E[Y ]:

Odotusarvo on lineaarinen:

E[aX + bY ] = aE[X] + bE[Y ] kaikilla a; b 2 R ja satunnaismuuttujilla X; Y .

Lineaarisuus ei suoraan yleisty aarettomiin summauksiin. Milloin patee E

" ₁ X

i=1

Xi

#

= X1 i=1

E[Xi]

on ei-triviaali ongelma. Eras riittava ehto on, etta kaikki odotusarvot E[jXij]

ovat maariteltyja ja P₁

E[jX j] suppenee.

Jensenin ep ayht al o

Maaritelmista seuraa suoraan tarkea perusominaisuus E[X²] (E[X])²:

Tama on erikoistapaus Jensenin epayhtalosta.

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.

Binomijakauma

Satunnaismuuttuja Y noudattaa Bernoulli-jakaumaa parametrilla p jos Pr(Y = 1) = p ja Pr(Y = 0) = 1 p:

Selvasti E[Y ] = p.

Satunnaismuuttuja X noudattaa binomijakaumaa parametreilla n ja p, merkitaan X B(n; p), jos se on n riippumattoman Bernoulli-muuttujan summa:

Pr(X = j) = _n j

p^j(1 p)^{n j}; j = 0; : : : ; n:

Odotusarvon lineaarisuudesta seuraa

E[X] = np:

Ehdollinen odotusarvo

Kun Y ja Z ovat satunnaismuuttujia, Y :n arvojoukko on V , ja z 2 R, merkitaan

E[Y j Z = z] = X

y2V

y Pr(Y = y j Z = z):

Esimerkki 2.2: Olkoot X1 ja X2 riippumattomien nopanheittojen tulokset ja X = X1 + X2. Talloin E[X j X1 = 3] = 6¹₂ ja

E[X1 j X = 4] = 1 1

3 + 2 1

3 + 3 1

3 = 2:

Kaikille satunnaismuuttujille X ja Y patee

E[X] = X

E[X j Y = y] Pr(Y = y)

Ehdollinen odotusarvo E[Y j Z] on satunnaismuuttuja joka maaritellaan seuraavasti:

Olkoot Y ja Z satunnaismuuttujia otosavaruudessa (eli funktioita ! R). Nyt E[Y j Z]: ! R on satunnaismuuttuja, jolla

E[Y j Z](!) = E[Y j Z = Z(!)]

kaikilla ! 2 .

Esimerkki 2.3: Olkoon taas X = X1 + X2, missa X1 ja X2 ovat riippumattomia nopanheittoja. Nyt

E[X j X1] = X1 + 31 2:

Ehdollinen odotusarvo noudattaa tavallisen odotusarvon perusominaisuuksia:

E[X1 + X2 j Z] = E[X1 j Z] + E[X2 j Z] jne. Lisaksi

Esimerkki 2.4: Haarautuvat prosessit.

Tarkastellaan tilannetta, jossa prosessi suorittaa jotain tiettya aliohjelmaa.

Tama aliohjelma voi puolestaan luoda uusia samanlaisia prosesseja.

Oletetaan, etta yhden prosessin elinaikanaan luomien uusien prosessien lukumaara on B(n; p)-jakautunut. Kun lahdetaan liikkeelle yhdesta

prosessista, niin odotusarvoisesti kuinka monta prosessia kaikkiaan kaynnistyy?

Olkoon Yi prosessien lukumaara "sukupolvessa" i. Siis Y0 = 1 ja

Y1 B(n; p). Kiinnitetaan nyt i, ja merkitaan sukupolven i prosessin numero k jalkelaisten lukumaaraa Zk. Siis Zk B(n; p).

Tarkastellaan ehdollisia odotusarvoja:

E[Yi j Yi 1 = yi 1] = E

"_{yi 1} X

k=1

Zk j Yi 1 = yi 1

#

= E

"_y Xi 1

k=1

Zk

#

= yi 1np koska Zk ? Yi 1. Siis E[Yi j Yi 1] = npYi 1, joten

E[Yi] = E[E[Yi j Yi 1]] = E[npYi 1]:

Koska Y0 = 1, induktiolla saadaan E[Yi] = (np)ⁱ. Prosessien kokonaismaaran odotusarvo on

E 2 4X

i0

Yi

3

5 ₌ X

i0

(np)ⁱ

Geometrinen jakauma

Satunnaismuuttuja X noudattaa geometrista jakaumaa parametrilla p, merk.

X Geom(p), jos

Pr(X = n) = (1 p)^{n 1}p; n = 1; 2; : : : :

Siis X ilmaisee riippumattomien kokeiden maaraa etta saadaan ensimmainen onnistuminen, kun yksittaisen kokeen onnistumistodennakoisyys on p.

Geometrisella jakaumalla on unohdusominaisuus

Pr(X = n + k j X > k) = Pr(X = n):

Jakauman odotusarvo on

E[X] = 1 p: Osoitamme taman kahdella eri tavalla.

Tapa 1: Kaytetaan kaavaa

E[X] = X1 i=1

Pr(X i)

joka patee kun X saa vain ei-negatiivisia kokonaislukuarvoja.

Kun X Geom(p), niin

Pr(X i) = X1 n=i

(1 p)ⁿp = (1 p)^{i 1}: Siis

E[X] = X1 i=1

(1 p)^{i 1} = 1 p:

Tapa 2: Kaytetaan unohdusominaisuutta. Olkoon X = min f i j Yi = 1 g missa satunnaimuuttujat Yi, i = 1; 2; : : :, ovat riippumattomia

Bernoulli(p)-jakautuneita.

Tunnetun perusominaisuuden mukaan

E[X] = E[X j Y1 = 0] Pr(Y1 = 0) + E[X j 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 j X > 1) = Pr(X = n) eli, kun merkitaan Z = X + 1,

Pr(X = m j X > 1) = Pr(X = m 1) = Pr(Z = m); m 2:

Siis E[X j X > 1] = E[Z] = E[X] + 1. Saadaan

E[X] = (1 p)(E[X] + 1) + p

Esimerkki 2.5: Kortinkeraajan ongelma

Muropakkauksessa on aina yksi kerailykortti. Kortteja on n erilaista. Kuinka monta muropakettia pitaa ostaa, etta saadaan koko sarja?

Olkoon kyseinen satunnaismuuttuja X. Olkoon Xi niiden pakkausten maara, jotka ostettiin sina aikana, kun tasan i 1 erilaista korttia oli jo loydetty. Siis

X = Xn i=1

Xi:

Kun i 1 korttia on loydetty, todennakoisyys saada uusi kortti seuraavasta pakkauksesta on pi = (n i + 1)=n. Siis Xi Geom(pi).

Saadaan

E[X] =

Xn i=1

E[Xi]

=

Xn i=1

1 pi

=

Xn i=1

n n i + 1

= n Xn j=1

1 j

= nH(n) missa H(n) = P_n

i=1(1=i). Koska

ln n H(n) ln n + 1;

nahdaan

Esimerkki 2.6: Pikajarjestaminen (quicksort).

Tarkastellaan algoritmin satunnaistettua versiota:

Quicksort(S[1::n])

Jos n 1 palauta S.

Valitse satunnainen i 2 f 1; : : : ; n g. Olkoon x = S[i].

Jaa S kahteen osalistaan:

Listaan L alkiot jotka ovat pienempia 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 = (n²) vertailua.

Keskimaarainen tapaus: Olkoon X satunnaisen Quicksortin tekemien vertailujen lukumaara.

Olkoot taulukon S luvut suuruusjarjestyksessa y1; : : : ; yn. Merkitaan Xij = 1 jos suorituksen aikana alkioita yi ja yj verrataan, muuten Xij = 0. Koska mitaan alkioparia ei verrata kahdesti, niin

X =

n 1X

i=1

Xn j=i+1

Xij:

Kiinnitetaan i < j. Hetken miettiminen osoittaa, etta Xij = 1 jos ja vain jos joko yi tai yj on ensimmainen joukosta Y ^ij = f yi; yi+1; : : : ; yj 1; yj g valittu jakoalkio. Koska kaikki jakoalkiot ovat yhta todennakoisia,

E[Xij] = Pr(Xij = 1) = 2

j i + 1:

Nyt voidaan laskea

E[X] =

n 1X

i=1

Xn j=i+1

2 j i + 1

=

n 1X

i=1

n i+1X

k=2

2 k

=

Xn k=2

n+1 kX

i=1

2 k

=

Xn k=2

(n + 1 k)2 k

= (n + 1) Xn k=2

2

k 2(n 1)

= (2n + 2)H(n) 4n:

Tarkastellaan viela yksinkertaista deterministista versiota: jakoalkioksi valitaan aina listan ensimmainen alkio x = S[1].

Jos nyt oletetaan, etta syote on satunnaisessa jarjestyksessa (ja kaikkien jarjestysten todennakoisyydet samat) niin algoritmi tekee keskimaarin samat 2n ln n + (n) vertailua kuin edella.

Tama nahdaan kuten ylla. Nyt alkiot yi ja yj tulevat vertailluksi, jos jompi kumpi niista on syotteessa ennen muita joukon Y ^ij alkioita.

Huom. tassa siis keskiarvo on syotteiden, ei algoritmin satunnaisvalintojen yli. Tama edellyttaa oletusta syotteen jakaumasta. Haluttaessa voidaan tietysti lisata algoritmiin esiprosessointi, joka sekoittaa listan satunnaisesti.

3. Momentit ja poikkeamat

Pelkka odotusarvo ei yleensa ole kovin tyhjentava kuvaus

satunnaismuuttujan jakaumasta. Seuraava askel jakauman kuvaamisessa on tyypillisesti keskihajonnan laskeminen.

Hajontalukujen avulla voidaan myos todistaa "hantarajoja" eli arvioida todennakoisyytta, etta saadaan hyvin suuri (tai pieni) arvo. Nama ovat etenkin tietojenkasittelyssa (mutta myos tilastotieteessa) usein juuri ne suureet, joista ollaan ensisijaisesti kiinnostuneita.

Yksinkertaisin arviointitekniikka perustuu Markovin epayhtaloon: jos X ei saa negatiivisia arvoja, niin

Pr(X a) E[X]

a : Todistus:

E[X] = X

x

x Pr(X = x)

= X

x<a

x Pr(X = x) + X

xa

x Pr(X = x) 0 + aX

xa

Pr(X = x)

missa summaukset rajoitetaan X:n arvoalueeseen.

Esimerkki 3.1: Heitetaan symmetrista rahaa n kertaa. Milla todennakoisyydella tulee ainakin 3n=4 kruunaa?

Jos X on kruunien lukumaara, niin X 0 ja E[X] = n=2. Siis Pr(X 3n=4) n=2

3n=4 = 2 3:

Tama on erittain karkea arvio, jossa siis ei viela kaytetty lainkaan hyvaksi tietoja jakauman hajonnasta. (Jo yksinkertaisella symmetriatarkastelulla nakee, etta kyseinen todennakoisyys on alle 1/2.)

Momentit ja varianssi

Satunnaismuuttujan X k:s momentti on E[X^k].

Satunnaismuuttujan X varianssi on

Var[X] = E[(X E[X])²] ja keskihajonta

[X] = p

Var[X]:

Satunnaismuuttujien X ja Y kovarianssi on

Cov(X; Y ) = E[(X E[X])(Y E[Y ])]:

Maaritelmista ja odotusarvon lineaarisuudesta seuraa suoraan Var[X] = E[X²] (E[X])²

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 ]

Nama yleistyvat 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 B(n; p), niin

Var[X] = np(1 p):

Tsebysevin ep ayht al o

Lause 3.3: Mille tahansa a > 0 patee

Pr(jX E[X]j a) Var[X]

a² :

Todistus: Kirjoitetaan arvioitava todennakoisyys muotoon Pr(jX E[X]j a) = Pr((X E[X])² a²)

ja sovelletaan ei-negatiiviseen satunnaismuuttujaan Y = (X E[X])² Markovin epayhtaloa:

Pr(Y a²) E[Y ]

a² = Var[X]

a² :

Esimerkki 3.4: Tarkastellaan samaa tilannetta kuin Markovin epayhtalon yhteydessa: Symmetrista rahaa heitetaan n kertaa. Milla todennakoisyydella kruunien lukumaara X on ainakin 3n=4?

Koska X on binomijakautunut, saadaan E[X] = n=2 ja Var[X] = n¹₂(1 ¹₂) = n=4. Siis

Pr(^{X n}₂ ⁿ₄⁾ Var[X]

(n=4)² = 4 n: Tilanteen symmetrisyyden takia

Pr(^{X n}₂ ⁿ₄^{) = 2 Pr(X n}₂ ⁿ₄^);

joten

Pr(X 3n

4 ) 2 n:

(Tamakin on itse asiassa erittain loysa raja, paljon parempi saadaan pian

Esimerkki 3.5: Kortinkeraajan ongelma (jatkoa Esimerkkiin 2.5).

Tarvittavien muropakkausten lukumaaran X odotusarvoksi saatiin nH(n).

Siis Markovin epayhtalosta seuraa

Pr(X 2nH(n)) 1 2:

Tsebysevin epayhtalon laskemiseksi tarvitaan varianssi Var[X]. Muistetaan etta X = P_n

i=1Xi missa Xi Geom(pi) ja pi = (n i + 1)=n.

Satunnaismuuttujan X Geom(p) varianssi on tunnetusti Var[X] = 1 p

p² :

Satunnaismuuttujat Xi ovat riippumattomia, joten Var[X] =

Xn

Var[Xi]:

Arvioimalla Var[Xi] 1=p²_i saadaan Xn

i=1

Var[Xi] Xn i=1

n n i + 1

₂

n² X1 i=1

1

i² = ²n² 6 : Siis Tsebysevin epayhtalosta seuraa

Pr(jX nH(n)j nH(n)) ²n²=6

(nH(n))² = O

1 (log n)²

:

Tamakaan ei ole kovin tiukka arvio. Todennakoisyys etta askeleeseen n(c + ln n) mennessa ei ole loydetty korttia i on

1 1

n

_{n(c+ln n)}

exp( (c + ln n)):

Todennakoisyys etta jotakin korttia ei ole loydetty askeleeseen n(c + ln n) mennessa on siis korkeintaan n exp( (c + ln n)) = e ^c. Sijoittamalla c = ln n saadaan

1

Satunnaistettu mediaanialgoritmi

Tarkastellaan yksinkertaisuuden vuoksi tapausta, jossa joukossa S on pariton maara erisuuria lukuja. Joukon S mediaani on siis joukon S jarjestyksessa (dn=2e):s alkio, missa n = jSj.

Mediaani voidaan maarittaa yksinkertaisesti jarjestamalla joukko ajassa O(n log n). Ongelmalle tunnetaan myos (monimutkaisehko) ajassa O(n) toimiva deterministinen algoritmi. Seuraavassa esitellaan yksinkertainen ajassa O(n) toimiva satunnaisalgoritmi.

Ideana on valita sopivalla satunnaismenetelmalla "alaraja" d 2 S ja "ylaraja"

u 2 S siten, etta suurella todennakoisyydella 1. mediaani on lukujen d ja u valissa ja

2. lukujen d ja u valissa on vain vahan joukon S lukuja.

Kun sivuutetaan toistaiseksi lukujen d ja u valintaperusteet, saadaan seuraava algoritmi:

1. Valitse d ja u.

2. Muodosta joukko C = f x 2 S j d x u g seka laske

`<sub>d</sub> = jf x 2 S j x < d gj ja `u = jf x 2 S j u < x gj.

3. Jos `<sub>d</sub> > n=2 tai `u > n=2 niin epaonnistu.

4. Jos jCj > 4n³⁼⁴ niin epaonnistu.

5. Muuten jarjesta joukko C ja palauta sen (bn=2c `_d + 1):s alkio.

Jos alkioiden d ja u valinta tapahtuu ajassa O(n), niin koko algoritmin aikavaatimus on selvasti O(n).

Jos algoritmi ei epaonnistu, se tuottaa selvasti oikean vastauksen.

Toistamalla sita kunnes onnistutaan saadaan siis Las Vegas -algoritmi, joka antaa aina oikea lopputuloksen mutta toisinaan vie paljon aikaa.

Analyysin mielenkiintoinen kohta on maarata d ja u siten, etta epaonnistumistodennakoisyys on pieni.

(Jatetaan jatkossa pyoristyksen merkitsematta.)

Lukujen d ja u valintamenetelma on seuraava:

1. Valitse (moni)joukko R S poimimalla tasaisesta jakaumasta (takaisinpanolla) n³⁼⁴ alkiota.

2. Jarjesta joukko R.

3. Nyt d on jarjestyksessa (¹₂n³⁼⁴ n¹⁼²):s joukon R alkio ja u jarjestyksessa (¹₂n³⁼⁴ + n¹⁼²):s.

Intuitiivisesti joukon R mediaani, eli jarjestyksessa (¹₂n³⁼⁴):s alkio, on samalla estimaatti koko joukon S mediaanille. Ensimmainen epaonnistumishaara

vastaa tilannetta, jossa tama estimaatti on mennyt pahasti pieleen.

Alkioiden d ja u valilla on 2n¹⁼² joukon R alkiota, joten jos otanta on ollut

"tasaista", niiden valilla on 2n¹⁼²(n=n³⁼⁴) = 2n³⁼⁴ joukon S alkiota. Toinen epaonnistumishaara vastaa tilannetta, etta otos on sattunut epatasaisesti.

Luvut n³⁼⁴, n¹⁼² jne. maaraytyvat siita, millaisia arvioita otantatarkkuudelle tunnetaan. (Toisin sanoen ne on valittu siten, etta seuraavat todistukset menevat lapi.)

Analysoidaan nyt epaonnistumistodennakoisyys tasmallisesti. Olkoon m joukon S mediaani ja k = jRj = n³⁼⁴. Muodostetaan kolme tapahtumaa:

E1 : jf r 2 R j r m gj < k

2 n¹⁼² E2 : jf r 2 R j r m gj < k

2 n¹⁼² E3 : jCj > 4k:

Tapahtuma E3 vastaa selvasti toista epaonnistumisehtoa.

Tapahtumat E1 ja E2 vastaavat tilanteita m < d ja m > u eli yhdessa kattavat ensimmaisen epaonnistumisvaihtoehdon.

Todennakoisyyden Pr(E1) arvioimiseksi merkitaan Y1 = jf r 2 R j r m gj.

Siis Y1 = P_k

i=1Xi missa 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 B(k; p) missa 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 Tsebysevin epayhtaloa:

Pr(E1) Pr(jY1 E[Y1]j > n¹⁼²) Var^[Y1]

n 1

4n ¹⁼⁴:

Samoin nahdaan

Pr(E2) 1

4n ¹⁼⁴:

Tapahtumaa E3 varten erotellaan kaksi osatapausta:

E3;1 : jf c 2 C j c > m gj 2k E3;2 : jf c 2 C j c < m gj 2k:

Jos jCj > 4k, niin ainakin toinen naista patee. Tapaukset ovat symmetriset.

Tarkastellaan tapausta E3;1. Talloin alkion u jarjestysnumero joukossa S on ainakin n=2 + 2k. Siis alkio u ja sita suuremmat otoksen R alkiot kuuluvat n=2 2k suurimman alkion joukkoon joukossa S. Alkion u maaritelman perusteella naita on k=2 n¹⁼² kappaletta.

Merkitaan Xi =

1 jos i:s otos kuuluu n=2 2k suurimman alkion joukkoon joukossa S 0 muuten

ja X = P_k

i=1Xi. Taas X on binomijakautunut, E[X] = k

2 2n¹⁼² ja

Var[X] = k 1

2 2n ¹⁼⁴ 1

2 + 2n ¹⁼⁴

< k 4 joten

Pr(E3;1) Pr(jX E[X]j n¹⁼²) Var[X]

n < 1

4n ¹⁼⁴: Siis kaikkiaan epaonnistumistodennakoisyys on korkeintaan

Pr(E ) + Pr(E ) + Pr(E ) + Pr(E ) < n ¹⁼⁴:

4. Chernon rajat

"Chernon raja" on yleisnimi joukolle epayhtaloita, jotka kertovat satunnaismuuttujan keskittymisesta odotusarvonsa ymparille.

Perusesimerkki: Kun X B(n; p), niin kaikilla 0 < 1 patee Pr

X np np

exp

1

3np²

: Tasta seuraa esim. etta todennakoisyydella 1=2

X np + p

3np ln 2:

Tata rajaa voidaan (a) tarkentaa ja (b) yleistaa.

Seuraavassa kaydaan lapi tamantyyppisia rajoja, niiden todistuksia ja sovelluksia.

Momenttigeneroiva funktio

Satunnaismuuttujan X momenttigeneroiva funktio on MX(t) = E[e^tX]

(mikali tama odotusarvo on aarellinen). Derivoimalla momenttigeneroiva funktio origossa n kertaa saadaan satunnaismuuttujan n:s momentti:

Lause 4.1: Jos Mx(t) on maaritelty jossain origon ymparistossa t 2 ( ; ), niin

E[Xⁿ] = M_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 termeittain:

M⁽ⁿ⁾(t) = X

Pr(X = x)xⁿexp(tx):

Esimerkki 4.2: Kun X Geom(p), niin E[e^tX] =

X1 k=1

(1 p)^{k 1}pe^tk

= p

1 p X1 k=1

((1 p)e^t)^k

= p

1 p

1

1 (1 p)e^t 1

mista derivoimalla saadaan

M_X⁰ (t) = pe^t

(1 (1 p)e^t)² M_X⁰⁰(t) = 2p(1 p)e^2t

(1 (1 p)e^t)³ + pe^t

(1 (1 p)e^t)²:

Voidaan osoittaa (mutta talla kurssilla ei osoiteta), etta momenttigeneroiva funktio (tai kaikki momentit) spesioi todennakoisyysmuuttujan jakauman yksikasitteisesti:

Lause 4.3: Jos X ja Y ovat satunnaismuuttujia joille jollain > 0 patee MX(t) = MY(t) kaikilla < t < , niin satunnaismuuttujilla X ja Y on sama jakauma.

Tata voidaan kayttaa esim. kahden satunnaismuuttujan tulon jakauman maarittamiseen yhdessa seuraavan kanssa:

Lause 4.4: Jos X ja Y ovat riippumattomia, niin MX+Y(t) = MX(t)MY(t):

Todistus: Talloin myos e^tX ja e^tY ovat riippumattomia, joten E[e^{t(X+Y )}] = E[e^tXe^tY] = E[e^tX]E[e^tY]:

Siirrytaan nyt itse Chernon rajoihin. Idea on soveltaa Markovin epayhtaloa satunnaismuuttujaan e^tX sopivalla t.

Markovin epayhtalosta saadaan

Pr(X a) = Pr(e^tX e^ta) E[e^tX] e^ta milla tahansa t > 0, eli erityisesti

Pr(X a) min

t>0

E[e^tX] e^ta : Samoin myos

Pr(X a) min

t>0

E[e^tX] e^ta :

Idean soveltamiseen tarvitaan arvio momenttigeneroivalle funktiolle E[e^tX] ja sopiva t:n arvo.

Yleisimmin kaytetyssa versiossa X = P_n

i=1Xi missa Xi Bernoulli(p_i) ovat riippumattomia. Satunnaismuuttujia Xi sanotaan Poisson-toistokokeiksi. Jos jakaumat ovat identtiset, pi = p kaikilla i, puhutaan Bernoulli-toistokokeista.

Merkitaan = E[X] = P_n

i=1 pi. Yritamme arvioida todennakoisyyksia Pr(X (1 + )) ja Pr(X (1 )).

Arvioidaan ensin yksittaisten toistokokeiden momenttigeneroivaa funktiota:

M_Xi(t) = pie^t1 + (1 pi)e^t0 = 1 + pi(e^t 1) exp(pi(e^t 1)):

Tasta saadaan MX(t) =

Yn i=1

MXi(t) exp

Xn i=1

pi(e^t 1)

!

= exp (e^t 1) :

Johdamme seuraavaksi erikseen rajat todennakoisyyksille, etta X on hyvin suuri tai hyvin pieni.

Todistetaan ensin perusraja, joka on (suhteellisen) tiukka mutta hankala.

Tasta voidaan sitten johtaa yhsinkertaistettuja (ja loysempia) versioita.

Lause 4.5: Kaikille > 0 patee

Pr(X (1 + )) <

e

(1 + )¹⁺

:

Todistus: Kuten edella todettiin, Markovin epayhtalosta saadaan Pr(X (1 + )) = Pr(e^tX e^t(1+)) E[e^tX]

exp(t(1 + )): Valitaan t = ln(1 + ), jolloin

E[e^tX] exp((e^t 1)) = e ja

exp(t(1 + )) = (1 + )⁽¹⁺⁾:

Seuraava on usein kaytetty yksinkertaistus:

Lause 4.6: Kun 0 < 1, niin

Pr(X (1 + )) exp( ²=3):

Todistus: Riittaa siis osoittaa

e

(1 + )¹⁺ e ²⁼³

eli yhtapitavasti (ottamalla logaritmi puolittain) f() 0 missa f() = (1 + ) ln(1 + ) + 1

3²:

Derivoidaan:

f() = (1 + ) ln(1 + ) + 1 3² f⁰() = ln(1 + ) + 2

3 f⁰⁰() = 1

1 + + 2 3:

Nyt f⁰⁰() < 0 valilla 0 < 1=2, eli f⁰() pienenee. Toisaalta f⁰⁰() > 0 valilla 1=2 < < 1, eli f⁰() kasvaa.

Koska f⁰(0) = 0 ja f⁰(1) = 2=3 ln 2 < 0, patee f⁰() 0 Koska f(0) = 0, patee f() 0 kaikilla 0 < < 1.

Toinen tapa yksinkertaistaa rajaa on seuraava:

Lause 4.7: Kun R 6, niin

Pr(X R) 2 ^R:

Todistus: Merkitaan R = (1 + ), jolloin = R= 1 5. Saadaan e

(1 + )¹⁺

e 1 +

₍₁₊₎

_e

6 _R 2 ^R:

Tarkastellaan sitten tapausta, etta X on hyvin pieni.

Lause 4.8: Kaikilla 0 < < 1 patee

Pr(X (1 ))

e (1 )¹

: Todistus: Kuten aiemmin,

Pr(X (1 )) E[e^tX]

e^{t(1 )} exp((e^t 1)) exp(t(1 )): Haluttu arvio saadaan sijoittamalla t = ln(1 ).

Tata voidaan arvioida kuten toisessakin tapauksessa:

Lause 4.9: Kaikilla 0 < < 1 patee

Pr(X (1 )) exp( ²=2):

Todistus: Samalla tekniikalla kuin tapaus "(1 + )", yksityiskohdat sivuutetaan.

Arviot voidaan yhdistaa:

Korollaari 4.10: Kaikilla 0 < < 1 patee

Pr(jX j ) 2 exp( ²=3):

Esimerkki 4.11: Heitetaan symmetrista rahaa n kertaa. Siis = n=2.

Millainen raja patee todennakoisyydella 2=n (siis hyvin todennakoisesti)?

Halutaan exp( (n=2)²=3) = 1=n, mista = p

(6 ln n)=n. Sijoittamalla tama rajaan saadaan

Pr

^{X n}

2 ¹₂^{p6n ln n}

2 n: Siis melko varmasti poikkeamat ovat O(p

n log n).

Verrataan Tsebysevin epayhtalolla saatuun arvioon Pr^{X n}₂ ⁿ₄

4 n:

Jos otetaan Cherno-arvio samalle virheen suuruudelle, saadaan Pr^{X n}₂ ⁿ₄

2e ⁿ⁼²⁴

Sovellus: parametrin estimointi

Suoritetaan riippumattomia toistoja tuntemattomasta (mutta samana pysyvasta) jakaumasta Bernoulli(p). Halutaan arvioida parametria p.

Olkoon X = P_n

i=1Xi onnistumisten lukumaara n toistossa ja ~p = X=n.

Selvasti E[~p] = =n = p. Mita voidaan sanoa virhetodennakoisyyksista?

Vali [~p ; ~p + ] on (1 )-luottamusvali parametrille p, jos Pr(p 2 [~p ; ~p + ]) 1 :

Tulkinta: Nahtyamme koesarjan, jonka onnistumisfrekvenssi on ~p, meilla on

"luottamus" 1 siihen, etta oikea parametri p on valilla [~p ; ~p + ]. Jos nain ei olisi, niin havaitunlaisten koesarjojen todennakoisyys olisi alle .

Huom. p on vakio, silla ei ole mitaan todennakoisyytta (ellemme sitten oleta jotain priorijakaumaa ja tee bayeslaista analyysia.

Jos p 62 [~p ; ~p + ], niin toinen seuraavista on tapahtunut:

p < ~p : siis X = n~p > n(p + ) = (1 + =p).

p > ~p + : siis X = n~p < n(p ) = (1 =p).

Chernon rajoista saadaan

Pr(p 62 [~p ; ~p + ]) e ^(=p)2=2 + e ^(=p)2=3 = e ^n2=(2p) + e ^n2=(3p): Koska p ei ole tiedossa, kaytetaan ylarajaa p 1, jonka perusteella voidaan valita

= e ⁿ²⁼² + e ⁿ²⁼³

(tai kaantaen ratkaista tasta , kun on valittu ja n tunnetaan).

Tarkempia rajoja erikoistapauksille

Tarkastellaan tassa joitain tilanteita, joissa Xi on symmetrisesti jakautunut.

Lause 4.12: Jos Pr(Xi = 1) = Pr(Xi = 1) = 1=2, niin kaikilla a > 0 patee Pr(X a) exp

a² 2n

:

Todistus: Kaikilla t > 0 patee

E[e^tXi] = 1

2e^t + 1 2e ^t: Sijoitetaan tahan

e^t =

X1 _t^j

j!:

Siis saadaan E[e^tXi] = 1

2

1 + t + t²

2 + t³

3! + t⁴

4! + : : :

+ 1 2

1 t + t² 2

t³

3! + t⁴

4! : : :

= 1 + t²

2 + t⁴

4! + : : :

=

X1 j=0

t^2j (2j)!

X1 j=0

1 j!

t² 2

_j

= exp t²

2

:

Siis

E[e^tX] = Yn i=1

E[e^tXi] exp

t²n 2

; joten

Pr(X a) E[e^tX]

e^ta exp

t²n

2a ta

: Valitsemalla t = a=n saadaan haluttu

Pr(X a) exp

a² 2n

:

Korollaari 4.13: Jos Pr(Xi = 1) = Pr(Xi = 1) = 1=2, niin kaikilla a > 0 Pr(jXj a) 2 exp

a² 2n

:

Korollaari 4.14: Olkoot Yi riippumattomia ja

Pr(Yi = 1) = Pr(Yi = 0) = 1=2. Merkitaan Y = P_n

i=1Yi ja = E[Y ] = n=2.

Nyt kaikilla a > 0 patee

Pr(Y + a) exp

2a² n

ja kaikilla > 0 patee

Pr(Y (1 + )) exp ² :

Todistus: Olkoot Xi kuten aiemmin ja Yi = ¹₂(Xi + 1). Siis erityisesti Y = ¹₂X + .

Edellisesta lauseesta seuraa

Pr(Y + a) = Pr(X 2a) exp

4a² 2n

: Toista osaa varten valitaan a = , jolloin

Pr(Y (1 + )) = Pr(X 2) exp

4²² 2n

= exp ² :

Samoin todistetaan

Korollaari 4.15: Olkoot Yi riippumattomia ja

Pr(Yi = 1) = Pr(Yi = 0) = 1=2. Merkitaan Y = P_n

i=1Yi ja = E[Y ] = n=2.

Nyt kaikilla 0 < a < patee

Pr(Y a) exp

2a² n

ja kaikilla > 0 patee

Sovellus: joukon tasapainotus

On annettu m henkiloa ja n ominaisuutta. Tehtavana on osittaa henkilot kahteen joukkoon A ja A s.e. kaikilla j = 1; : : : ; n

jf p 2 A j p:lla on ominaisuus i gj p 2 A j p:lla on ominaisuus i :

Maaritellaan taulukko A = (aij) 2 f 0; 1 g^nm missa aij = 1 jos henkilolla j on ominaisuus i.

Esitetaan ositus (A; A) vektorina b 2 f 1; 1 g^m, missa bj = 1 jos henkilo j on joukossa A.

Nailla merkinnoilla tehtavana on siis minimoida suure kAbk₁ = max

i jcij missa ci = P

aijbj.

Miten hyvin onnistutaan, jos b valitaan satunnaisesti s.e. kukin bj on 1 todennakoisyydella 1=2 toisistaan riippumatta?

Vaitetaan, etta

Pr(kAbk₁ p

4m ln n) 2 n:

Osoitetaan tama nayttamalla jokaiselle yksittaiselle riville i 2 f 1; : : : ; n g etta tapahtuman jcij p

4m ln n todennakoisyys on korkeintaan 2=n². Merkitaan k = P

j aij. Jos k p

4m ln n, vaite on selva.

Muuten, koska aijbj saa arvoja 1 ja 1 symmetrisesti ja riippumattomasti, niin

Pr 0

@ X

j

aijbj

^{> p4m ln n} 1

A _{2 exp}

4m ln n 2k

2

n²

Esimerkki: pakettien reititys

Verkossa on N solmua, joista joidenkin valilla on kaari. Kaaret ovat

seuraavassa suunnattuja, mutta tarkastelemissamme topologioissa yhteydet ovat symmetrisia (kaari (v; v⁰) olemassa joss (v⁰; v) on).

Tehtavana on valittaa verkkoa pitkin joukko paketteja, joista jokaisella on annettu alkupiste ja osoite (jotka ovat verkon solmuja). Paketin reitti on sille valittu verkon polku haluttujen solmujen valilla.

Yhden aikayksikon aikana

kukin paketti voi edeta korkeintaan yhden kaaren verran ja

kutakin kaarta pitkin voidaan lahettaa korkeintaan yksi paketti.

Solmuissa on (riittavasti) puskuritilaa paketeille, jotka odottavat

Verkon toiminnan maaraamiseksi pitaa kiinnittaa,

miten reitti valitaan, kun lahto- ja maalisolmut on annettu ja

missa jarjestyksessa samaa kaarta tarvitsevat paketit paasevat eteenpain (jonotus).

Tassa esiteltavien tulosten kannalta ei ole tarkeaa, miten jonotus hoidetaan, kunhan vain kaarten ei anneta olla joutilaina.

Verkon ruuhkautuminen riippuu tietysti siita, minka solmujen valilla paketteja lahetetan. Tarkastelemme seuraavassa tilanteita, joita syntyy permutaatioreitityksesta: jokainen solmu on seka lahtosolmuna etta maalisolmuna tasan yhdelle paketille.

Reititysongelma on kiinnostava lahinna, jos verkko on harva (kaaria paljon alle N(N 1)). Tarkastelemme esimerkkitopologiana hyperkuutiota. Tassa N = 2ⁿ, ja samastamme solmut joukon f 0; 1 gⁿ alkioiden kanssa.

Hyperkuutiossa solmujen (a1; : : : ; an) ja (b1; : : : ; bn) valilla on kaari, jos on tasan yksi indeksi i jolla ai 6= bi.

Hyperkuutiossa on siis 2N log₂N kaarta, ja verkon halkaisija (pisin kahden solmun etaisyys) on log₂ N.

Lahtokohta reititykseen hyperkuutiossa on bitinkorjausalgoritmi.

Tarkastellaan pakettia, jonka lahtosolmu on a = (a1; : : : ; an) ja maalisolmu b = (b1; : : : ; bn). Kun i = 1; : : : ; n + 1, maaritellaan

vi = (b1; : : : ; bi 1; ai; : : : ; an):

Paketin polku kulkee nyt solmujen a = v1; v2; : : : ; vn+1 = b kautta.

(Kyseisesta solmulistasta saadaan varsinainen polku jattamalla pois toistuvat solmut, joita esiintyy kun ai = bi.)

Siis paketin "osoite korjataan" bitti kerrallaan, vasemmalta alkaen.

Bitinkorjausalgoritmi toimii hyvin keskimaaraisessa tapauksessa, kun maalisolmut valitaan satunnaisesti. Osoittautuu kuitenkin, etta joissain tapauksissa se johtaa ruuhkautumiseen ja vaatii ajan (N¹⁼²).

Bitinkorjauksen pahimpien tapausten valttamiseksi tarkastelemme satunnaistettua kaksivaiheista reititysta.

Vaihe I: Valitse jokaiselle paketille satunnainen solmu "valitavoitteeksi".

Reitita paketit valitavoitteisiinsa bitinkorjauksella.

Vaihe II: Reitita paketit valitavoitteista lopullisiin tavoitteisiinsa bitinkorjauksella.

Osoitamme, etta todennakoisyydella 1 O(N ¹) kaksivaiheinen reititys onnistuu ajassa O(log N). Koska log₂N on verkon halkaisija, tama on (jollain tarkkuudella) optimaalista.

Se, milloin jokin paketti ylittaa tietyn reitilleen kuuluvan kaaren, riippuu tietysti siita, missa jarjestyksessa jonoja puretaan.

Analyysin yksinkertaistamiseksi olkoon T (M) aika, joka paketilta M kuluu maalinsa saavuttamiseen. Jokainen naista T (M) aika-askelista kuluu

jompaan kumpaan seuraavista:

1. paketti M ylittaa jonkin kaaren reitillaan tai

2. paketti M odottaa jonossa kun jokin toinen paketti ylittaa sen tarvitsemaa kaarta.

Olkoon X(e) niiden pakettien lukumaara, joiden reittiin kaari e kuuluu.

Edellisen perusteella tehdaan

Havainto: Jos paketin M reitti koostuu kaarista e1; : : : ; em, niin T (M)

Xm

X(e ):

Edellinen havainto sallii meidan keskittya polkujen analysoimiseen ja unohtaa jonotuskayttaytyminen jne. Kun P on polku, joka koostuu kaarista

e1; : : : ; em, maaritellaan

T (P ) = Xm i=1

X(ei):

Edellisen havainnon perusteella minka tahansa reitityksen viema aika on korkeintaan maxP 2RT (P ), missa R on reititykseen kuuluvien polkujen joukko.

Huomaa, etta edellinen patee mihin tahansa reititystilanteeseen. Olkoot erityisesti T1 ja X1 suureet T ja X kun rajoitutaan satunnaisen

kaksivaihereitytyksen vaiheeseen I. Osoitamme, etta suurella todennakoisyydella T (P ) 30n kaikilla mahdollisilla reiteilla P .

Kiinnitetaan nyt jokin polku P = (v0; : : : ; vm), joka on mahdollinen paketin reitti bitinkorjausalgoritmia kaytettaessa.

Haluamme suurella todennakoisyydella patevan rajan summalle T1(P ) = P_m

i=1X1(ei). Koska satunnaismuuttujat X1(ei) eivat ole riippumattomia, Chernon rajoja ei voi suoraan soveltaa.

Ongelman ratkaisemiseksi arvioimme ensin todennakoisyytta, etta vahintaan 6n eri pakettia ylittaa jonkin polun P kaaren.

Taman jalkeen osoitetaan, etta suurella todennakoisyydella mikaan yksittainen paketti ei kayta kovin monta kaarta polulla P .

Olkoon vi 1 solmu polulla P , ja j se bitti jonka osalta vi 1 ja vi poikkeavat.

Sanomme, etta paketti k on aktiivinen solmussa vi 1, jos 1. paketti k kulkee solmun vi 1 kautta, ja

2. paketin k tullessa solmuun vi 1 sen bittia j ei ole viela "korjattu".

Kun k = 1; : : : ; N, merkitaan H_k = 1 jos paketti k on aktiivinen jossain polun P solmussa. Olkoon H = P_N

k=1 H_k.

Olkoon

vi 1 = (b1; : : : ; bj 1; aj; aj+1; : : : ; an) vi = (b1; : : : ; bj 1; bj; aj+1; : : : ; an):

Ehdon 2 mukaan solmussa vi 1 aktiivisen paketin lahtosolmu on muotoa (; : : : ; ; aj; : : : ; an). Siis mahdollisia lahtosolmuja on 2^{j 1}.

Ehdon 1 mukaan solmussa vi 1 aktiivisen paketin maalisolmu on muotoa (b1; : : : ; bj 1; ; : : : ; ). Siis mahdollisen lahtosolmun paketista tulee aktiivinen todennakoisyydella 2 ^j+1.

Siis solmussa vi 1 aktiivisten pakettien maaran osotusarvo on 1, joten E[H] m 1 n:

Koska satunnaismuuttujat H_k ovat riippumattomia, voimme soveltaa Chernon rajaa (lause 4.7):

Pr(H 6n) 2 ⁶ⁿ: Valitsemme nyt B = f H 6n g arviossa

Pr(A) = Pr(A j B) Pr(B) + Pr(A j B) Pr(B) Pr(B) + Pr(A j B):

Siis

Pr(T1(P )) 30n) 2 ⁶ⁿ + Pr(T1(P ) 30n j H < 6n):

Arvioidaan seuraavaksi jalkimmaista ehdollista todennakoisyytta.