Statistikk og Simulering

Øktene 26. april til 11. mai

11. mai

22.7. 11. mai

  22.7.1 Felles
  22.7.2 Løysingsforslag
  Oppgåve 22.1
  Oppgåve 22.2
  22.7.3 Eigenarbeid

22.7.1. Felles

Desse to oppgåvene handlar slumptal og χ2-testen som ikkje har vore pensum før. Dei er formulerte som typiske eksamensoppgåver, og liknande oppgåver er sannsynleg på eksamen.

Oppgåve 22.1 Mange dataprogram treng tilfeldige tal. Ein vanleg måte å generera slike slumptal er den lineære kongruensgeneratoren

xi = a xi1 + c(modm).

For eit gjeve frø x0, gjev rekurrensen ei fylgje [x1,x2,x3] som vert brukt som tilfeldige tal.

1.
Forklar kva me meiner med at eit tal (eller hending) er tilfeldig.
2.
Under kva omstende gjev den lineære kongruensgeneratoren tilfredsstillande slumptal?

Ta a = 6, c = 7, og m = 25, og studer generatoren

xi = 6 xi1 + 7(mod 25).

3.
Kva er perioden til denne generatoren med frøet x0 = 11?
4.
På kva måtar lyt ein ta omsyn til perioden ved praktisk bruk av generatoren?

Oppgåve 22.2 Det er vanleg å testa kvaliteten på ein slumptalsgenerator ved hjelp av statistisk hypotesetesting. Lat [x1,x2,,xn] vera ein heiltalsfylgje frå slumptalsgeneratoren. For å testa at dei fire siste bitsa er uniformt fordelte kan me bruka χ2-statistikken

G = i=015(Fy Ey)2 Ey

der yi = xi mod 16, Fy er frekvensen av kvar mogleg verdi av yi og Ey = n16 er forventa frekvens.

1.
Dei fleste slumptalsgeneratorar leverer heiltal på 31 bits eller meir, men i testen over testar me berre fire bits frå kvart slumptal. Kvifor testar me aldri alle 31 samstundes?
2.
Kva er nullhypotesen for testen?
3.
Kva fordeling har G under nullhypotesen?
4.
Kva er den kritiske verdien for testen ved 5% signifikansnivå?
5.
Sett at me observerer n slumptal og observerer g = 6,9. Kan me forkasta nullhypotesen?

22.7.2. Løysingsforslag

Oppgåve 22.1

1.
Der finst ingen enkel definisjon på tilfeldig. Me seier at ei hending er tilfeldig dersom me ikkje kan forutseia utfallet. Det treng ikkje tyda 50-50 sannsyn (uniform fordeling), sjølv om ein rimeleg kan seia at uniform fordeling er meir tilfeldig enn andre fordelingar.

Hasardspel som rullett er eit godt døme. Føresetnaden er at kula landar med uniform fordeling på ulike tal. Dersom kulen faktisk landar tilfeldig, vil spelarane i lengda vinna (dvs. tapa) like mykje. Dersom nokon kan forutseia kula og slå banken i lengda, so er kula ikkje tilfeldig.

2.
Dette spørsmålet kan tolkast på to ulike måtar.
a)
Korleis skal ein velja parametra a,c,m slik at slumptala vert gode?

Dette er eit vanskeleg spørsmål, og eit fullstendig svar ligg utanfor pensum. Ein skal likevel vita at m er ei øvre grense for perioden, og må difor vera stor. Dersom m er ein potens av to får ein dårleg statisk fordeling. Parametra må veljast samla for å få gode statistiske eigenskapar (inkl. stor periode). Der er få gode val, og vilkårlege parametre vert sjelden gode.

b)
For kva bruk er den lineære generatoren god nok med beste moglege parameterval?

Det er godt kjent at den lineære generatoren er sårbar for kryptologiske åtak. Dvs. ein åtakar som investerer ressursar i det, vil kunne forutseia fylgja berre ved å observera nokre av tala. Den lineære generatoren kan difor ikke brukast i nokon samanheng der der står store pengar på spel (pengetransaksjonar, nettbank, hasardspel).

3.
Me skriv ned fylgja,
11, 23, 20, 2, 19, 21, 8, 5, 12, 4, 6, 18, 15, 22, 14, 16, 3, 0, 7, 24, 1, 13, 10, 17, 9, 11

Me ser at me har maksimal periode, dvs. 25.

4.
Me kan aldri bruka meir enn ein brøkdel av perioden. Når me har brukt opp ein del av perioden, tek det til å påverka sannsynsfordeling på dei attståande tala. Når me har brukt opp heile perioden, for me eksakt repetisjon.

Oppgåve 22.2

1.
Fordi utfallsrommet då vert svært stort, mykje større enn det utvalet som me i praksis kan testa. Resultatet då er at endringar i Ey gjev minimale endringar G, og me klarer ikkje å skilja ulike fordelingar. Dersom testen skal fungera, må utvalet vera svært stort samanlikna med utfallsrommet.
2.
Ey = Ey for alle y og y
3.
G er χ2-fordelt med 15 fridomsgradar

22.7.3. Eigenarbeid

1.
Haust 2016, oppgåve 3
2.
Vår 2016, oppgåve 2
3.
Haust 2016, oppgåve 2