Testování generátorů náhodných čísel Při použití generátoru pseudonáhodných čísel v praxi je důležité ověřit, zda získaná posloupnost čísel má vlastnosti náhodného výběru ze zadaného rozložení: - typ rozložení - náhodnost - nezávislost. Obecné zásady pro testování: - ověřovaná posloupnost musí být dostatečně rozsáhlá - závěry se provádějí až po prozkoumání většího počtu posloupností - testované posloupnosti by měly mít různé výchozí hodnoty. 1. Testy shody rozložení a) Kolmogorovův – Smirnovův test Test je založen na porovnání teoretické a empirické distribuční funkce. Velké odchylky mezi těmito dvěma funkcemi budou svědčit o tom, že rozdíl mezi modelovými a vygenerovanými hodnotami není způsoben pouze náhodnými vlivy. Nechť X1, ..., Xn je náhodný výběr ze spojitého rozložení s distribuční funkcí Φ(x). Výběrovou distribuční funkci označíme Fn(x), tj. pro :Rx   xX;icard n 1 )x(F in  . Na hladině významnosti α testujeme nulovou hypotézu H0: Φ(x) = Fn(x) pro Rx  proti alternativě H1: Φ(x) ≠ Fn(x) pro aspoň jednu hodnotu x. Testová statistika má tvar:    xFxmaxD n Rx n   . Nulovou hypotézu zamítáme na hladině významnosti α, když Dn > Dn,α, kde Dn,α je tabelovaná kritická hodnota. Pro větší n lze kritickou hodnotu aproximovat výrazem   2 ln n2 1 D ,n . Upozornění: Při testování generátorů pseudonáhodných čísel přesně známe parametry rozložení, z něhož čísla generujeme, tudíž v K-S testu nemusíme používat modifikované kritické hodnoty. V MATLABu provádí K-S test funkce kstest.m. Příklad 1.: Bylo vygenerováno 10 000 pseudonáhodných čísel z Rs(0,1). Vygenerované hodnoty byly roztříděny do 10 ekvidistantních třídicích intervalů. Máme k dispozici jejich meze  1jj u,u  a absolutní četnosti nj:  1jj u,u  nj  1,0;0 985  2,0;1,0 1029  3,0;2,0 1005  4,0;3,0 1005  5,0;4,0 1002  6,0;5,0 970  7,0;6,0 1028  8,0;7,0 1032  9,0;8,0 960  1;9,0 984 Na hladině významnosti 0,05 ověřte K-S testem, že tyto hodnoty skutečně pocházejí z rozložení Rs(0,1). Řešení: Tabulku absolutních četností doplníme o hodnoty teoretické a výběrové distribuční funkce a vypočteme absolutní hodnoty jejich rozdílů. Největší z těchto absolutních hodnot porovnáme s kritickou hodnotou a pak rozhodneme o nulové hypotéze.  1jj u,u  nj Nj  x  xF10000    xFx 10000  1,0;0 985 985 0,1 0,0985 0,0015  2,0;1,0 1029 2014 0,2 0,2014 0,0014  3,0;2,0 1005 3019 0,3 0,3019 0,0019  4,0;3,0 1005 4024 0,4 0,4024 0,0024  5,0;4,0 1002 5026 0,5 0,5026 0,0026  6,0;5,0 970 5996 0,6 0,5996 0,0004  7,0;6,0 1028 7024 0,7 0,7024 0,0024  8,0;7,0 1032 8056 0,8 0,8056 0,0056  9,0;8,0 960 9016 0,9 0,9016 0,0016  1;9,0 984 10000 1 1 0 Největší rozdíl v absolutní hodnotě je 0,0056. To je realizace testové statistiky, kterou porovnáme s aproximací kritické hodnoty počítané podle vzorce   2 ln n2 1 D ,n : 0136,0 05,0 2 ln 100002 1 D 05,0;10000    . Jelikož testová statistika je menší než kritická hodnota, nelze na hladině významnosti 0,05 zamítnout hypotézu, že vygenerovaná data pocházejí z rozložení Rs(0,1). Kolmogorovův - Smirnovův test pro rozložení Rs(0,1) v MATLABu Vygenerujeme n = 10000 realizací z Rs(0,1): n=10000; realizace=unifrnd(0,1,n,1); Vypočteme hodnoty distribuční funkce rozložení Rs(0,1) v bodech vygenerovaných realizací: Fi=unifcdf(realizace,0,1); Zavoláme funkci kstest: [h,p,ksstat,cv]=kstest(realizace,[realizace,Fi]) Vstupní parametry: realizace … sloupcový vektor realizací [realizace,Fi] … matice nx2 obsahující vektor realizací a vektor hodnot distribuční funkce rozložení Rs(0,1) Výstupní parametry: h … nabývá hodnoty 0, když nulovou hypotézu nezamítáme na hladině významnosti 0,05 a hodnoty 1, když zamítáme na hladině významnosti 0,05 p … p-hodnota ksstat … hodnota testové statistiky cv … kritická hodnota b) Test χ2 dobré shody Testujeme hypotézu, která tvrdí, že náhodný výběr X1, ..., Xn pochází z rozložení s distribuční funkcí Φ(x). Spojitý případ: Je-li distribuční funkce spojitá, pak data rozdělíme do r třídicích intervalů  1jj u,u  , j = 1, ..., r. Zjistíme absolutní četnost nj j-tého třídicího intervalu a vypočteme pravděpodobnost pj, že náhodná veličina X s distribuční funkcí Φ(x) se bude realizovat v j-tém třídicím intervalu. Platí-li nulová hypotéza, pak pj = Φ(uj+1) - Φ(uj). Diskrétní případ: Má-li distribuční funkce nejvýše spočetně mnoho bodů nespojitosti, pak místo třídicích intervalů použijeme varianty x[j], j = 1, …, r. Pro variantu x[j] zjistíme absolutní četnost nj a vypočteme pravděpodobnost pj, že náhodná veličina X s distribuční funkcí Φ(x) se bude realizovat variantou x[j]. Platí-li nulová hypotéza, pak          j xx jj xXPxlimxp j   . Provedení testu pro diskrétní i spojitý případ Testová statistika:       r 1j j 2 jj np npn K . Platí-li nulová hypotéza, pak K ≈ χ2 (r-1-p), kde p je počet odhadovaných parametrů daného rozložení. (Např. pro normální rozložení p = 2, protože z dat odhadujeme střední hodnotu a rozptyl.) Nulovou hypotézu zamítáme na asymptotické hladině významnosti α, když testová statistika K ≥ χ2 1-α(r-1-p). Aproximace se považuje za vyhovující, když teoretické četnosti npj ≥ 5, j = 1, ..., r. Závažnost rozdílu mezi pozorovanými četnostmi a teoretickými četnostmi lze pro každý index j orientačně posoudit porovnáním vypočítaného sčítance   j 2 jj np npn  s hodnotou 3,84 (to je kvantil  195,0 2  ). Jestliže některý sčítanec převýší tuto hodnotu, lze předpokládat, že odchylka od modelu se nachází právě v této oblasti hodnot. χ2 test dobré shody v MATLABu provádí funkce chi2gof.m Příklad 2.: Na hladině významnosti 0,05 ověřte χ2 testem dobré shody, zda data z příkladu 1 pocházejí z rozložení Rs(0,1). Řešení: Tabulku absolutních četností doplníme o pravděpodobnosti pj, teoretické četnosti npj a jednotlivé sčítance   j 2 jj np npn  vstupující do testové statistiky K.  1jj u,u  nj pj npj   j 2 jj np npn   1,0;0 985 0,1 1000 0,225  2,0;1,0 1029 0,1 1000 0,841  3,0;2,0 1005 0,1 1000 0,025  4,0;3,0 1005 0,1 1000 0,025  5,0;4,0 1002 0,1 1000 0,004  6,0;5,0 970 0,1 1000 0,900  7,0;6,0 1028 0,1 1000 0,784  8,0;7,0 1032 0,1 1000 1,024  9,0;8,0 960 0,1 1000 1,600  1;9,0 984 0,1 1000 0,256 Testová statistika:   684,5256,0841,0225,0 np npn K r 1j j 2 jj      Kritický obor:     ;919,16,9W 95,0 2 Protože se testová statistika nerealizuje v kritickém oboru, nemůžeme na hladině významnosti 0,05 zamítnout hypotézu, že data pocházejí z rozložení Rs(0,1). Test dobré shody pro rozložení Rs(0,1) v MATLABu Funkce chi2gof.m implicitně třídí data do 10 intervalů. [h,p] = chi2gof(realizace,'cdf',@unifcdf) Vstupní parametry: realizace … sloupcový vektor realizací 'cdf' … parametr, který dává funkci na vědomí, že bude použita distribuční funkce nějakého rozložení @unifcdf … označení distribuční funkce rovnoměrného spojitého rozložení Výstupní parametry: h … nabývá hodnoty 0, když nulovou hypotézu nezamítáme na hladině významnosti 0,05 a hodnoty 1, když zamítáme na hladině významnosti 0,05 p … p-hodnota 2. Testy náhodnosti Nechť x1, …, xn je posloupnost navzájem různých čísel generovaných ze spojitého rozložení (jsou-li dvě sousední hodnoty stejné, jednu vyškrtneme). Na hladině významnosti α testujeme nulovou hypotézu H0: posloupnost je náhodná proti alternativě H1: posloupnost není náhodná. a) Test založený na bodech zvratu Tento test zkoumá, zda kolísání hodnot podle velikosti se v dané posloupnosti mění dostatečně rychle. Není vhodný pro testování existence trendu, protože vychází pouze z lokálních vlastností posloupnosti. Číslo xi se nazývá bodem zvratu, když obě sousední čísla jsou současně buď větší než xi nebo menší než xi, tj. platí-li buď xi-1 > xi < xi+1 nebo xi-1 < xi > xi+1. Konstrukce testové statistiky: Označme Y celkový počet bodů zvratu v posloupnosti x1, …, xn. Platí-li H0, pak statistika Y má asymptoticky normální rozložení se střední hodnotou     3 2n2 YE   a rozptylem   90 29n16 YD   , tedy standardizovaná statistika    1,0N 90 29n16 3 2n2 Y U      . Kritický obor:    ,uu,W 2/12/1 Pokud WU  , nulovou hypotézu zamítáme na asymptotické hladině významnosti α. Příklad 3: Bylo vygenerováno 28 pseudonáhodných čísel z Rs(0,1): 0,39 0,94 0,17 0,16 0,80 0,63 0,59 0,92 0,16 0,51 0,39 0,16 0,67 0,03 0,67 0,73 0,67 0,80 0,27 0,75 0,58 0,86 0,49 0,43 0,86 0,08 0,66 0,60 Pomocí testu založeného na bodech zvratu ověřte na hladině významnosti 0,05 hypotézu, že tato posloupnost je náhodná. Řešení: 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 Celkem zjistíme Y = 21 bodů zvratu. Testová statistika:     699,1 90 292816 3 2282 21 90 29n16 3 2n2 Y U          . Kritický obor: W =     ,96,196,1,,uu, 975,0975,0 . Protože testová statistika s nerealizuje v kritickém oboru, nelze na hladině významnosti 0,05 zamítnout hypotézu, že daná posloupnost je náhodná. Výpočet v MATLABu: Test založený na bodech zvratu je prováděn pomocí funkce body_zvratu.m: function [H,P,U]=body_zvratu(x,alfa) % funkce testuje nahodnost posloupnosti pomoci bodu zvratu % synatxe: [H,P,U]=body_zvratu(x,alfa) % vystupni parametry: % H ... vysledek testu: 1 ... H0 zamitame, 0 ... H0 ... nezamitame % P ... vypocitana p-hodnota % U ... realizace testove statistiky % vstupni parametry: % x ... sloupcovy vektor hodnot testovane posloupnosti % alfa ... hladina vyznamnosti n=size(x,1); Y=0; for i=2:n-1 if ((x(i)>x(i-1))&(x(i)>x(i+1)))|((x(i)alfa H=0; end Použijeme-li tuto funkci na data z příkladu 3, dostaneme výsledky: [H,P,U]=body_zvratu(x,alfa) H = 0 P = 0.0893 U = 1.6994 Protože p-hodnota je 0,0893, nemůžeme na hladině významnosti 0,05 zamítnout hypotézu o náhodnosti dané posloupnosti. b) Test znamének diferencí Tento test zkoumá, zda posloupnost neobsahuje dlouhé řady čísel jdoucích za sebou vzestupně nebo sestupně. Používá se k ověření existence trendu. Test je založen na počtu kladných 1. diferencí dané posloupnosti, tj. na počtu bodů růstu. Číslo xi se nazývá bodem růstu, když xi < xi+1. Konstrukce testové statistiky: Označme Y celkový počet bodů růstu v posloupnosti x1, …, xn. Platí-li H0, pak statistika Y má asymptoticky normální rozložení se střední hodnotou   2 1n YE   a rozptylem   12 1n YD   , tedy standardizovaná statistika  1,0N 12 1n 2 1n Y U      . Kritický obor: W =    ,uu, 2/12/1 Pokud WU  , nulovou hypotézu zamítáme na asymptotické hladině významnosti α. Příklad 4.: Na hladině významnosti 0,05 testujte pomocí testu znamének diferencí hypotézu, že data z příkladu 3 jsou náhodná. Řešení: 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 Celkem zjistíme Y = 12 bodů růstu. Testová statistika: 9649,0 12 128 2 128 12 12 1n 2 1n Y U          . Kritický obor: W =     ,96,196,1,,uu, 975,0975,0 . Protože testová statistika s nerealizuje v kritickém oboru, nelze na hladině významnosti 0,05 zamítnout hypotézu, že daná posloupnost je náhodná. Výpočet v MATLABu: Test znamének diferencí je prováděn pomocí funkce znamenka_diferenci.m: function [H,P,U]=znamenka_diferenci(x,alfa) % funkce testuje nahodnost posloupnosti pomoci znamenek diferenci % synatxe: [H,P,U]=znamenka_diferenci(x,alfa) % vystupni parametry: % H ... vysledek testu: 1 ... H0 zamitame, 0 ... H0 ... nezamitame % P ... vypocitana p-hodnota % U ... realizace testove statistiky % vstupni parametry: % x ... sloupcovy vektor hodnot testovane posloupnosti % alfa ... hladina vyznamnosti n=size(x,1); Y=0; for i=1:n-1 if x(i)alfa H=0; end Použijeme-li tuto funkci na data z příkladu 3, dostaneme výsledky: [H,P,U]=znamenka_diferenci(x,alfa) H = 0 P = 0.3346 U = -0.9649 Protože p-hodnota je 0,3346, nemůžeme na hladině významnosti 0,05 zamítnout hypotézu o náhodnosti dané posloupnosti. c) Test založený na Spearmanově koeficientu Tento test zkoumá, zda velikost generované hodnoty nezávisí na pořadí, v němž bylo číslo generováno (např. zda na počátku generované posloupnosti nejsou soustředěny nízké hodnoty a na konci vysoké). Na základě generované posloupnosti x1, …, xn utvoříme dvojice (1, x1), …, (n, xn). Předpokládáme, že tyto dvojice pocházejí z dvourozměrného rozložení s teoretickým Spearmanovým koeficientem pořadové korelace ρS. Na hladině významnosti α testujeme nulovou hypotézu H0: ρS = 0 proti H1: ρS ≠ 0. Označme Ri pořadí hodnoty xi v dané posloupnosti. Vypočteme Spearmanův koeficient pořadové korelace:         n 1i 2 i2S Ri 1nn 6 1r . Nulovou hypotézu zamítáme na hladině významnosti α ve prospěch alternativy, když │rS│≥ rS,1-α/2(n), kde rS,1-α/2(n) je kritická hodnota, kterou pro α = 0,05 a n ≤ 30 najdeme v tabulkách. Kritické hodnoty pro Spearmanův koeficient pořadové korelace pro n = 5, 6, …, 30, α = 0,05 n 975,0;Sr 95,0;Sr 5 0,9 0,8 6 0,8286 0,7714 7 0,745 0,6786 8 0,6905 0,5952 9 0,6833 0,5833 10 0,6364 0,5515 11 0,6091 0,5273 12 0,5804 0,4965 13 0,5549 0,478 14 0,5341 0,4293 15 0,5179 0,4429 16 0,5 0,4265 17 0,4853 0,4118 18 0,4716 0,3994 19 0,4579 0,3895 20 0,4451 0,3789 21 0,4351 0,3688 22 0,4241 0,3597 23 0,415 0,3518 24 0,4061 0,3435 25 0,3977 0,3362 26 0,3894 0,3299 27 0,3822 0,3236 28 0,3749 0,3175 29 0,3685 0,3113 30 0,362 0,3059 Příklad 5: Pro data z příkladu 3 testujte na hladině významnosti 0,05 hypotézu, že velikost generované hodnoty nezávisí na pořadí. Výpočet proveďte pomocí MATLABu. Řešení: Ve statistickém toolboxu MATLABu je implementována funkce tiedrank(x), která pro daný vektor x poskytne vektor pořadí, přičemž pro skupinky stejných hodnot spočítá průměrné pořadí. Postup výpočtu: Do proměnné x vložíme dané hodnoty. Utvoříme vektor y=[1:28]’; Pomocí funkce tiedrank zjistíme vektor pořadí: R=tiedrank(x); Pomocí funkce corrcoef spočteme koeficient korelace a odpovídající p-hodnotu: [rs,p]=corrcoef(y,R) Dostaneme r = 1.0000 0.0729 0.0729 1.0000 p = 1.0000 0.7124 0.7124 1.0000 Velikost Spearmanova koeficientu (rs = 0,0729) svědčí o velmi slabé přímé pořadové závislosti, která je na hladině 0,05 nevýznamná (p = 0,7124). Asymptotické varianty testu n > 20: lze použít testovou statistiku 2 S S 0 r1 2nr T    , která se v případě platnosti nulové hypotézy asymptoticky řídí rozložením t(n-2). Kritický obor:        ,2nt2nt,W 2/12/1 Hypotézu, že velikost generovaných hodnot nezávisí na pořadí, zamítáme na asymptotické hladině významnosti α, když t0  W. n > 30: lze použít testovou statistiku 1nrs  . Platí-li H0, pak 1nrs  ≈ N(0, 1). Nulovou hypotézu tedy zamítáme na asymptotické hladině významnosti α ve prospěch alternativy, když    ,uu,1nr 2/12/1S . 3. Testy nezávislosti a) Test založený na koeficientu autokorelace Tímto testem ověřujeme, zda existuje lineární závislost mezi sousedními nebo i vzdálenějšími členy posloupnosti x1, …, xn. Pro k < n je výběrový koeficient autokorelace k-tého řádu rk definován jako výběrový Pearsonův koeficient korelace dvojic (x1, xk+1), …., (xn-k, xn), o nichž předpokládáme, že pocházejí z dvourozměrného rozložení s koeficientem korelace ρk. Je-li k = 1, počítá se koeficient korelace mezi sousedními členy generované posloupnosti. Není vhodné počítat koeficienty autokorelace pro k > n/4. Posloupnost koeficientů autokorelace r1, r2, … se nazývá korelogram. Na hladině významnosti α testujeme nulovou hypotézu H0: ρk = 0 proti H1: ρk ≠ 0. Testová statistika knrT k0  se v případě platnosti nulové hypotézy asymptoticky řídí rozložením N(0,1). Kritický obor: W =    ,uu, 2/12/1 Pokud WT0  , nulovou hypotézu zamítáme na asymptotické hladině významnosti α, tedy hodnoty generované posloupnosti po k členech nelze považovat za lineárně nezávislé. Příklad 6: Pro data z příkladu 3 testujte na hladině významnosti 0,05 hypotézu, že mezi nimi neexistuje autokorelace 1. až 7. řádu. Řešení: Tabulka pro výpočet koeficientů autokorelace 1. až 7. řádu 1 X(i) 2 X(i+1) 3 X(i+2) 4 X(i+3) 5 X(i+4) 6 X(i+5) 7 X(i+6) 8 X(i+7) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 0,39 0,94 0,17 0,16 0,8 0,63 0,59 0,92 0,94 0,17 0,16 0,8 0,63 0,59 0,92 0,16 0,17 0,16 0,8 0,63 0,59 0,92 0,16 0,51 0,16 0,8 0,63 0,59 0,92 0,16 0,51 0,39 0,8 0,63 0,59 0,92 0,16 0,51 0,39 0,16 0,63 0,59 0,92 0,16 0,51 0,39 0,16 0,67 0,59 0,92 0,16 0,51 0,39 0,16 0,67 0,03 0,92 0,16 0,51 0,39 0,16 0,67 0,03 0,67 0,16 0,51 0,39 0,16 0,67 0,03 0,67 0,73 0,51 0,39 0,16 0,67 0,03 0,67 0,73 0,67 0,39 0,16 0,67 0,03 0,67 0,73 0,67 0,8 0,16 0,67 0,03 0,67 0,73 0,67 0,8 0,27 0,67 0,03 0,67 0,73 0,67 0,8 0,27 0,75 0,03 0,67 0,73 0,67 0,8 0,27 0,75 0,58 0,67 0,73 0,67 0,8 0,27 0,75 0,58 0,86 0,73 0,67 0,8 0,27 0,75 0,58 0,86 0,49 0,67 0,8 0,27 0,75 0,58 0,86 0,49 0,43 0,8 0,27 0,75 0,58 0,86 0,49 0,43 0,86 0,27 0,75 0,58 0,86 0,49 0,43 0,86 0,08 0,75 0,58 0,86 0,49 0,43 0,86 0,08 0,66 0,58 0,86 0,49 0,43 0,86 0,08 0,66 0,6 0,86 0,49 0,43 0,86 0,08 0,66 0,6 0,49 0,43 0,86 0,08 0,66 0,6 0,43 0,86 0,08 0,66 0,6 0,86 0,08 0,66 0,6 0,08 0,66 0,6 0,66 0,6 0,6 Korelogram a hodnoty testových statistik i 1 ri 2 n-i 3 T0 4 kvantil 5 rozhodnutí 1 2 3 4 5 6 7 -0,3235 27 -1,68096 1,959964 nezamítáme 0,0523 26 0,266679 1,959964 nezamítáme 0,1708 25 0,854 1,959964 nezamítáme -0,4572 24 -2,23981 1,959964 zamítáme 0,3121 23 1,496779 1,959964 nezamítáme -0,2657 22 -1,24624 1,959964 nezamítáme 0,0285 21 0,130603 1,959964 nezamítáme Závěr: V testovaných datech byla na hladině významnosti 0,05 prokázána autokorelace 4. řádu. b) Cochranův test Na hladině významnosti α testujeme nulovou hypotézu H0: ρ1 = ρ2 = … ρk = 0 (tj. všechny koeficienty autokorelace až do řádu k jsou nulové) proti alternativě H1: ρi ≠ 0 pro aspoň jeden index i. Testová statistika:   k 1i 2 irnQ Platí-li nulová hypotéza, Q se asymptoticky řídí rozložením χ2 (k). H0 tedy zamítáme na asymptotické hladině významnosti α, když Q ≥ χ2 1-α(k). Cochranův test má význam zvláště v případě, kdy jeden z autokorelačních koeficientů je významný (přitom může být významný pouze nahodile) a ostatní významné nejsou. Příklad 7: Pro data z příkladu 3 proveďte na hladině významnosti 0,05 Cochranův test. Řešení: Připomeňme, že koeficienty autokorelace byly ri -0,3235 0,0523 0,1708 -0,4572 0,3121 -0,2657 0,0285 Po dosazení do vzorce pro testovou statistiku dostaneme Q = 14,4034. Odpovídající kvantil: χ2 1-α(k) = χ2 0,95(7) = 14,067. Protože Q ≥ 14,067, H0 zamítáme na asymptotické hladině významnosti 0,05. Výpočet v MATLABu: Cochranův test je prováděn pomocí funkce Cochran.m: function [Q,chi,h,p]=Cochran(x,rad,alpha) % funkce provadi Cochranuv test autokorelace % vstupni parametry: x - vektor realizaci % rad - nejvyssi rad autokorelace % alpha - hladina vyznamnosti % vystupni parametry: % Q - hodnota testove statistiky % chi - kriticka hodnota % h zamitnuti (1)/nezamitnuti (0) nulove hypotezy % p-hodnota testu n=size(x,1); if rad>n/4 error('Rad autokorelace je prilis velky') end; Q=0; for i=1:rad [r,p]=corrcoef(x(1:n-i),x(i+1:n));Q=Q+r(1,2)^2; end; Q=n*Q;chi=chi2inv((1-alpha),rad); if Q