Wieczorkowski R. - Komputerowe generatory liczb losowych.pdf

(3324 KB) Pobierz
VN1 \
V
\
*\
\
7
Spis treści
Przedmowa......................................................................................................................................................
Wykaz niektórych oznaczeń.............................................................................................................................
1. „ Liczby losowe"..........................................................................................................................................
2. Generatory liczb losowych o rozkładzie równomiernym..............................................................................
2.1. Wprowadzenie.......................................................................................................................................
2.2. Generatory liniowe................................................................................................................................
2.2.1. Opis....................................................................................................................................................
2.2.2. Okres generatora.............................................................................................................................
2.2.3. Struktura przestrzenna....................................................................................................................
2.2.4. Ogólne generatory liniowe..............................................................................................................
2.2.5. Parametry statystyczne...................................................................................................................
2.2.6. Wybór parametrów dla generatorów liniowych...............................................................................
2.3. Generatory oparte na rejestrach przesuwnych........................................................................................
2.4. Generatory Fibonacciego.......................................................................................................................
2.5. Kombinacje generatorów.......................................................................................................................
2.6. Uniwersalny generator liczb losowych o rozkładzie równomiernym......................................................
2.7. Generatory oparte na odejmowaniu z pożyczką i generator ULTRA......................................................
2.8. Generatory oparte na mnożeniu z przeniesieniem..................................................................................
2.9. Generatory nieliniowe............................................................................................................................
2.10. Uwagi o implementacji numerycznej...................................................................................................
2.11. Przykładowe implementacje w języku C ..............................................................................................
2.11.1.
Inicj owanie generatorów.......................................................................................................
2.11.2.
Ogólny generator liniowy.....................................................................................................
2.11.3. Generator Tauswortha z podrozdziału 2.3.....................................................................................
2.11.4. Generator uniwersalny z podrozdziału 2.6.....................................................................................
3. Generatory liczb losowych o dowolnych rozkładach prawdopodobieństwa..................................................
3.1. Ogólne metody konstrukcji generatorów liczb losowych o dowolnych rozkładach prawdopodobieństwa
3.1.1. Metoda odwracania dystrybuanty....................................................................................................
3.1.2. Metoda eliminacji...........................................................................................................................
3.1.3. Metoda superpozycji rozkładów......................................................................................................
3.1.4. Metoda ROU...................................................................................................................................
3.1.5. Rozkłady dyskretne.........................................................................................................................
3.2. Metody konstrukcji generatorów dla podstawowych rozkładów prawdopodobieństwa....................
3.2.1. Rozkłady dyskretne.........................................................................................................................
3.2.2. Rozkład wykładniczy......................................................................................................................
3.2.3. Rozkład normalny...........................................................................................................................
3.2.4. Rozkład gamma..............................................................................................................................
3.2.5. Rozkład beta...................................................................................................................................
3.2.6. Rozkład Cauchy'ego.......................................................................................................................
3.2.7. Rozkłady a-stabilne........................................................................................................................
3.3. Związki między rozkładami...................................................................................................................
4. Generatory liczb losowych o rozkładach wielowymiarowych.......................................................................
4.1. Przypadek ogólny..................................................................................................................................
4.2. Rozkłady równomierne w
Rm.................................................................................................................
4.2.1. Uwagi ogólne..................................................................................................................................
4.2.2. Rozkład równomierny na sferze i na kuli w
Rm...............................................................................
4.2.3. Rozkład równomierny na sympleksie i na powierzchni sympleksu..................................................
4.3. Wielowymiarowy rozkład normalny......................................................................................................
5. Testowanie generatorów liczb losowych.......................................................................................................
5.1. Metodyka testowania generatorów.........................................................................................................
5.2. Testy zgodności z rozkładem U(0,1)......................................................................................................
5.2.1. Test chi-kwadrat.............................................................................................................................
5.2.2. Test zgodności z rozkładem wielowymiarowym.............................................................................
5.2.3. Test OPSO......................................................................................................................................
2.4. Test Kołmogorowa................................................................................................................................
5.3. Testy zgodności rozkładów statystyk.....................................................................................................
5.3.1. Wprowadzenie................................................................................................................................
5.3.2. Testy oparte na statystykach pozycyjnych.......................................................................................
5.3.3. Test sum..........................................................................................................................................
5.3.4. Test
d2............................................................................................................................................
5.3.5. Test urodzin dla spacji....................................................................................................................
.. 4
.. 5
.. 6
.. 8
.. 8
10
10
11
12
13
13
14
16
19
20
21
22
23
24
26
26
26
27
27
28
30
30
30
32
43
50
53
56
56
61
63
67
72
74
76
77
82
82
83
83
84
86
88
89
89
91
91
91
92
93
94
95
95
96
96
97
5.3.6. Test najmniejszej odległości w parach...................................................................................................... 97
5.5. Testy serii....................................................................................................................................................... 100
5.6. Testy kombinatoryczne.................................................................................................................................... 102
5.6.1. Testpokerowy..........................................................................................................................................102
5.6.2. Testkolekcjonera...................................................................................................................................... 104
5.6.3. Test kolizji i test liczby pustych cel...........................................................................................................104
5.6.4. Testpermutacji.........................................................................................................................................105
5.6.5. Test oparty na rzędzie losowych macierzy binarnych................................................................................105
5.7. Testowanie generatorów za pomocą zadań kontrolnych................................................................................. 105
6.Prace cytowane....................................................................................................................................................... 106
Przedmowa
Losow anie prób w kontekście badań statystycznych (badania reprezentacyjne, sym ulacyjne
badania estym atorów , testów i statystycznych reguł decyzyjnych) oraz w kontekście obliczeń
numerycznych (metody M onte Carlo, klasyczne dla całek i rów nań z operatorami liniowymi i
now sze dla zadań optym alizacji), ja k rów nież sym ulacyjne badania m odeli probabilistycznych w
technice, ekonomii, naukach przyrodniczych i praktycznie we w szystkich dziedzinach wiedzy,
wymagają wyposażenia współczesnego kom putera w odpow iednie narzędzia. Takimi narzędziam i
są generatory liczb losowych.
K om putery trafiły pod strzechy i fala publikacji poświęconych różnym aspektom ich
w y k o rzy stan ia nie opada. Jesteśm y p rzek onani, że w czasie, jaki upłynie m iędzy postaw ieniem
przez nas ostatniej kropki w kom puteropisie tej książki a jej dotarciem do pierw szych
Czytelników , pojawi się co najmniej kilkadziesiąt nowych publikacji i program ów bezpośrednio
zw iązanych z tem atyką generatorów liczb losow ych. W ierzym y jednak, że to co proponujem y
Czytelnikom, będzie jeszcze przez pew ien czas aktualne, a przynajm niej ułatw i Im, i jeszcze
długo będzie ułatw iało, poruszanie się w gąszczu coraz to now ych osiągnięć w tej dziedzinie.
W arszaw a, maj 1997
A utorzy
Wykaz niektórych oznaczeń
a
[a]
{a}
Ml
a
mod
b
a
xor
b
A
C ov(X , Y)
D2(X)
E (X )
1
a
lm(A)
In
a
P{A}
R
Rn
sign
m
o
rn
Q
□
T
transpozycja w ektora
a
n a jw ię k sz a lic z b a całk o w ita, m n ie jsz a lub ró w n a
a
ułam kow a część liczby
a
norm a (długość) w ektora
a
reszta z dzielenia liczby
a p rze z b
operacja binarna (a +
b)
m od 2
dopełnienie zbioru
A
kow ariancja zm iennych losow ych
X i Y
w ariancja zm iennej losowej
X
w artość oczekiw ana zm iennej losowej
X
funkcja charakterystyczna zbioru A
m iara (L ebesgue'a) zbioru
A
w
R m
logarytm naturalny liczby
a
praw dopodobieństw o zdarzenia
A
zbiór liczb rzeczywistych
przestrzeń euklidesow a n-w ym iarow a
funkcj a znaku
funkcja gam m a E ulera
dystrybuanta rozkładu norm alnego A (0,1)
zdarzenie elem entarne
przestrzeń zdarzeń elem entarnych
koniec przykładu
koniec lem atu lub tw ierdzenia

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin