Statistikk og Simulering

Prosjekt 5

Test av slumptalsgeneratorar

9.1. Test av slumptalsgeneratorar

  9.1.1 χ2-testen

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.

All bruk av slumptalsgeneratorer byggjer på ein hypotese:

H0 : slumptala er uniformt fordelte

Dette er ein hypotese som me kan testa.

9.1.1. χ2-testen

Dersom denne hypotesen er sann, so er det òg sant at slumptala modulo 16 er sann. Når me ser på datamaterialet, i form av eit histogram, kan me vurdera om denne hypotesen er rimeleg eller ikkje.

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.

Slik visuell vurderinga av datamaterialet vert mykje synsing. For å gjera ein objektiv vurdering ynskjer me enkle kvantitative svar.

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.1 Sjå på uttrykket for G. Kva verdiar kan G ta? Korleis ser histogrammet ut når G tek minste mogleg verdi?

Oppgåve 9.2 Kva verdiar ventar du at G har når hypotesen om uniform fordeling held? Kva når ho ikkje held?

Oppgåve 9.3 Bruk rng1.m som i førre avsnitt 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.4 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 dine observasjonar av G frå forrige oppgåve med sannsynsfordelinga. Synest du observasjonane dine ser sannsynlege ut dersom slumptala er uniformt fordelte?