Prosjekt 5

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:

Dette er ein hypotese som me kan testa.

9.2.1. Rafinering av nullhypotesen (Fyrste omgang)

Me skal bruka ${\chi }^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

Dersom $H_0$ er sann, so er $H_0^{\left(1\right)}$ sann. Dersom me forkastar $H_0^{\left(1\right)}$ må me forkasta $H_0$. Me skal koma tilbake til uavhenge seinare.

Føresetnaden for ${\chi }^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.

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 $H_0^{\left(2\right)}$ 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 $H_0^{\left(2\right)}$ 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. ${\chi }^2$-testen

Lat oss ta utgangspunkt i histogrammet igjen. Lat $\left[y_1,y_2,\dots ,y_n\right]$ vera utvalet vårt, dvs. ei fylgje av slumptal modulo 16.

1.

Lat $F_y$ vera frekvensen av verdien $y$ i utvalet.

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

2.

Lat $E_y$ vera forventingsverdien til $F_y$, dersom hypotesen vår er sann.

Hypotesa seier uniform fordelinga, og då er $E_y=n∕16$ der $n$ er storleiken på utvalet.

3.

Me reknar ut den stokastiske variabelen

$$G=\sum _{y=0}^{15}\frac{{\left(F_y-E_y\right)}^2}{E_y}.$$

Variabelen $G$ er eit standardverkty for å samanlikna ein empirisk fordeing ($F_u$) 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.

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 $X$. Me må sjå på ein serie med verdiar $X_1,\dots ,X_n$.

Dersom $H_0$ er sann, so er det òg sant at

Dersom $X_1$ og $X_2$ er uavhengig og uniformt fordelt, so vil det seia at parret $\left(X_1,X_2\right)$ er uniformt fordelt. Likeeins vil tuplar $\left(X_1,\dots ,X_n\right)$ vera uniformt fordelte. Me kan difor danna hypotesen

Dersom $H_0^{\left(3\right)}$ er sann, so må $H_0^{\left(4\right)}$ vera sann.

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

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

Dersom $H_0^{\left(4\right)}$ er sann, er det altso sant at

Denne hypotesen kan testast på same måte som $H_0^{\left(2\right)}$. Det er berre $Y$ som er rekna ut på ein litt annan måte.

9.2.5. Testing for uavhengig fordeling

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.