Statistikk og Simulering

Prosjekt 5

Veke 15. Test av slumptalsgeneratorar

9.2. Veke 15. Test av slumptalsgeneratorar

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:

H0 : slumptala er uavhengige og uniformt fordelte

Dette er ein hypotese som me kan testa.

9.2.1. Rafinering av nullhypotesen (Fyrste omgang)

Me skal bruka χ2-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

H0(1) : slumptala er uniformt fordelte

Dersom H0 er sann, so er H0(1) sann. Dersom me forkastar H0(1) må me forkasta H0. Me skal koma tilbake til uavhenge seinare.

Føresetnaden for χ2-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 X vera eit slumptal frå generatoren, og lat Y = Xmod 16. Hypotesen vår er

H0(1) : X er uniformt fordelt

Dersom denne hypotesen er sann, er det òg sant at

H0(2) : Y  er uniformt fordelt

Utfallsrommet åt Y er {0, 1,, 15}, 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 X 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 H0(2) frå døme . Dersom du trekk eit par hundre slumptal X og reknar ut Y , kan du plotta observasjonar av Y i eit histogram. Visuelt kan du so vurdera om H0(2) 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. χ2-testen

Lat oss ta utgangspunkt i histogrammet igjen. Lat [y1,y2,,yn] vera utvalet vårt, dvs. ei fylgje av slumptal modulo 16.

1.
Lat Fy vera frekvensen av verdien y i utvalet.

Dvs. Fy, for 0 y 15 er talet på gongar y førekjem i utvalet. Histogrammet plottar Fy for kvar y.

2.
Lat Ey vera forventingsverdien til Fy, dersom hypotesen vår er sann.

Hypotesa seier uniform fordelinga, og då er Ey = n16 der n er storleiken på utvalet.

3.
Me reknar ut den stokastiske variabelen
G = y=015(Fy Ey)2 Ey .

Variabelen G er eit standardverkty for å samanlikna ein empirisk fordeing (Fu) med ein hypotetisk fordeling (uniform i dette tilfellet). Det er lettare å sjå avvik i ein enkelt skalarvariabel G, enn å sjå på heile histogrammet med seksten forskjellige frekvensar.

Oppgåve 9.19 Sjå på uttrykket for G. Kva verdiar kan G ta? Korleis ser histogrammet ut når G tek minste mogleg verdi?

Oppgåve 9.20 Kva verdiar ventar du at G 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å n = 1000 tilfeldige tal modulo 16. Finn frekvensane Fy vha. funksjonen

1f = histcounts(y,’BinMethod’,’integers’) Rekna ut G som forklart over. Kva verdi får du?

Gjer det same for rng2.m.

Oppgåve 9.22 Variabel G er stokastisk med χ2-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 x vha. den eksisterande funksjonen som har 2.

Samanlikna observasjonar av G frå forrige oppgåve med sannsynsfordelinga. Synest du observasjonane dine ser sannsynlege ut dersom slumptala er uniformt fordelte?

Oppgåve 9.23 Rekn ut p-verdien frå testane av rng1.m og rng2.m. Kva kan du seia om kvaliteten på dei to slumptalsgeneratorane? (Der er χ2-tabell i læreboka.)

9.2.4. Nullhypotesar for uavhengig fordeling

Lat oss gå tilbake til urhypotesen vår

H0 : slumptala er uavhengige og uniformt fordelte

Når me krev uavhengig fordeling, rekk det ikkje å sjå på éin verdi X. Me må sjå på ein serie med verdiar X1,,Xn.

Dersom H0 er sann, so er det òg sant at

H0(3) : X i er uavhengig og uniformt fordelt

Dersom X1 og X2 er uavhengig og uniformt fordelt, so vil det seia at parret (X1,X2) er uniformt fordelt. Likeeins vil tuplar (X1,,Xn) vera uniformt fordelte. Me kan difor danna hypotesen

H0(4) : (X 1,X2) er uniformt fordelt

Dersom H0(3) er sann, so må H0(4) vera sann.

Utfallsrommet er no sjølvsagt altfor stort, men me kan kombinera med modulustrikset som me brukte i stad. No er X1 og X2 to stokastiske variablar. Me kan definera

Y = 4 (X 1 mod 4) + (X2 mod 4)

Effektivt tek me då to bits frå X1 og to bits frå X2 og set dei saman til eit firebits tal. Utfallsrommet er altso 16 element som før.

Dersom H0(4) er sann, er det altso sant at

H0(5) : Y  er uniformt fordelt

Denne hypotesen kan testast på same måte som H0(2). Det er berre Y 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 reflabelsec:chi2a med utgangspunkt i Y og H0(5) i staden for Y og H0(2).

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.