Prosjekt 5
Veke 15. Test av slumptalsgeneratorar
9.2. Veke 15. Test av slumptalsgeneratorar
9.2.2 Frå intuisjon til statistisk hypotesetest
9.2.3 -testen
9.2.4 Nullhypotesar for uavhengig fordeling
9.2.5 Testing for uavhengig fordeling
9.2.6 Meir lesing
I denne øvinga skal me sjå på eit klassisk problem i informatikk: statistisk testing av slumptalsgeneratorar. Me har allereie studert fordelinga frå ulike slumptalsgeneratorar og sett at nokon er svært dårlege og andre mindre dårlege, men det heile har vore skjønn og synsing.
I denne øvinga skal me bruka statistikk til å vurdera kvaliteten på slumptalsgeneratorar. Dette føreset at de har lært hypotesetesting gjennom rekneøvingane. Eg tek gjerne ein prat om korleis me får dei statistiske modellane til å passa saman med det praktiske problemet med slumptalsgeneratorar. Ikkje nøl med å spørja om du sit fast. Eg har ikkje gjeve nokon detaljert oppskrift, simpelthen fordi de treng å vera med på prosessen, men de treng ikkje ta han aleine.
All bruk av slumptalsgeneratorer byggjer på ein hypotese:
Dette er ein hypotese som me kan testa.
9.2.1. Rafinering av nullhypotesen (Fyrste omgang)
Me skal bruka -testen. Før me ser på korleis me utfører han, skal me sjå på kva utval me treng, og finna hypotesar som me kan bruka.
Nullhypotesen over er føreset to ting; at slumptala er (1) uavhengige og (2) uniformt fordelte. I fyrste omgang skal me fokusera berre på fordelinga, og sjå på hypotesen
Dersom er sann, so er sann. Dersom me forkastar må me forkasta . Me skal koma tilbake til uavhenge seinare.
Føresetnaden for -testen er at me kan trekkja eit utval som er mange gongar større enn utfallsrommet.
Dvs. at me kan ikkje bruka heile utfall frå slumptalsgeneratoren direkte. Då er utfallsrommet altfor stort. Me kan derimot slå saman utfall for å skapa eit mindre utfallsrom.
Døme 14 Lat vera eit slumptal frå generatoren, og lat . Hypotesen vår er
Dersom denne hypotesen er sann, er det òg sant at
Utfallsrommet åt er , altso 16 element. Det kan me bruka.
I eksempelet tek me ein nullhypotese som testar dei fire minst signifikante bitsa i slumptalet. Me kan trekkja ut, og testa på, ein kvan bitmaske. Dersom slumptala er uniformt fordelte, vil alle bitmaskar òg vera uniformt fordelte.
(OK. Der er eit aber. Dersom storleiken på utfallsrommet for ikkje er deleleg med 16, fordeler ikkje tala seg jamnt. Der vil vera eitt tal meir som vert 1 modulo 16 enn dei som vert 0. Dette kan me sjå bort frå dersom utfallsrommet er stort og me maskar ut få bits.)
9.2.2. Frå intuisjon til statistisk hypotesetest
Me skal starta med å testa frå døme . Dersom du trekk eit par hundre slumptal og reknar ut , kan du plotta observasjonar av i eit histogram. Visuelt kan du so vurdera om verkar rimeleg.
Dersom histogrammet ikkje ser ut som ei uniform fordeling, er det rimeleg å tru at det ikkje er generert av ei uniform fordeling, og hypotesen er usann. Me går då ut frå at slumptalsgeneratoren er dårleg.
Dersom histogrammet ser ut som ei uniform fordeling, er det rimeleg å gå ut frå at hypotesen er sann, og me generatoren har i alle fall ikkje denne dårlege eigenskapen.
Den visuelle vurderinga er derimot reint skjønn. Synsing vil nokon seia. For å gjera ein objektiv vurdering ynskjer me enkle kvantitative svar.
9.2.3. -testen
Lat oss ta utgangspunkt i histogrammet igjen. Lat vera utvalet vårt, dvs. ei fylgje av slumptal modulo 16.
- 1.
- Lat
vera frekvensen av verdien
i utvalet.
Dvs. , for er talet på gongar førekjem i utvalet. Histogrammet plottar for kvar .
- 2.
- Lat
vera forventingsverdien til ,
dersom hypotesen vår er sann.
Hypotesa seier uniform fordelinga, og då er der er storleiken på utvalet.
- 3.
- Me reknar ut den stokastiske variabelen
Variabelen er eit standardverkty for å samanlikna ein empirisk fordeing () med ein hypotetisk fordeling (uniform i dette tilfellet). Det er lettare å sjå avvik i ein enkelt skalarvariabel , enn å sjå på heile histogrammet med seksten forskjellige frekvensar.
Oppgåve 9.19 Sjå på uttrykket for . Kva verdiar kan ta? Korleis ser histogrammet ut når tek minste mogleg verdi?
Oppgåve 9.20 Kva verdiar ventar du at har når hypotesen om uniform fordeling held? Kva når ho ikkje held?
Oppgåve 9.21 Bruk rng1.m frå avsnitt 5.3 og lag eit utval på tilfeldige tal modulo 16. Finn frekvensane vha. funksjonen
1f = histcounts(y,’BinMethod’,’integers’)
Rekna ut
som forklart over. Kva verdi får du?
Gjer det same for rng2.m.
Oppgåve 9.22 Variabel er stokastisk med -fordeling med 15 fridomsgradar. Plott sannsynsfordelinga
1fplot( @(x)chi2pdf(x,15), [0 40] )
Det merkelege uttrykket @(x)chi2pdf(x,15) er eit lambdauttrykk og lagar ein ny funksjon med ein
parameter
vha. den eksisterande funksjonen som har 2.
Samanlikna observasjonar av frå forrige oppgåve med sannsynsfordelinga. Synest du observasjonane dine ser sannsynlege ut dersom slumptala er uniformt fordelte?
Oppgåve 9.23 Rekn ut -verdien frå testane av rng1.m og rng2.m. Kva kan du seia om kvaliteten på dei to slumptalsgeneratorane? (Der er -tabell i læreboka.)
9.2.4. Nullhypotesar for uavhengig fordeling
Lat oss gå tilbake til urhypotesen vår
Når me krev uavhengig fordeling, rekk det ikkje å sjå på éin verdi . Me må sjå på ein serie med verdiar .
Dersom er sann, so er det òg sant at
Dersom og er uavhengig og uniformt fordelt, so vil det seia at parret er uniformt fordelt. Likeeins vil tuplar vera uniformt fordelte. Me kan difor danna hypotesen
Dersom er sann, so må vera sann.
Utfallsrommet er no sjølvsagt altfor stort, men me kan kombinera med modulustrikset som me brukte i stad. No er og to stokastiske variablar. Me kan definera
Effektivt tek me då to bits frå og to bits frå og set dei saman til eit firebits tal. Utfallsrommet er altso 16 element som før.
Dersom er sann, er det altso sant at
Denne hypotesen kan testast på same måte som . Det er berre som er rekna ut på ein litt annan måte.
9.2.5. Testing for uavhengig fordeling
Oppgåve 9.24 Gjenta oppgåvene i avsnitt 9.2.3 med utgangspunkt i og i staden for og .
9.2.6. Meir lesing
Det er verd å lesa Donald Knuths klassikar, The Art of Computer Programming. I band 2, Seminumerical Algorithms, har han eit kapittel om slumptalsgeneratorar, med ei rekkje døme på statistiske testar.