Véletlenszám generátorok és tesztelésük Tossenberger Tamás
Érdekességek ●
Pénzérme feldobó gép:
●
$0,25-os érme 1/6000 valószínűséggel esik az élére
●
51% eséllyel érkezik a felfelé mutató oldalára
●
Pörgetésnél akár 80% eséllyel a nehezebbik oldalára esik
Érdekességek II ● ●
●
●
Dobókockák pontatlansága: Legjobb szabvány: oldalhoszszok közt legfeljebb 5 μm -es eltérés megengedett Keresés youtube videólinkek közt Keresés
π -ben
TRNG ●
PRNG, TRNG, CSRNG
●
Mi lehet TRNG? Radioaktív bomlás, quantum jelenségek
●
Határeset: random.org, hőmérsékleti zaj
PRNG ●
● ●
●
Véletlen ~ egyáltalán nem tudjuk megjósolni a sorozat következő elemét az előzőekből De a PRNG-ok épphogy rekurzívak Új elvárás „véletlenre”: a konkrét alkalmazásunkban az eredmény szempontjából legyen (közel) egyenértékű egy TRNG-vel Alkalmazások: fizikai szimulációk, MC-módszerek, online játékok/szerencsjátékok, mintavétel
Mi a véletlen? ●
●
●
●
Elméletben: X 1 , X 2 , X 3 ,... azonos eloszlású független valószínűségi változók felvett sorozatait szeretnénk szimulálni Probléma: gyakorlati szempontból nem megvalósítható; számsorozatokról szeretnénk eldönteni, hogy azok véletlen sorozatok-e A véletlen U ([ 0;1)) -sorozat fogalmát szeretnénk valahogy megfogni, egy intuitíve elvárt tulajdonságát definiálni Ezután ugyanezt megtenni a {0,1,...,b−1} halmazra vonatkozó diszkrét egyenletes eloszlás-sorozatra
A véletlen sorozat esszenciája ● ●
Adott U=U 1 ,U 2 ,U 3 ,...
U ([ 0;1)) -beli
számsorozat
μ(n ,u, v):=∣{ j:0≤ j
sorozat első n tagja közül azoknak a száma, melyek az [u ;v) intervallumra esnek μ(n,u ,v) =v−u n
●
Szeretnénk: ∀u
●
Szemléletesebb jelöléssel:
●
A sorozat -egyenletes, ha P(u1 ≤U j
●
A sorozat ∞-egyenletes, ha ∀ k -ra -egyenletes
P (u≤U j
μ(n , u , v) n
Ugyanez b alapú számsorozatokra ●
●
A számítógép által generálható számsorozatokra szeretnénk véletlen fogalmat nyerni; valós számsorozatokat (általánosan) nem tudunk generálni Egy b alapú sorozat -egyenletes, ha P( X j =x 1 ,... X j+k−1= x k )=
1 k b
∀ x1 ,... , x k ∈{0,...,b−1} -ra
●
Megjegyzés: -egyenletes sorozat (k−1)-egyenletes
●
∞ -egyenletes, ha ∀ k -ra -egyenletes
Ugyanez b alapú számsorozatokra ●
●
A számítógép által generálható számsorozatokra szeretnénk véletlen fogalmat nyerni; valós számsorozatokat (általánosan) nem tudunk generálni Egy b alapú sorozat -egyenletes, ha P( X j =x 1 ,... X j+k−1= x k )=
1 k b
∀ x1 ,... , x k ∈{0,...,b−1} -ra
●
Megjegyzés: -egyenletes sorozat (k−1)-egyenletes
●
∞ -egyenletes, ha ∀ k -ra -egyenletes
Mi a helyzet a véges sorozatokkal? ●
●
●
Bizonyos értelemben nincs értelme véges sorozatok véletlenségéről beszélni: mindegyik ugyanolyan valószínűségű Viszont egyes alkalmazásokban célszerű kizárni bizonyos nem véletlenszerűnek ítélt sorozatokat Adott X 1 ,... , X n b alapú sorozat -egyenletes, ha 1 1 P ( X j= x1 ,... , X j+ k−1= x k )− k ≤ b √n
∣ ● ●
∣
A sorozat „véletlen” ha -egyenletes ∀k≤logb N -re Pl. 170 db 11 hosszú nem véletlen bináris sorozat létezik
Négyzetközép-módszer ●
●
●
Egy n jegyű számból indulunk ki (tetszőleges számrendszerben) Rekurzió: az aktuális n jegyű számot négyzetre emeljük, és az eredménynek, mint 2 n jegyű szám, vesszük a középső n jegye által alkotott n jegyű számot Nem túl gyors; egy ideig véletlenszerűként viselkedik, de utána általában rövid ciklusba áll be: pl. 20 bites számok esetén csak 13 különböző ciklus van, és ezek közül a leghosszabb 142 hosszú
Lineáris kongruencia módszer ● ●
● ●
● ●
ℤ m gyűrűben dolgozunk Adott ( m modulus,) X kezdőérték, a együttható és c növekmény ℤ m -ből Rekurzió: X n+1=a X n +c m (maximális) ciklushossz elérhető, ha: (c , m)=1 ; a−1 -et osztja m minden prímosztója; és ha 4 |m , akkor 4 | a−1 Célszerű választás: 0.01m≤a≤0.99m Nagyon gyors, és egyszerű alkalmazásokra megbízható 0
1 lépéses rekurziók ●
Megéri-e kombinálni a PRNG-ainkat?
●
Pl.
●
●
X n+1=((a X n )mod(m+1)+c)mod m
még véletlenszerűbb?
Az 1-egyenletességhez nagy ciklusra van szükségünk (ha a az ismétlődéses fázist is fel akarjuk használni) „Véletlen választott” 1 lépéses rekurzió esetén legalább
1 e
a valószínűsége, hogy 1 hosszú
ciklusba jutunk, és legfeljebb ismétlésmentes szakasznak
n e
a várható értéke a
2
χ -próba ● ●
Csak diszkrét eloszlások vizsgálatára alkalmas Az elemi eseményeket osszuk be k partícióba, ezekbeli gyakoriságot jelölje Y j , az elméleti valószínűségét pedig az adott partícióba esésnek jelölje p j k
2
2
(Y j−n p j) 1 k Y j ● V =∑ = ∑ −n n p n p j=1 j j=1 j
1 2
k−1 2
, paraméterekkel, így táblázatból kiolvasható, vagy kiszámolható, a kívánt valószínűség
●
Γ eloszlású
λ=
α=
Konyhamódszer: ha 3 sorozatból legalább 2 gyanús (5%-nál kevesebb, vagy 95%-nál több), akkor a generátor nem elég véletlenszerű
Kolmogorov-Szmirnov-próba ●
●
Csak folytonos eloszlásfüggvényű eloszlásokra alkalmazható A tapasztalati és az elméleti eloszlásfüggvény legnagyobb eltéréseit karakterizálja
●
K n = √n max(F n ( x)−F (x)) ,
●
Táblázatból kiolvasható a keresett valószínűség
●
A kis lokális eltéréseket nem mutatja ki
+
−
K n = √n max(F (x )−F n (x))
Egyéb tesztek ●
●
●
Sorozatpróba: k -asokba rendezzük a sorozat 2 elemeit, és ezekre χ -próbát végzünk; nagyobb k -ra érdemesebb pl. pókerpróbát használni Pókerpróba: számötösökre bontjuk a sorozatot, majd 7 partíciót hozunk létre: mind különböző, egy pár, két pár, drill, full house, póker, öt egyforma; 2 χ ezekre -próbát végzünk Hézagpróba: a hézagok hosszainak eloszlását vizsgáljuk, elméletben ez 2geometriai eloszlást adna, ezzel összevetjük χ próba segítségével
Egyéb eloszlások szimulálása ●
●
Eddig csak egyenletes eloszlást próbáltunk meg szimulálni, de gyakran más nevezetes eloszlások generálására is szükségünk van; szerencsére ezek (általában) visszavezethetőek az egyenletesre Ha X valószínűségi változó F (x) eloszlásfüggvénye −1 F ismert, akkor mivel (U ) eloszlásfüggvénye megegyezik az előbbivel, ezért ezen formula segítségével szimulálhatjuk X eloszlást
Normális eloszlás ●
●
A normális eloszlásnak nem ismerjük az eloszlásfüggvényét, így az előbbi módszert nem tudjuk alkalmazni Box-Muller algoritmus: Adott U , U [0 ;1) -en egyenletes (független) valószínűségi változók 2 2 V =2U −1 V =2U −1 S =V +V (1) Legyen 1 1 , 2 2 és 1 2 (2) Ha S≥1 GOTO (1) −2 ln S −2 ln S X =V X =V (3) Legyen és S S Így X 1 , X 2 független, normális eloszlású valószínűségi változók 1
1
1
√
2
2
√
2
Tesztkérdés ●
Melyik (végtelen) bináris sorozat 2-egyenletes az alábbiak közül? A) 101010... B) 100100100... C) 001100110011... D) 111000111000111000...
