Test-chi.pdf

(47 KB) Pobierz
L.Kowalski
- Test losowości
Test losowości
χ
Testowanie losowości generatora ciągu binarnego.
2
Hipoteza zerowa
H
0
(
Ciąg ma charakter losowy).
Hipoteza alternatywna
H
1
(
Ciąg nie ma charakteru
losowego).
poziom istotności
α.
Weryfikacja powyższych hipotez za pomocą testu
χ
2
przebiega następująco:
1. Generujemy długi binarny ciąg losowy.
Dzielimy go na bloki np. 4-bitowe.
n – liczba bloków, n > 80,
k – liczba możliwych wartości w bloku, (dla
bloków 2-bitowych k = 4 liczb dwubitowych, dla
bloków 4-bitowych k = 16 liczb czterobitowych)
1
L.Kowalski
- Test losowości
1
2. Przyjmujemy,
że
p
i
=
k
.
3. Wyznaczamy liczbę n
i
wystąpień i – tej wartości
we wszystkich blokach, i = 1, 2, , k.
k
∑
n
i
=
n
i
=1
4. Obliczamy
(
n
i
−
np
i
)
1
(
n
i
)
u
n
=
∑
=
∑
−
n
np
i
n
i
=
1
p
i
i
=
1
k
2
k
2
5. Wyznaczamy zbiór krytyczny obustronny
K
=<
0 ;
k
1
> ∪ <
k
2
;
∞
)
,
gdzie
k
1
,
k
2
wyznaczamy z tablicy rozkładu
χ
2
z
k - 1 stopniami swobody .
P
(
Y
k
−
1
≥
k
1
)
=
1
−
α
2
,
2
P
(
Y
k
−
1
≥
k
2
)
=
α
2
L.Kowalski
- Test losowości
Podejmujemy decyzję:
odrzucamy hipotezę
H
0
, gdy
u
n
∈
K
przyjmujemy hipotezę
H
0
, gdy
u
n
∉
K
Test pokerowy 4 bitowy.
Hipoteza zerowa
H
0
(
Ciąg ma charakter losowy).
poziom istotności
α.
Generujemy długi binarny ciąg losowy. Dzielimy
go na bloki 4-bitowe.
n – liczba bloków, n > 80,
k – liczba możliwych wartości w bloku, dla
bloków 4-bitowych k = 16 liczb czterobitowych)
1
Przyjmujemy,
że
p
i
=
16
.
Wyznaczamy liczbę n
i
wystąpień i – tej wartości
we wszystkich blokach, i = 1, 2, , 16.
16
∑
n
i
=
n
i
=
1
3
L.Kowalski
- Test losowości
Obliczamy
16
u
n
=
n
∑
(
n
i
)
i
=
1
15
2
−
n
6. Wyznaczamy zbiór krytyczny obustronny
K
=<
0 ;
k
1
> ∪ <
k
2
;
∞
)
,
k
1
,
k
2
wyznaczamy z tablicy rozkładu
χ
2
z
gdzie
k - 1 stopniami swobody .
P
(
Y
k
−
1
≥
k
1
)
=
1
−
P
(
Y
k
−
1
≥
k
2
)
=
α
2
,
α
2
Podejmujemy decyzję:
Nie ma podstaw do odrzucenia ciągu gdy
k
1
<
u
n
<
k
2
4
L.Kowalski
- Test losowości
Wyznaczanie liczby jedynek w ciągu binarnym
Przykład. (test
monobitowy)
Wyznaczanie liczby jedynek w równomiernym
ciągu binarnym.
Niech n = 10000, poziom istotności
α
= 0,01.
H
0
(
p
=
0,5)
,
H
1
(
p
≠
0,5)
K
=
(
−∞
;
−
k
> ∪ <
k
;
∞
)
,
Φ
(
k
)
=
1
−
α
2
W
−
0,5
U
n
=
n
0,5(1
−
0,5)
gdzie W –
średnia
liczba jedynek w ciągu.
K
=
(
−∞
;
−
k
> ∪ <
k
;
∞
)
=
=
(
−∞
;
−
2,58
> ∪ <
2,58 ;
∞
)
5
Wtedy k = 2,58,

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin