UNIVERZA V LJUBLJANI
FAKULTETA ZA MATEMATIKO IN FIZIKO Matematika 1. stopnja
pela Petan
Testiranje generatorjev izidov v igrah na sre£o Delo diplomskega seminarja
Mentor: izr. prof. dr. Mihael Perman
Ljubljana, 2021
Kazalo
1. Uvod 4
2. Matemati£no ozadje 4
2.1. Matemati£na formulacija problema 5
2.2. Hi-kvadrat test 5
2.3. Alternativni hi-kvadrat test 8
3. Knuthovi testi naklju£nosti 10
3.1. Frekven£ni test 10
3.2. Test na parih 10
3.3. Test vrzeli 11
3.4. Poker test 12
3.5. Permutacijski test 12
3.6. Test nara²£ajo£ih in padajo£ih podzaporedij 13
4. Testiranje na nivoju iger na sre£o 19
4.1. Holm-Bonferronijeva metoda 19
4.2. Deljenje kart 20
4.3. Igre s koluti 25
Slovar strokovnih izrazov 30
Literatura 30
Testiranje generatorjev izidov v igrah na sre£o Povzetek
V algoritme za generiranje izidov v igrah na sre£o so vgrajeni generatorji slu£ajnih
²tevil. V diplomskem delu je predstavljenih ²est empiri£nih Knuthovih testov, ki preverjajo, ali se verjetnosti generiranih izidov ujemajo s teoreti£nimi verjetnostmi.
Vsak test lahko prevedemo na Pearsonovχ2 test, ki ima za velike slu£ajne vzorceχ2 porazdelitev. Tako lahko izra£unamo p-vrednost, na podlagi katere ocenimo po²te- nost generatorjev. Pearsonov χ2 test pa je kljub ²iroki uporabljenosti zahteven, saj za natan£nost potrebuje velik slu£ajni vzorec. Zato je v delu predstavljen tudi pred kratkim objavljen alternativen χ2 test.
Testing outcome generators in games of chance Abstract
Random number generators are used in algorithms for outcome generating in games of chance. We present the six Knuth's tests. They check whether probabilities of generated outcomes match the theoretical probabilities. Each one of them reduces to Pearson'sχ2 test, which has theχ2 distribution for large random samples. That is how we calculatep-values based on which we evaluate the fairness of outcome gene- rators. Despite Pearson'sχ2 test being widely used, it is complex, since a big random sample is needed for its accuracy. Therefore the recently published alternative χ2 test is also presented in the thesis.
Math. Subj. Class. (2020): 62F05, 62P30
Klju£ne besede: igre na sre£o, statisti£ni testi, generatorji slu£ajnih ²tevil,χ2 testi Keywords: games of chance, statistical tests, random number generators, χ2 tests
1. Uvod
Igre na sre£o, ki imajo algoritme za deljenje kart, vrtenje koluta in podobno, je potrebno testirati, da so pravi£ne. Pri tem uporabljamo ve£ razli£nih testov. Naj- pogosteje uporabljen test je χ2 test, ki ga je leta 1900 izpeljal Karl Pearson. V diplomskem delu bo najprej opisan Pearsonovχ2 test in dokazana njegova porazde- litev. Pogledali si bomo alternativni χ2 test. Sledil bo opis ²estih Knuthovih testov in njihova pretvorba na χ2 test. V zadnjem poglavju pa bo predstavljena uporaba testov za testiranje generatorjev v igrah na sre£o.
2. Matemati£no ozadje
Generatorje slu£ajnih ²tevil ºelimo testirati, da preverimo njihovo po²tenost. Zato si moramo najprej postaviti ni£elno domnevo, da bomo vedeli, kaj testiramo.
Denicija 2.1. Hipotezi oziroma domnevi, ki jo postavimo pri testiranju, pravimo ni£elna domneva. Ozna£imo jo s H0. Nasprotje ni£elni domnevi je alternativna do- mneva in jo ozna£imo s H1.
Privzeli bomo ni£elno domnevo, da so generirana ²tevila enakomerno in neodvisno porazdeljena. Na generiranih ²tevilih bomo izvedli statisti£ne teste, ki bodo povedali, ali ni£elno hipotezo zavrnemo in sprejmemo alternativno hipotezo ali pa ne naredimo ni£esar. Pri tem si bomo izbrali stopnjo tveganja.
Denicija 2.2. Stopnja tveganja je najve£ja dopu²£ena verjetnost dogodka, ko ni-
£elno hipotezo zavrnemo, £eprav ta velja. Ozna£imo jo z α.
Najpogosteje si za stopnjo tveganja izberemo 0,05, 0,01 ali 0,001, vendar za te izbire ni nobene matemati£ne utemeljitve. Pri testiranju lahko naredimo dve vrsti napak. Napaka tipa I je napaka, ko ni£elno hipotezo zavrnemo, ko je ne bi smeli.
Napaka tipa II je napaka, ko ni£elne hipoteze ne zavrnemo, ko bi jo morali. Ve£ja napaka je napaka tipa I, zato pri vsakem testiranju zahtevamo, da je ta napaka £im manj²a in sicer manj²a od izbrane stopnje tveganja. elimo pa si, da bi bili obe napaki £im manj²i. Pri vsakem testu izra£unamo tudi p-vrednost testa.
Denicija 2.3. Verjetnosti, da dobimo tako ekstremen rezultat, kot je opazovan re- zultat statisti£nega testa ob privzetku, da ni£elna domneva drºi, pravimop-vrednost.
Na podlagi izbrane stopnje tveganja α in p-vrednosti testa se lahko odlo£imo o ni£elni domnevi. e jeαmanj²i odp-vrednosti, potem ni£elne domneve ne zavrnemo.
e je α ve£ji odp-vrednosti, pa ni£elno domnevo zavrnemo.
Vpeljimo ²e nekaj denicij. Sre£ali bomo dve porazdelitvi, χ2 in polinomsko po- razdelitev. Denirajmo ju s pomo£jo virov [6] in [8].
Denicija 2.4. Porazdelitev χ2 z n prostostnimi stopnjami je porazdelitev vsote X12 + X22 +· · · +Xn2, kjer so X1, X2, . . . , Xn neodvisne in standardno normalno porazdeljene slu£ajne spremenljivke. Gostota porazdelitve je po viru [6]
f(x) =
⎧
⎪⎨
⎪⎩
xn2−1e−x2 2n2Γ(︁n
2
)︁; £e je x >0, 0; sicer. Ozna£imo jo kot χ2(n).
Vidimo, da jeχ2 porazdelitev le poseben primer gama porazdelitve, saj jeχ2(n) = Γ(n2,12)
Denicija 2.5. Naj bodo X1, X2, . . . , Xr slu£ajne spremenljivke. Naj bo p = (p1, p2, . . . , pr)T, za katerega velja ∑︁r
j=1pj = 1. Polinomska porazdelitev je dolo£ena s predpisom
P(X1 =k1, X2 =k2, . . . , Xr =kr) = n!
k1!·k2!· · ·kr! ·pk11 ·pk22· · ·pkrr, kjer so kj cela nenegativna ²tevila in n =∑︁r
j=1kj. Ozna£imo jo sP olinom(n;p). Polinomska porazdelitev je le posplo²ena binomska porazdelitev. Denirajmo ²e
²ibko konvergenco slu£ajnih vektorjev.
Denicija 2.6. Zaporedje slu£ajnih vektorjev X1,X2, . . . z vrednostmi v Rm ²ibko konvergira proti slu£ajnemu vektorju X, £e za vsako zvezno in omejeno funkcijo h:Rm →R velja
n→∞lim E(h(Xn)) =E(h(X)).
ibko konvergenco ozna£imo z Xn
−−−→d
n→∞ X.
ibko konvergenco potrebujemo za centralni limitni izrek, ki nam bo pomagal pri kasnej²em dokazovanju.
Izrek 2.7 (Centralni limitni izrek). Naj bodo X1,X2, . . . neodvisni in enako poraz- deljeni slu£ajni vektorji, za katere obstaja µ1 =E(X1) in Σ1 = var(X1). Tedaj
X1+X2+· · ·+Xn−nµ1
√n
−−−→d
n→∞ N(0,Σ1).
2.1. Matemati£na formulacija problema. Generator slu£ajnih ²tevil je algori- tem, ki vra£a zaporedje naklju£nih ²tevil. tevila, ki jih generator vra£a, izgledajo naklju£na, v resnici pa tipi£ni programski jeziki uporabljajo v naprej napisane al- goritme. Zato ta ²tevila imenujemo psevdo-naklju£na. Osnovni generatorji slu£ajnih
²tevil vra£ajo zaporedje ni£el in enk, izvedeni pa enakomerno razporejena cela ²tevila na intervalu med 0 in m−1, za neki m∈ N. Generatorje ºelimo preveriti, £e zares vra£ajo naklju£na ²tevila. Zato uporabljamo razli£ne teste. Empiri£ni testi delujejo tako, da iz skupin ²tevil v zaporedju izra£unajo dolo£eno statistiko. Ni£elna hipoteza pri testiranju generatorjev slu£ajnih ²tevil je, da so generirana ²tevila enakomerno porazdeljena in neodvisna.
2.2. Hi-kvadrat test. Leta 1900 jeχ2 test prvi uporabil Karl Pearson.χ2 test sloni na primerjavi empiri£nih frekvenc s pri£akovanimi frekvencami. Empiri£na frekvenca je ²tevilo podatkov v vzorcu, ki so enaki neki vrednosti. Po viru [7] test uporabljamo na neodvisnih poskusih, ki imajo r moºnih izidov z verjetnostmi p0, p1, . . . , pr−1. Poskus neodvisno ponovimo n-krat. Z nj ozna£imo ²tevilo pojavitev izida j v n poskusih. χ2 testno statistiko deniramo kot
(1) χ2(n) =
r−1
∑︂
j=0
(nj−npj)2 npj .
χ2 statistiko lahko po viru [9] interpretiramo kot mero razhajanja med teoreti£nimi verjetnostmi in dejansko opazovanimi verjetnostmi. Odlo£iti se moramo, kdaj ne moremo ve£ sprejeti, da so empiri£ne frekvence zdruºljive s teoreti£nimi. Izberemo
si parameter α ∈(0,1), ki je stopnja tveganja. Pri izvajanju testa mora biti vzorec dovolj velik, da bo zagotovljena natan£nost aproksimacijχ2 testa in da bop-vrednost χ2 testa porazdeljena enakomerno na[0,1]. Zato po viru [3, stran 45] obstaja pravilo, da morajo biti pri£akovane frekvencenpj ve£je od5. V nadaljevanju bomo pokazali, zakaj je poimenovanje testne statistike χ2 smiselno, saj ima v primeru veljavnosti ni£elne hipoteze pribliºno χ2 porazdelitev z r−1 prostostnimi stopnjami. To velja le za velike testne vzorce.
Izrek 2.8. Ko gre n proti neskon£nosti, χ2 testna statistika χ2(n) =
r−1
∑︂
j=0
(nj −npj)2 npj
kovergira proti χ2 porazdelitvi z r−1 prostostnimi stopnjami.
Dokaz. Naj ima poskus r moºnih izidov. Vsak izid j naj se zgodi z verjetnostjo pj in naj velja ∑︁r−1
j=0pj = 1. Poskus neodvisno ponavljamo. Naj bodo X1,X2,X3, . . . neodvisni slu£ajni vektorji, ki predstavljajo posamezno ponovitev poskusa. Skupno naj bodo porazdeljeni P olinom(1,p), kjer je
p=
⎡
⎢
⎢
⎣ p0
p1 ...
pr−1
⎤
⎥
⎥
⎦ .
Slu£ajni vektor
Xi =
⎡
⎢
⎢
⎣ xi0 xi1 ...
xi(r−1)
⎤
⎥
⎥
⎦
je vektor dolºine r in je sestavljen iz samih ni£el in ene enke na mestu k, kjer je k zmagovalni izid v i-ti ponovitvi. Za vsak 0≤j ≤r−1 velja
P(Xij = 1) = 1−P(Xij = 0) =pj. (2)
Opazujemo testno statistiko
χ2(n) =
r−1
∑︂
j=0
(nj−npj)2 npj ,
kjer je nj slu£ajna spremenljivka, ki predstavlja ²tevilo uspehov j-tega izida v n poskusih, zato jo ozna£imo znX¯j. S pomo£jo (2) izra£unajmo pri£akovano vrednost in varianco Xij.
E(Xij) = 0·P(Xij = 0) + 1·P(Xij = 1) =pj E(Xij2) = 02·P(Xij = 0) + 12·P(Xij = 1) =pj
var(Xij) =E(Xij2)−E(Xij)2 =pj−p2j =pj(1−pj)
Sedaj lahko izra£unamo ²e kovarianco Xij inXil zaj ̸=l. Pri tem upo²tevajmo, da Xij inXil ne moreta biti hkrati 1, saj je v vektorju Xi natanko ena enka.
E(XijXil) =
1
∑︂
u=0 1
∑︂
v=0
uvP(Xij =u, Xil =v) = 0
cov(Xij, Xil) =E(XijXil)−E(Xij)E(Xil) =−pjpl Torej je kovarian£na matrika slu£ajnega vektorja Xi
(3) Σ =
⎡
⎢
⎢
⎣
p0(1−p0) −p0p1 · · · −p0pr−1
−p0p1 p1(1−p1) · · · −p1pr−1
... ... ... ...
−p0pr−1 p1pr−1 · · · pr−1(1−pr−1)
⎤
⎥
⎥
⎦ .
Ker je E(Xi) =p, po centralnem limitnem izreku velja
√n(X¯n−p)−−−→d
n→∞ N(0,Σ) kjer je nX¯n=∑︁n
i=1Xi. Opazimo, da je vsota j-te vrstice ali j-tega stolpca kovari- an£ne matrike Σ enaka 0, saj je
pj(1−p0−p1− · · · −pr−1) =pj(1−1) = 0.
To pomeni, da so vrstice in stolpci linearno odvisni in zato Σ ni obrnljiva. Da bi dobili obrnljivo matriko, slu£ajnim vektorjem Xi odstranimo eno dimenzijo
X∗i =
⎡
⎢
⎢
⎣ Xi0 Xi1 ...
Xi(r−2)
⎤
⎥
⎥
⎦
in podobno tudi vektorju p
p∗ =
⎡
⎢
⎢
⎣ p0 p1 ...
pr−2
⎤
⎥
⎥
⎦ .
Kovarian£na matrika slu£ajnega vektorja X∗i je podmatrika matrike Σ, zmanj²ana na r−1 vrstic in stolpcev, in je polnega ranga. Zapi²emo jo lahko kot
Σ∗ =
⎡
⎢
⎢
⎣
p0(1−p0) −p0p1 · · · −p0pr−2
−p0p1 p1(1−p1) · · · −p1pr−2
... ... ... ...
−p0pr−2 p1pr−2 · · · pr−2(1−pr−2)
⎤
⎥
⎥
⎦
=
⎡
⎢
⎢
⎣
p0 0 · · · 0 0 p1 · · · 0 ... ... ... ...
0 0 · · · pr−2
⎤
⎥
⎥
⎦
−p∗(p∗)T.
Ker jeΣ∗ polnega ranga, lahko izra£unamo njen inverz. Inverz ima po viru [1, stran 3] obliko
(Σ∗)−1 =
⎡
⎢
⎢
⎢
⎣
1 p0 + p1
r−1
1
pr−1 · · · p1
1 r−1
pr−1
1 p1 + p1
r−1 · · · p1 ... ... ... r−1...
1 pr−1
1
pr−1 · · · p1
r−2 + p1
r−1
⎤
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎣
1
p0 0 · · · 0 0 p1
1 · · · 0 ... ... ... ...
0 0 · · · p1
r−2
⎤
⎥
⎥
⎥
⎦ + 1
pr−1
⎡
⎢
⎢
⎣
1 1 · · · 1 1 1 · · · 1 ... ... ... ...
1 1 · · · 1
⎤
⎥
⎥
⎦ .
Preoblikujmo χ2 testno statistiko χ2(n) =
r−1
∑︂
j=0
(nX¯j−npj)2 npj
=n (︄r−2
∑︂
j=0
(X¯
j −pj)2
pj +(X¯r−1−pr−1)2 pr−1
)︄
=n (︄r−2
∑︂
j=0
(X¯j −pj)2
pj +(∑︁r−2 j=0(X¯
j−pj))2 pr−1
)︄
(4) .
Pri zadnjem ena£aju upo²tevamo, da je ∑︁r−1 j=0(X¯
j − pj) = 0. Ena£bo (4) lahko zapi²emo tudi v matri£ni obliki
χ2(n) =n(X¯∗−p)T(Σ∗)−1(X¯∗−p)
= (√
n(Σ∗)−12(X¯∗−p∗))T
⏞ ⏟⏟ ⏞
(Yn)T
(√
n(Σ∗)−12(X¯∗−p∗))
⏞ ⏟⏟ ⏞
Yn
. Centralni limitni izrek pove, da
Yn −−−→d
n→∞ N(0, Ir−1).
Sledi, da χ2 = (Yn)TYn konvergira proti N(0, Ir−1)TN(0, Ir−1). To pa predstavlja vsoto kvadratovr−1neodvisnih standardno normalnih slu£ajnih spremenljivk. Zato sledi
χ2(n)−−−→d
n→∞ χ2(r−1). □
2.3. Alternativni hi-kvadrat test. Glavna motivacija, da bi na²li bolj²o testno statistiko od χ2, je, da ta zahteva zelo velik testni vzorec. Poleg tega se izkaºe tudi, da na test mo£no vplivajo izidi z majhnimi verjetnostmi. Vse to nas vzpodbudi, da bi χ2 test nekoliko preoblikovali. V £lanku [4] je predstavljen test, alternativen χ2 testu, ki bo v tem poglavju bolje predstavljen.
Recimo, da imamo n vzorcev. Naj Xj ozna£uje ²tevilo pojavitev j-tega izida in pj njegovo verjetnost. Torej je po deniciji
χ2(n) =
r−1
∑︂
j=0
(Xj−npj)2 npj .
Podrobneje si oglejmo vsoto, ki nastopa v zgornji ena£bi
r−1
∑︂
j=0
(Xj−npj)2 pj . (5)
Za laºjo primerjavo z alternativnim testom najprej izrazu (5) od²tejmo konstanto. To smemo narediti, saj se obna²anje testne statistike ne bo spremenilo, £e ji od²tejemo konstanto n
r−1
∑︂
j=0
(Xj−npj)2−npj
pj .
Prva sprememba, ki jo naredimo na testu, je, da zamenjamo teoreti£no frekvenco npj z empiri£no Xj.
r−1
∑︂
j=0
(Xj−npj)2−Xj pj
Druga pa, da zamenjamo faktor p1j z 1
p
2 3 j
r−1
∑︂
j=0
(Xj −npj)2−Xj p
2 3
j
.
Obe spremembi ºelita popraviti to, da imajo izidi z majhnimi verjetnostmi velik vpliv na rezultat χ2 testa. Zakaj je za drugo spremembo najbolj primerna potenca ravno
2
3, je podrobneje dokazano v delu [4]. Motivacijo za prvo spremembo pa poglejmo v spodnjem primeru.
Primer 2.9 (zamenjavanpj zXj). Naj ima igrak+ 1moºnih izidov, kjer je k∈N.
Izid a naj ima verjetnost pa = 1− 1k. Ostalih k izidov naj ima vsak verjetnost pk = k12. e izberemo n = 100k vzorcev, bomo med vsemi dobili pribliºno 100 redkej²ih izidov. Ostali bodo izid a. Redkej²i izidi bodo imeli velik vpliv na χ2 test.
Ker je v tem primeru n·pk zelo majhno ²tevilo, lahko £len v vsoti za enega izmed redkej²ih k izidov ocenimo kot
(Xj −npk)2
npk ≈ Xj2 npk.
e se izid j ̸= a ne bi pojavil nikoli, tudi k vsoti χ2 testa ne bi prispeval ni£esar.
Vendar £e bi se pojavil le enkrat, tj. Xj = 1, bi na test mo£no vplival, saj np1k ni zanemarljiv £len. V primeru alternativnegaχ2 testa lahko naredimo podobno oceno
(Xj −npj)2−Xj np
2 3
j
≈ Xj2−Xj np
2 3
k
e se izid j ne pojavi, se rezultat testa ne spremeni. Prav tako, £e se izid pojavi le
enkrat, je £len v vsoti ponovno 0. ♢
Alternativenχ2test je zaradi obeh sprememb veliko bolj grob za zaznavanje manj-
²ih izidov. Zato ima v primerjavi s Pearsonovim χ2 testom manj²o varianco. Spre- membe se mo£no poznajo tudi pri ²tevilu potrebnih vzorcev. Prvotenχ2 test po oce- nah iz literature [4] potrebuje najmanjO(︂√
npoly((log(n)) ϵ4
)︂vzorcev, kjerpoly(x)pred- stavlja polinom v spremenljivki x. Alternativni test pa le O(︂√
n ϵ2
)︂, kjer je ϵ∈(0,1)
izbrana konstanta, potrebna za izvedbo alternativnega testa. Po viru [4, stran 58]
alternativni test namre£ deluje tako, da lo£i izide glede na njihovo verjetnost. Izide razvrstimo po vrsti glede na verjetnosti, kjer naj bo prvi v vrsti tisti z najmanj²o verjetnostjo. V mnoºici Snaj bo prvih toliko izidov, da je∑︁
j∈Spj ≤ 8ϵ in £e bi vsoti pri²teli verjetnost naslednjega najmanj²ega izida, bi bila ta prevelika. V mnoºici M naj bodo vsi izidi, razen izida z najve£jo verjetnostjo in izidov, ki so v S. S pM ozna£imo vektor verjetnosti izidov, ki so v mnoºici M. Alternativniχ2 test pove, da
£e velja
∑︂
j∈M
(Xj −npj)2 −Xj
p
2 3
j
>4n∥pM∥
1 3 2 3
ali
∑︂
j∈S
Xj > 3 16ϵn,
se empiri£ne frekvence ne ujemajo s teoreti£nimi. Sicer se. eprav so z alternativnim χ2 testom izbolj²ali Pearsonov χ2 test, se ²e zmeraj uporablja zadnji.
3. Knuthovi testi naklju£nosti
Empiri£ni Knuthovi testi izvedenih generatorjev slu£ajnih ²tevil testirajo, £e imajo vsa ²tevila enako verjetnost in morebitno odvisnost med zaporednimi generiranimi
²tevili. V nadaljevanju bo predstavljenih ²est Knuthovih testov in njihove pretvorbe naχ2 test. Pri tem bomo sledili [3, poglavje 3.3.2.]. V tem poglavju privzemimo, da imamo generator, ki generira slu£ajna cela ²tevila na intervalu[0, m−1]. Generator testiramo na vzorcu velikosti n.
3.1. Frekven£ni test. Frekven£ni test je najbolj osnoven izmed vseh in preverja enakomerno porazdelitev ²tevil. Generator je dober, £e je verjetnost poljubnega ²te- vila enaka
p= 1 m.
Test izvedemo tako, da uvedemo ²tevce nj, ki ²tejejo pojavitev ²tevilaj ∈ {0,1, . . . , m−1}. Pregledamo ²tevila v zaporedju. Ko se pojavi ²teviloj, pove£amo ²tevecnj za1. Na koncu mora biti vsota ²tevcev enaka velikosti vzorcan.χ2 testno statistiko izra£unamo kot
χ2(n) =
m−1
∑︂
j=0
(nj−np)2
np .
3.2. Test na parih. Test na parih preverja odvisnost med generiranimi ²tevili.
Generirano zaporedje ²tevil razdelimo na urejene pare zaporednih ²tevil (Y2i−1, Y2i) za1≤i≤ n2. e je generator dober, potem je verjetnost pojavitve kateregakoli para enaka
p= 1 m2.
Test izvedemo tako, da vpeljemo ²tevcenklza vsak par k, l∈ {0,1, . . . , m−1}. e se v zaporedju pojavi par (k, l), pove£amo ²tevec nkl za1. e ºelimo imeti n opaºenih izidov, moramo pri tem testu generirati 2n ²tevil. χ2 testno statistiko izra£unamo kot
χ2(n) =
m−1
∑︂
k,l=0
(nkl−np)2
np .
Za velike m bo ²tevilo moºnih parov veliko. Zato v tem primeru test prilagodimo tako, da mnoºico{0,1, . . . , m−1}razdelimo v disjunktne podmnoºiceA0, A1, . . . , Ar za neki r ∈ N. Velikosti teh podmnoºic naj bodo enake ali skoraj enake. Razbitje mnoºice {0,1, . . . , m−1} lahko najdemo na razli£ne na£ine. Najenostavneje je, da jo razdelimo na podmnoºice zaporednih ²tevil. Par zaporedno zgeneriranih ²tevil (Y2i−1, Y2i)preimenujemo v par(s, t), £e jeY2i−1 ∈As inY2i ∈At. Verjetnost takega para je
pst = |As×At | m2 .
Test na parih izvedmo na preimenovanih parih. Zato uporabljamo ²tevce nst za vsak par s, t ∈ {0,1, . . . , r}. V tem primeru χ2 test izra£unamo kot
χ2(n) =
r
∑︂
s,t=1
(nst−npst)2 npst .
3.3. Test vrzeli. Test vrzeli preverja, kako pogosto generator naklju£nih ²tevil ge- nerira ²tevilo iz neke izbrane mnoºice izidov A. Mnoºico{0,1, . . . , m−1}razdelimo na disjunktne podmnoºice, ki imajo enako ali pribliºno enako velikost. Med temi podmnoºicami si izberemo podmnoºico A in poi²£emo vrzeli v generiranem zapo- redju ²tevil. Vrzel je tako zaporedje ²tevil Ui, Ui+1, . . . , Ui+r, da sta Ui, Ui+r ∈A in Ui+1. . . , Ui+r−1 ∈/ A. Dolºina take vrzeli je r−1. V generiranem zaporedju i²£emo dolºine vrzeli med ²tevili iz izbrane mnoºice. Dolºine vrzeli so med seboj neodvisne.
Ozna£imo verjetnost, da je ²tevilo element mnoºice A, s p = |A|m. Verjetnost, da se v vrzeli nahaja j ²tevil, ki niso elementi mnoºice A, je (1−p)j. Verjetnost, da je zadnje ²tevilo element mnoºice A, pa je p. e z X ozna£imo dolºino vrzeli, potem je za j ∈N∪ {0}
pj =P(X =j) = (1−p)jp.
Vsaka vrzel mnoºice A se za£ne s ²tevilom iz te mnoºice, zato pri verjetnosti, da je vrzel dolga j, ne upo²tevamo prvega ²tevila v vrzeli. Test izvedemo tako, da izberemo eno izmed podmnoºicAmnoºice{0,1, . . . , m−1}. Naj ²tevecnj ²teje vrzeli dolºine j za j ∈ N∪ {0}. Odstranimo vsa za£etna ²tevila generiranega zaporedja, ki niso v mnoºici A. Prvo ²tevilo zaporedja je element A. Poi²£emo dolºino vrzeli do naslednjega ²tevila, ki je v mnoºici A. e je dolºina vrzelij, pove£amo ²tevecnj
za 1. Potem izbri²emo ²tevila prve vrzeli in poi²£emo dolºino naslednje. Postopek ponavljamo, dokler ne pridemo do zadnjega ²tevila, ki je ²e v mnoºiciA. e to ²tevilo ni zadnje v zaporedju, zadnje nedokon£ane vrzeli ne upo²tevamo. tevilo vrzeli med elementi mnoºice A je
N =n0+n1+n2+· · · .
Ker je verjetnost, da se pojavi dalj²a vrzel manj²a, kot da se pojavi kraj²a vrzel, poi²£emo najve£ji tak K ∈N, da je
p
¯ =P(X ≥K) = (1−p)K ≥0,001 in zdruºimo ²tevce dolºin vrzeli dalj²ih od K−1
n
¯K =nK +nK+1+· · · . χ2 izra£unamo kot
χ2(N) = (n¯K−N p¯)2 N p¯ +
K−1
∑︂
j=0
(nj −N pj)2 N pj .
3.4. Poker test. Zaporedje generiranih ²tevil razdelimo v disjunktne bloke po pet zaporednih ²tevil (Y5i−4, Y5i−3, . . . , Y5i)za 1≤i≤ n5. V vsakem bloku je lahko med 1 in 5razli£nih ²tevil. Pri izra£unu verjetnosti, da je v bloku j razli£nih ²tevil, kjer je j ∈ {1,2,3,4,5}, si bomo pomagali s Stirlingovimi ²tevili druge vrste.
Denicija 3.1. tevilu vseh razbitij n-elementne mnoºice A na k nepraznih pod- mnoºic pravimo Stirlingova ²tevila druge vrste in ga ozna£imo s S(n, k).
O£itno velja, da je S(n, k) = 0 za k > n, S(n, n) = 1 in S(n,1) = 1. Sicer pa za vsak par n, k ∈N,1≤k ≤n velja rekurzivna formula, povzeta po viru [10].
S(n, k) =S(n−1, k−1) +kS(n−1, k)
Izra£unajmo verjetnost, da je v bloku j razli£nih ²tevil. Verjetnost, da v bloku nastopa j razli£nih ²tevil, je m(m−1)···(m−j+1)
m5 . tevilo vseh moºnih permutacij petih
²tevil, med katerimi je j razli£nih ²tevil, pre²tejemo s pomo£jo Stirlingovih ²tevil druge vrste. To naredimo tako, da vsaki komponenti urejenega bloka petih ²tevil dolo£imo, kateri mnoºici izmedj mnoºic pripadajo. tevila, ki pripadajo isti mnoºici, dolo£imo kot enaka. Zato, £e ºelimo, da je v bloku natankoj razli£nih ²tevil, moramo 5 ²tevil razdeliti naj nepraznih mnoºic. Torej je verjetnost, da je v blokuj razli£nih
²tevil, kjer je j ∈ {1,2,3,4,5},
pj =S(5,j)· m(m−1)· · ·(m−j+ 1)
m5 .
Test izvedemo tako, da zaporedje generiranih ²tevil razdelimo v disjunktne bloke po 5 zaporednih ²tevil. Ker en blok predstavlja en izid in £e ºelimo imeti n izidov, moramo generirati 5n ²tevil. Nastavimo ²tevce nj, ki ²tejejo bloke z j razli£nimi
²tevili, kjer je j ∈ {1,2,3,4,5}. V vsakem bloku pre²tejemo ²tevilo razli£nih ²tevil in primeren ²tevec pove£amo za 1. Vsota vseh ²tevcev mora biti na koncu enaka n. χ2 izra£unamo kot
χ2(n) =
5
∑︂
j=1
(nj−npj)2 npj .
e pogledamo verjetnosti pj za ve£je m, ugotovimo, da je zelo majhna verjetnost, da se znotraj bloka pojavi 5 enakih ²tevil. e je najmanj²a verjetnost izida manj²a od 0,001, potem je smiselno zdruºiti izida z najmanj²ima verjetnostima. Verjetnost zdruºenega izida je vsota verjetnosti zdruºenih izidov. tevec zdruºenega izida je vsota ²tevcev zdruºenih izidov. Dobimo 4 izide in njihove verjetnosti ozna£imo s p11, p12, p13, p14, njihove ²tevce pa z n11, n12, n13, n14. e je najmanj²a verjetnost ²e zmeraj manj²a od0,001, postopek ponovimo. Kon£amo, ko so verjetnosti vseh izidov ve£je od 0,001 ali pa nam ostaneta le ²e dva izida. Po ponovljenihi-korakih zdruºe- vanja dobimo r= 5−iizidov z verjetnostmipi1, pi2, . . . , pir in ²tevcini1, ni2, . . . , nir. Sledi
χ2(n) =
r
∑︂
j=1
(nij −npij)2 npij .
3.5. Permutacijski test. Permutacijski test preverja, ali se morda katera permu- tacija v zaporedju pojavlja z ve£jo verjetnostjo kot katera druga. To bi nakazovalo na predvidljive vzorce v zaporedju generiranih ²tevil. Zaporedje generiranih slu£aj- nih ²tevil razdelimo na N blokov po r ²tevil. e so vsa ²tevila v bloku razli£na, denirajo eno od r! moºnih permutacij znotraj bloka. Vse te permutacije so enako verjetne. Ker se ²tevila znotraj bloka lahko tudi ponovijo, so moºni izidi poskusa vse
moºne permutacije in izid, kjer vsa ²tevila znotraj bloka niso razli£na. Verjetnost, da vsa ²tevila v bloku niso razli£na, je
p
¯ = 1−m(m−1)· · ·(m−r+ 1)
mr .
Verjetnost posamezne permutacije je
p= m(m−1)· · ·(m−r+ 1)
mr · 1
r!.
Test izvedemo tako, da najprej vse moºne izide o²tevil£imo. Vpeljemo ²tevce nj, ki
²tejejo pojavitevj-te permutacije. tevecn0 naj ²teje ²tevilo blokov, kjer vsa ²tevila med seboj niso razli£na. Potem pogledamo vsak blok posebej. e se v bloku neko
²tevilo ponovi, pove£amo ²tevec n0 za 1. e so vsa ²tevila razli£na, najmanj²e prei- menujemo v1, drugo najmanj²e v 2in tako naprej, tako da zadnjega preimenujemo v r. Dobimo permutacijo prvihr ²tevil in pove£amo ²tevec dobljene permutacije za 1. Tako preverimo vse bloke. Vsota vseh ²tevcev mora biti na koncu enaka ²tevilu vseh blokov N = nr. Sledi
χ2(N) = (n0−N p¯)2 N p¯ +
r!
∑︂
j=1
(nj −N p)2 N p .
3.6. Test nara²£ajo£ih in padajo£ih podzaporedij. Test preverja odvisnost med generiranimi ²tevili tako, da poi²£emo dolºine vseh najdalj²ih strogo padajo£ih ali strogo nara²£ajo£ih podzaporedij v generiranem zaporedju ²tevil. Obravnavanje nara²£ajo£ih in padajo£ih podzaporedij je simetri£no. Zato pri testiranju na prvi polovici zaporedja uporabimo test nara²£ajo£ih podzaporedij, na drugi polovici pa test padajo£ih podzaporedij. Izra£unajmo verjetnost, da je podzaporedje dolºine j ∈Nali ve£. Medm²tevili izberemoj razli£nih, ki bodo nastopala v podzaporedju.
Ta lahko razporedimo v strogo nara²£ajo£e ali strogo padajo£e podzaporedje na en sam na£in. Vseh moºnih razporeditevm²tevil v podzaporedje dolgoj, kjer se ²tevila lahko ponavljajo, je (︁1
m
)︁j
. Torej, £e z R ozna£imo dolºino podzaporedja, velja P(R ≥j) =
(︃m j
)︃ (︃
1 m
)︃j
.
Verjetnost, da je dolºina podzaporedja dolga natanko j, zra£unamo kot pj =P(R =j) =P(R≥j)−P(R≥j+ 1).
Natan£nost χ2 testa zagotovimo z zadostnim ²tevilom podzaporedij. Test izvedemo tako, da vpeljemo ²tevce nj, ki ²tejejo podzaporedja dolºine j za j ∈ N. Na prvi polovici generiranega zaporedja poi²£emo najdalj²a nara²£ajo£a podzaporedja in nji- hove dolºine. Z vsakim najdenim podzaporedjem pove£amo primeren ²tevec za 1. Enako ponovimo na drugi polovici generiranega zaporedja, le da i²£emo najdalj²a padajo£a podzaporedja. Na koncu je vsota ²tevcev enaka ²tevilu najdenih podza- poredij N. Verjetnost, da se pojavi dalj²e podzaporedje, je veliko manj²e, kot da se pojavi kraj²e. Zato je smiselno zdruºiti ²tevilo dalj²ih zaporedji v isti izid. Zdruºimo zadnjih toliko izidov, da velja:
p
¯ =P(R ≥K)≥0,001.
tevec zdruºenega izida je vsota ²tevcev zdruºenih izidov n¯K =nK +nK+1+· · ·+nm.
Skupno tako dobimo K moºnih izidov. e bi ºeleli test nara²£ajo£ih in padajo£ih podzaporedij pretvoriti naχ2 test, bi pri²li do problema. Najdena podzaporedja niso zares neodvisna med sabo. Vsako podzaporedje (razen zadnje) se zaklju£i, ker nasle- dnje ²tevilo v primeru nara²£ajo£ih podzaporedij ni ve£je od svojega predhodnika, oziroma ni manj²e od svojega predhodnika v primeru padajo£ih podzaporedij. Hkrati pa to isto ²tevilo za£enja novo podzaporedje. Torej sta sosednji podzaporedji odvi- sni. χ2 testna statistika pa zahteva neodvisnost. V tem primeru imamo dva moºna pristopa. Enostavnej²i je ta, da prilagodimo izvedbo testa. Prilagodimo jo tako, da ko najdemo primerno podzaporedje in ²tevilo, ki ga zaustavi, to ²tevilo presko£imo in ga ne ²tejemo k novemu podzaporedju. Novo podzaporedje za£nemo z naslednjim
²tevilom v vrsti. S tem, ko v novem podzaporedju ne bomo upo²tevali ²tevila, ki je zaustavilo prej²nje podzaporedje, bodo podzaporedja med sabo neodvisna in lahko izra£unamo
χ2(N) = (n¯K−N p¯)2 N p¯ +
K−1
∑︂
j=1
(nj −N pj)2 N pj .
Poglejmo ²e drugi pristop. V tem primeru bodo podzaporedja med sabo odvisna, zato ne bomo mogli uporabiti χ2 testa. Izpeljali bomo drugo testno statistiko in dokazali, da ima tudi ta χ2 porazdelitev. Osredoto£imo se le na nara²£ajo£a podza- poredja, saj je pri padajo£ih postopek simetri£en. Imamo zaporedje n ²tevil. De- nirajmo indikator
Zki =
{︄1; £e se na mestu i za£ne novo nara²£ajo£e podzaporedje dolgo k ali ve£
0; sicer.
Ker generiramo ²tevila med 0 in m−1, je najdalj²e moºno podzaporedje dolgo m. Torej je 1≤k ≤m. tevilo podzaporedij dolºine ve£je ali enake k je
R′k:=Zk1+Zk2 +· · ·+Zkn. (6)
tevilo podzaporedij dolºine natanko k je
Rk :=R′k−R′k+1. (7)
Izra£unali bomo pri£akovano vrednost Rk in kovarianco Rk in Rl za k, l ∈ N, ki merita odvisnost med Rk inRl. Pri tem si bomo pomagali s pri£akovano vrednostjo R′kin kovariancoR′kinR′l, saj velja (7). Na generirana cela ²tevila na intervalu[0, m−
1]lahko gledamo, kot da so dobljena na podlagi enakomernih slu£ajnih spremenljivk.
Torej lahko £len zaporedja Yi deniramo kotYi =⌊dUi⌋za nekid∈N, kjer soUi za i ∈ {1, . . . , n} neodvisne in enakomerno porazdeljene realne slu£ajne spremenljivke na intervalu med 0 in 1. Ker so U1, U2, . . . , Un z verjetnostjo 1 razli£na ²tevila, lahko zaporedjeU1, U2, . . . , Ungledamo kot permutacijon razli£nih ²tevil. Opazovali bomo le zaporedje U1, U2, . . . , Un. Dobljeni test lahko po viru [3] aproksimativno uporabimo tudi za generatorje celih ²tevil.
Trditev 3.2. Naj bo v zaporedju generiranih n ²tevil. Pri£akovana vrednost slu£ajne spremenljivke R′k za k∈N je
E(R′k) = (n+ 1)k
(k+ 1)! − k−1 k! . (8)
Dokaz. Izberimo si mestoi∈Nv zaporedjun generiranih ²tevil. Ker velja zveza (6), lahko do pri£akovane vrednosti R′k pridemo s pomo£jo pri£akovanih vrednosti Zki. Izra£unajmo najprej P(Zki = 1). e se na mestui ne za£ne podzaporedje dolºinek
ali ve£, je Zki enak 0. Poi²£imo, za koliko permutacijn ²tevil velja, da se na mestu i za£ne nara²£ajo£e podzaporedje dolºine k ali ve£. Ozna£imo permutacijo n ²tevil kot U1, U2, . . . , Un. e je Zki = 1, mora v primeru, ko je 1< i≤n−k+ 1 veljati
Ui−1 > Ui < Ui+1 <· · ·< Ui+k−1
Izra£unajmo ²tevilo permutacij, ki zado²£ajo temu pogoju. V zapisu nastopa k+ 1 elementov. Izberemo jih lahko na (︁ n
k+1
)︁ na£inov. Da jih postavimo v ºeljeno vrsto, imamok moºnosti, saj mora najmanj²i element med izbranimi vedno stati na i-tem mestu, na mestu i−1 pa lahko stoji poljuben izmed preostalih k. Ostali elementi morajo biti razvr²£eni po velikosti, zato je njihovo mesto enoli£no dolo£eno. Preostale n−k−1elemente, ki ne nastopajo v zgornji vrsti, lahko razvrstimo na (n−k−1)!
na£inov. Na²li smo
(︃ n k+ 1
)︃
·k·(n−k−1)!
permutacij. e je i= 1≤n−k+ 1, izra£unamo podobno. Veljati mora U1 < U2 <· · ·< Uk.
Sedaj ºelimo v vrsto postaviti k elementov, ki jih lahko izberemo na (︁n
k
)︁ na£inov.
Ker morajo biti postavljeni po velikosti, jih lahko razporedimo le na en na£in. Ostale elemente razvrstimo na (n−k)!na£inov. Skupaj je
(︃n k
)︃
·1·(n−k)!
moºnih permutacij, ki ustrezajo zgornjemu pogoju. e je i > n−k + 1, potem ne obstaja permutacija, ki bi na i-tem mestu za£ela podzaporedje dolºine k ali ve£.
Torej verjetnost, da je podzaporedje z za£etkom na mestu i dolgo k ali ve£, je
P(Zki = 1) =
⎧
⎪⎪
⎨
⎪⎪
⎩
(k+1n )·k·(n−k−1)!
n! ; £e je1< i≤n−k+ 1, (nk)·1·(n−k)!
n! ; £e jei= 1,
0; sicer.
e zapisano nekoliko poenostavimo, dobimo
(9) P(Zki = 1) =
⎧
⎪⎨
⎪⎩
k
(k+1)!; £e je 1< i≤n−k+ 1,
1
k!; £e je i= 1, 0; sicer.
S pomo£jo zveze (6) in verjetnosti (9) lahko izra£unamo pri£akovano vrednost R′k E(R′k) =E
(︄ n
∑︂
i=1
Zki )︄
=
n
∑︂
i=1
E(Zki)
=
n
∑︂
i=1
P(Zki = 1)
=P(Zk1 = 1) +
n−k+1
∑︂
i=2
P(Zki = 1)
= 1 k! +
n−k+1
∑︂
i=2
k (k+ 1)!
= 1
k! + k
(k+ 1)! ·(n−k)
= (n+ 1)k
(k+ 1)! − k−1
k! . □
Sedaj, ko imamo pri£akovano vrednost R′k, lahko izra£unamo kovarianco.
Trditev 3.3. Naj bo v zaporedju n generiranih ²tevil. Naj bosta k, l ∈ N in k ̸= l. Naj bo s = max(k, l). e je k+l ≤n, velja
cov(R′k, R′l) =E(R′s) + (n+ 1)
(︃(k+l)(1−kl) +kl
(k+ 1)!(l+ 1)! − 2(k+l) (k+l+ 1)!
)︃
+ + 2
(︃k+l−1 (k+l)!
)︃
+((k+l)2−k−l−2)kl−(k+l)2−k2l2+ 1 (k+ 1)!(l+ 1)! .
e je k+l > n, velja
cov(R′k, Rl′) = E(R′s)−E(Rk′)E(R′l).
Dokaz. Izberimo mesti i, j ∈ N v zaporedju generiranih ²tevil, za kateri velja i <
j ≤ n. Poleg ºe izra£unanih verjetnosti v prej²njem dokazu bomo potrebovali tudi P(ZkiZlj = 1). ProduktZkiZlj lahko zavzame vrednosti0in1. Vrednost bo neni£elna natanko tedaj, ko se bo na mestuiza£elo podzaporedje dolºine kali ve£, tj.Zki = 1, in ko se bo na mestu j za£elo podzaporedje dolºine l ali ve£, tj. Zlj = 1. Lo£imo primere, ko sta zaporedji med sabo neodvisni in velja i+k < j, ter ko sta odvisni in velja i+k =j. V prvem primeru, £e je i≥n−k−l+ 1 alij > n−l+ 1, tedaj ne obstajata tako dolgi zaporedji, ki bi se za£eli na mestih i in j. Zato naj velja i+k < j≤n−l+ 1. e je i̸= 1, potem imajo iskane permutacije obliko
Ui−1 > Ui < Ui+1 <· · ·< Ui+k−1· · ·Uj−1 > Uj < Uj+1 <· · ·< Uj+l−1. Prvo podzaporedje zahteva k+ 1 elementov, ki jih izberemo na (︁ n
k+1
)︁ na£inov. Da jih postavimo v ºeljeno vrsto, pa imamo k na£inov. Pogoju za drugo podzaporedje zadostimo tako, da izberemol+1elementov na(︁n−k−1
l+1
)︁na£inov. Te lahko postavimo na l moºnih na£inov. Preostale elemente, ki ne nastopijo v zgornji vrsti, poljubno razvrstimo na (n−k−l−2)! na£inov. Dobimo
(︃ n k+ 1
)︃
·k·
(︃n−k−1 l+ 1
)︃
·l·(n−k−l−2)!
moºnih permutacij. e je i = 1 in kljub temu velja i+k < j ≤ n−l + 1, i²£emo permutacije, ki bodo ustrezale
U1 < U2 <· · ·< Uk<· · ·< Uj−1 > Uj < Uj+1 <· · ·< Uj+l−1. Da razporedimo prvih k elementov, jih moramo le izbrati (︁n
k
)︁, saj jih lahko po velikosti razporedimo na en sam na£in. Da razporedimo elemente odj−1doj+l−1
mesta, pa imamo, enako kot prej, (︁n−k l+1
)︁·l moºnosti. Ostale elemente razporedimo na (n−k−l−1)! na£inov. Skupaj imamo
(︃n k
)︃
·
(︃n−k l+ 1
)︃
·l·(n−k−l−1)!
permutacij. Izra£unajmo verjetnost
P(ZkiZlj = 1) =
⎧
⎪⎪
⎨
⎪⎪
⎩
(k+1n )·k·(n−k−1l+1 )·l·(n−k−l−2)!
n! ; £e je i̸= 1 in i+k < j ≤n−l+ 1, (nk)·(n−kl+1)·l·(n−k−l−1)!
n! ; £e je i= 1 in i+k < j ≤n−l+ 1,
0; sicer.
Poenostavimo in dobimo (10) P(ZkiZlj = 1) =
⎧
⎪⎨
⎪⎩
k·l
(k+1)!·(l+1)!; £e jei̸= 1 ini+k < j≤n−l+ 1,
l
k!·(l+1)!; £e jei= 1 ini+k < j≤n−l+ 1,
0; sicer.
Izra£unati je potrebno samo ²e verjetnost P(ZkiZlj = 1), ko sta podzaporedji odvi- sni. Tedaj velja i+k = j. Podobno kot prej, £e za izbrane spremenljivke ne velja i≤n−k−l+ 1 in j ≤n−l+ 1, iskani podzaporedji ne obstajata. Zato naj velja i+k =j ≤n−l+ 1. V primeru, ko jei̸= 1, i²£emo permutacije, ki ustrezajo (11) Ui−1 > Ui < Ui+1 <· · ·< Ui+k−1 > Ui+k < Ui+k+1 <· · ·< Ui+k+l−1. Najprej izberemok+l+1elementov, ki jih bomo postavili v zgornjo vrsto, na(︁ n
k+l+1
)︁
na£inov. Prvi element v vrsti izberemo na k +l + 1 na£inov. e ne upo²tevamo prvega neena£aja, naslednjih k elementov izberemo na (︁k+l
k
)︁ na£inov. Ostane nam l elementov, ki jih po velikosti razporedimo enoli£no. Ker nismo upo²tevali, da je Ui−1 > Ui in Ui+k−1 > Ui+k, moramo od²teti permutacije, ki ne zado²£ajo tema pogojema. V primeru, ko je Ui−1 < Ui, imamo kar nara²£ajo£e podzaporedje dolºine k + 1. tevilo takih podzaporedij je (︁k+l+1
k+1
)︁, saj moramo izbrati k + 1 elementov, ki jih v nara²£ajo£o vrsto razporedimo na en sam na£in. Podobno, ko je Ui+k−1 <
Ui+k, dobimo podzaporedje dolºine k+l. Da dobimo tako podzaporedje, izberemo k+l elementov na (︁k+l+1
k+l
)︁ na£inov in jih enoli£no razvrstimo v nara²£ajo£o vrsto.
Permutacijo, ko veljata oba pogoja, smo ²teli dvakrat, zato moramo nazaj pri²teti eno. Preostalih n−k−l−1 elementov razporedimo poljubno. tevilo permutacij, ki zado²£ajo (11), je
(︃ n k+l+ 1
)︃
· (︃
(k+l+ 1) (︃k+l
k )︃
−
(︃k+l+ 1 k+ 1
)︃
−
(︃k+l+ 1 k+l
)︃
+ 1 )︃
·(n−k−l−1)!.
e je i= 1 in velja 1 +k =j ≤ n−l+ 1, potem i²£emo permutacije, ki se za£nejo kot
U1 < U2 <· · ·< Uk> Uk+1 < Uk+2 <· · ·< Uk+l. Izberemo k+l elementov na (︁ n
k+l
)︁ na£inov. Prvih k elementov izberemo na (︁k+l
k
)︁
na£inov in jih razporedimo le na en na£in. Tudi preostalih l elementov razporedimo enoli£no. e upo²tevamo, da je Uk > Uk+1, bomo morali od²teti ²e permutacijo, ko bi bili vsi elementi razporejeni po velikosti. Preostale elemente razporedimo na (n−k−l)!na£inov. Na²li smo
(︃ n k+l
)︃
·
(︃(︃k+l k
)︃
−1 )︃
·(n−k−l)!
ustreznih permutacij. Zadnja iskana verjetnost je torej
P(ZkiZlj = 1) =
⎧
⎪⎪
⎪⎪
⎨
⎪⎪
⎪⎪
⎩
(k+l+1n )·((k+l+1)(k+lk )−(k+l+1k+1 )−(k+l+1k+l )+1)·(n−k−l−1)!
n! ;
£e je i̸= 1 ini+k =j ≤n−l+ 1, (k+ln )·((k+lk )−1)·(n−k−l)!
n! ; £e jei= 1 ini+k=j ≤n−l+ 1,
0; sicer.
Poenostavljeno
(12) P(ZkiZlj = 1) =
⎧
⎪⎨
⎪⎩
k
(k+1)!·l!− (k+l+1)!k+l ; £e jei̸= 1 in i+k=j ≤n−l+ 1,
1
k!·l!− (k+l)!1 ; £e jei= 1 in i+k=j ≤n−l+ 1,
0; sicer.
Sedaj, ko imamo vse potrebne verjetnosti, izra£unajmo kovarianco. Pomagajmo si tudi s trditvijo 3.2.
cov(R′k, R′l) =E(R′kR′l)−E(R′k)E(R′l)
=E (︄
∑︂
1≤i,j≤n
ZkiZlj
)︄
−E(R′k)E(R′l)
= ∑︂
1≤i,j≤n
E(ZkiZlj)−E(R′k)E(R′l)
= ∑︂
1≤i,j≤n
P(ZkiZlj = 1)−E(R′k)E(R′l)
=
n
∑︂
i=1
P(ZkiZli = 1) + ∑︂
1≤i<j≤n
P(ZkiZlj = 1)+
+ ∑︂
1≤j<i≤n
P(ZkiZlj = 1)−E(R′k)E(R′l)
Pomagajmo si z verjetnostmi izra£unanimi v prej²njem dokazu. Vemo, da je P(ZkiZli = 1) =P(Zsi = 1),
kjer je s = max(k, l). e vstavimo (8), (10) in (12) in poenostavimo, dobimo cov(R′k, R′l) =E(R′s) + (n+ 1)
(︃(k+l)(1−kl) +kl
(k+ 1)!(l+ 1)! − 2(k+l) (k+l+ 1)!
)︃
+ + 2
(︃k+l−1 (k+l)!
)︃
+((k+l)2−k−l−2)kl−(k+l)2−k2l2+ 1 (k+ 1)!(l+ 1)! . To velja v primeru, ko je k+l ≤n. V primeru, ko je k+l > n, pa je kovarianca bolj preprosta. Namre£ ta primer se lahko zgodi le, £e se na istem mestu za£ne zaporedje dalj²e ali enako k in dalj²e ali enako l. Tedaj je
cov(R′k, R′l) =
n
∑︂
i=1
P(ZkiZli= 1)−E(R′k)E(R′l)
=E(R′s)−E(R′k)E(R′l). □ Sedaj lahko izra£unamo pri£akovano vrednost Rk in kovarianco Rk inRl, ki ju ne bomo poenostavljali.
(13) E(Rk) = E(R′k−R′k+1) =E(R′k)−E(R′k+1)
cov(Rk, Rl) = cov(R′k−R′k+1, R′l−R′l+1) (14)
= cov(R′k, R′l)−cov(R′k, R′l+1)−cov(Rk+1′ , Rl′) + cov(Rk+1′ , R′l+1) Tudi pri tem testu si bomo pomagali z zdruºevanjem izidov z manj²imi verjetnostmi.
Ker se verjetnosti izidov z dalj²anjem podzaporedij manj²ajo, zdruºimo vse izide, ko so zaporedja dalj²a od nekega t ∈ N. Naslednji izrek nam bo pomagal pri do- kazovanju porazdelitve novega testa. Ker je dokaz prezahteven, ga bomo izpustili.
Dokazan je v delu [5, izrek 1].
Izrek 3.4. Danih je n∈N generiranih ²tevil. Naj bodo Rk in Rk′ za vsak k∈N kot zgoraj denirane slu£ajne spremenljivke. Ko gren proti neskon£nosti, so R1, R2, . . . , Rt−1, Rt′ normalno porazdeljene z izra£unano pri£akovano vrednostjo (13) in kovari- anco (14).
Vrnimo se k izvajanju testa. Test izvedemo tako, da pre²tejemo ²tevilo nara²£ajo-
£ih podzaporedij Rk dolºin1≤k < tin ²tevilo nara²£ajo£ih podzaporedijR′tdolgih t ali ve£. Denirajmo
Qk :=Rk−E(Rk) za 1≤k < t in
Qt :=Rt′ −E(R′t).
Naj bo C matrika kovarianc, ki ima naij-tem mestu element cij = cov(Ri, Rj), na mestih it in tj pa elemente cit = cov(Ri, R′t) oziroma ctj = cov(R′t, Rj), kjer sta i, j ∈ {1,2, . . . , t−1}. Naj bo A = (aij) inverzna matrika matrike C. Ker velja izrek 3.4, ima produkt QTAQ za velike n po viru [3, stran 69] χ2 porazdelitev s t prostostnimi stopnjami. Zato ima test po viru [3, stran 69]
V = 1
n−t
∑︂
1≤i,j≤t
aij ·Qi·Qj
ob privzetku, da ni£elna domneva drºi,χ2porazdelitev. Na²li smo test, ki ne zahteva neodvisnosti med posameznimi izidi, vendar ima vseeno χ2 porazdelitev.
4. Testiranje na nivoju iger na sre£o
V tem poglavju bo predstavljeno testiranje izbranih iger na sre£o. Pri testiranju dolo£ene igre na sre£o je potrebno generirati izide. Slu£ajni vzorec je pri razli£nih igrah predstavljen druga£e. Pri ruleti je predstavljen s ²tevilkami, medtem ko je pri pokru slu£ajni vzorec predstavljen s posami£nimi delitvami kart. Pri zbiranju slu-
£ajnega vzorca mormo zagotoviti, da so vsi podatki pridobljeni pod enakimi pogoji.
Slu£ajni vzorec zberemo z generatorjem slu£ajnih ²tevil. Lahko bi ga izbrali tudi z dejanskim igranjem igre ali pa med ºe odigranimi igrami. Za £im bolj²o zanesljivost testa potrebujemo £im ve£ zbranih podatkov. Tudi dolºina posameznega vzorca je lahko izbrana poljubno. Tipi£no pa se zahteva20slu£ajnih vzorcev. Njihova dolºina naj bi bila taka, da imamo pri vsakem testu na voljo n = 1.000.000 izidov.
4.1. Holm-Bonferronijeva metoda. Ko testiramo generator igre na sre£o, na vsakem slu£ajnem vzorcu izvedemo ve£ razli£nih testov. Za vsak test dobimo drugo p-vrednost. Ker jih dobimo ve£, jih moramo zdruºiti v eno kon£no p-vrednost, na podlagi katere naredimo zaklju£ke o ni£elni domnevi. e je kon£nap-vrednost manj²a od izbrane stopnje tveganja α, potem ni£elno hipotezo zavrnemo, sicer pa o ni£elni hipotezi ne moremo povedati ni£esar. Pri zdruºevanju p-vrednosti si pomagamo z razli£nimi metodami. Nekatere metode zahtevajo neodvisnost p-vrednosti, kar pa je
teºko dose£i. Zato je bolj²e uporabiti metodo, ki zahteva le enakomerno porazdelje- nost p-vrednosti. Taka metoda je Holm-Bonferronijeva metoda.
Recimo, da imamoM p-vrednosti, ki testirajo isto ni£elno hipotezo. Ozna£imo jih s P1, P2, . . . , PM. Holm-Bonferronijevo metodo izvedemo tako, da vse p-vrednosti razvrstimo po vrsti v nara²£ajo£em vrstnem redu, da dobimo
P(1) ≤P(2) ≤ · · · ≤P(M). Denirajmo
P¯(i)= {︃
maxj≤i (M −j+ 1)·P(j) }︃
1
,
kjer je {x}1 = min(x,1)in i∈ {1,2, . . . , M}. Kon£no p-vrednost izra£unamo kot P = min
1≤i≤MP¯(i).
Metoda je dobra, saj zagotavlja, da bo napaka tipa I, £e se odlo£amo na podlagiP, manj²a od izbrane stopnje tveganja α. Ve£ o tem lahko najdemo v viru [2].
4.2. Deljenje kart. Ena najbolj igranih iger s kartami je enaindvajset oziroma blackjack. Cilj igralca je, da je vsota kart, ki jih dobi, £im bliºje 21, vendar ne ve£.
Med kartami je lahko med 1 in 8 kupov standardnih kart. Pri tej igri igralec igra proti delilcu in ne ostalim igralcem. Izidi igre so zmaga, izena£enje in poraz. Ker lahko igralec uporablja razli£ne strategije, je teºko dolo£iti to£ne verjetnosti izidov.
V takem primeru je bolj smiselno preveriti nepristranskost deljenja kart. Testiranje razdelimo na test enakomernosti in test raznolikosti, ki preverja, da so karte, ki jih dobi igralec, dovolj raznolike. V igri je lahko razli£no ²tevilo kupov standardnih kart, recimo, da jih vzamemoK. Pri testiranju ponavadi vzamemo kar najve£ji moºni K, v na²em primeru K = 8. Skupaj je v igri T = K ·52 kart. Ko se karte zme²ajo, dobimo naklju£no permutacijo vseh T kart. Ni£elna hipoteza, ki jo testiramo, je, da so vse te permutacije enako verjetne in med sabo neodvisne. Izberimo si stopnjo tveganja α= 0,05.
4.2.1. Test enakomernosti. MedT kartami imamo52razli£nih tipov kart. Tipe kart poljubno o²tevil£imo od 1 do 52. e si izberemo mesto v kupu kart, potem mora vsaka izmed 52-ih tipov kart z enako verjetnostjo zasesti izbrano mesto. Za vsako mesto v kupu kart bomo testirali ni£elno hipotezo, da razli£ne karte z enako verjetno- stjo zasedejo izbrano mesto. S tem bomo opravili T razli£nih testov. Za opravljanje testa potrebujemo slu£ajne vzorce. V primeru testiranja deljenja kart generiramo n = 1.000.000 permutacij T kart. Na vsakemu vzorcu opravimo vseh ²est testov, predstavljenih v poglavju 3.
4.2.1.1. Frekven£ni test. Za izbrano mesto j v permutaciji T kart deniramo izidk kot k-ti tip karte je na izbranem mestu j, kjer je k ∈ {1,2, . . . ,52}. Verjetnost posameznega izida je
p= 1 52.
Test izvedemo tako, da izberemo mestoj ∈ {1,2, . . . , T}. Vpeljemo ²tevcen1, n2, . . . , n52. Pogledamo vsako izmed n generiranih permutacij. e se na mestu i pojavi tip
