Statistikk og Simulering

Økt 25. Slumptalsgeneratorar

Perioden

18.2. Perioden

Definisjon 16 Perioden i ei fylgje [x1,x2,] er det minste talet m > 0 slik at xi = xi+m for alle i > k for ein eller annan k.

Ein fylgje som har periode m repeterer seg sjølv for kvart mte element. Merk at der kan vera ein serie med meir enn m distinkte tal i starten av fylgja, men frå eit eller anna punkt k kan me sjå periodiske syklar med fast lengd.

Oppgåve 18.5 Sjå på fylgjene som du genererte med dei tre kongruensgeneratorane over (for a = 6, 9, 10). Kva periode har fylgjene? Er periode uavhengig av frøet s?

Oppgåve 18.6 Kva er den største perioden du kan tenkja deg for ein kongruensgenerator med parameter a, c og m.

Sats 3 Den lineære kongrunsgeneratoren si = asi1 + cmodm har periode m dersom, og berre dersom,

1.
c og m er relativt prim (mao. hcf(c,m) = 1)
2.
p deler b = a 1 for alle primtal p som deler m
3.
4 deler b = a 1 dersom 4 som deler m