GENEROWANIE LICZB

LOSOWYCH

Liczby

Losowe

Wiele procesów zachodzących w przyrodzie, technice, ekonomii i życiu społecznym
sprawia wrażenie zjawisk losowych, a więc takich, dla których nie potrafimy
przewidzieć ich przyszłego przebiegu ani nie potrafimy ustalić przyczyn które je
wywołały. W każdym z tych przypadków, niezależnie od tego, czy udaje nam się
ustalić, jakie są przyczyny losowości zjawiska, możemy spróbować opisać to
zjawisko ilościowo, wykorzystując do tego celu pojęcie prawdopodobieństwa
rozumianego jako ilościowa miara niepewności – losowości. Podobnie jak w fizyce
i w przyrodzie, efekty losowe mogą występować również w świecie liczb

.

Liczba losowa to taka liczba, której wartość nie może zostać z góry przewidziana.
Sekwencję liczb losowych można stworzyć wykonując np. serię niezależnych rzutów
monetą i notując obserwowane wyniki pisząc 0 – gdy wynikiem rzutu jest reszka, oraz
1 – gdy wynikiem rzutu jest orzeł. Ponieważ prawdopodobieństwo zaobserwowania
reszki jest takie samo jak zaobserwowania orła i jest ono równe ½, więc zmienna
losowa – wynik rzutu – ma rozkład dwupunktowy i przyjmuje wartości 0 lub 1 z
jednakowym prawdopodobieństwem. Mówimy, że ta zmienna losowa ma rozkład
równomierny na zbiorze {0,1} lub rozkład dwupunktowy z parametrem p = ½.
W wyniku takiego postępowania otrzymamy więc na przykład następujący ciąg liczb:
1,0,0,1,1,... Taki ciąg liczb nazywa się ciągiem liczb losowych o rozkładzie
równomiernym na zbiorze {0,1} lub ciągiem liczb losowych o rozkładzie
dwupunktowym z parametrem p = ½.
Monetę, za pomocą której otrzymamy takie ciągi nazywa się generatorem liczb
losowych o rozkładzie równomiernym na zbiorze {0,1} lub generatorem liczb
losowych o rozkładzie dwupunktowym z parametrem p = ½.

zadania związane z badaniami reprezentacyjnymi np. badania pewnych zjawisk

społecznych na drodze szczegółowego opisu jednostek wybranych losowo z populacji
interesujących nas obiektów lub zadania ze statystycznej kontroli jakości, w których
partie różnych towarów opisuje się na podstawie badania losowo wybranych próbek
tych towarów;

zadania numeryczne rozwiązywane metodami Monte Carlo. Zadania numeryczne

zastępujemy zadaniem z rachunku prawdopodobieństwa, w taki sposób, że związek
pomiędzy rozwiązaniami obu zadań jest znany, a zadanie z rachunku
prawdopodobieństwa rozwiązujemy na drodze eksperymentu statystycznego.
Podstawową część tego eksperymentu stanowi losowanie próbki z odpowiedniej
populacji, a więc generowanie odpowiedniego ciągu liczbowego;

zadania związane z badaniem różnych zjawisk i procesów technicznych,

ekonomicznych, przyrodniczych na drodze symulowania (modelowania) tych
procesów i zjawisk na maszynach cyfrowych.

Zadania, do rozwiązywania których

używa się ciągów liczb losowych.

GENEROWANIE LICZB

LOSOWYCH

O ROZKŁADZIE

RÓWNOMIERNYM

Metody generowania cyfrowego

liczb losowych o rozkładzie

równomiernym

Podstawowymi generatorami liczb losowych są generatory fizyczne, takie jak:



moneta



urna o odpowiedniej zawartości



kostka do gry



ruletka itp.

są to urządzenia losowe.
Generatory tego typu mogą być przydatne do losowania nie dużych próbek dla
badań reprezentacyjnych albo do „ręcznego” rozwiązywania zadań metodami Monte
Carlo lub zadań z zakresu modelowania cyfrowego różnych zjawisk i procesów.

Przykładem fizycznego generatora liczb losowych jest generator korzystający ze
zjawiska promieniotwórczości: w pobliżu źródła promieniowania umieszcza się
licznik promieniowania i przyrosty wskazań tego licznika w kolejnych przedziałach
czasu o ustalonej długości traktuje się jako realizację pewnych zmiennych losowych.
Przyjmuje się, że liczba cząsteczek wypromieniowanych przez jednorodny izotop
jest zmienną losową o rozkładzie Poissona.

ZMIENNA LOSOWA O

ROZKŁADZIE POISSONA Z

PARAMETREM ct

2

1

2

0

2

0

ct

k

k

e

w

p















p ra w d o p o d o b i e ń s tw o , ż e w o d c i n k u c z a s u o d ł u g o ś c i t z o s ta n i e z a re j e s tro w a n a
p a rz y s ta l i c z b a c z ą s te k – o z n a c z a m y p rz e z p

0

Niech Z

1

będzie nową zmienną losową przyjmującą wartość 0, gdy stan licznika

promieniowania w okresie czasu o długości t zmieni się o liczbę parzystą, oraz
przyjmująca wartość 1 w przeciwnym przypadku. Zmienna losowa Z

1

ma więc

rozkład:

P { Z

1

= 0} = (1+) / 2

P { Z

1

= 1} = (1+) / 2

gdzie  = e

–2ct

Jeżeli intensywność c źródła promieniowania jest duża lub jeżeli odcinek czasu t jest

długi to  jest małe i rozkład zmiennej losowej Z

1

nieznacznie tylko różni się od

rozkładu dwupunktowego z parametrem p= ½.

ZMIENNA LOSOWA O

ROZKŁADZIE ROWNOMIERNYM

NA PRZEDZIALE (0,1)

zwykle rozumie się jako zmienna losowa x ciągła, dla której

























1

1

1

0

0

0

}

{

r

dla

r

dla

r

dla

r

X

Zrealizowanie takiej zmiennej losowej nie jest możliwe na żadnej maszynie
cyfrowej; w każdej maszynie można operować tylko skończoną liczbą różnych
wartości.
Można zauważyć, że jeżeli zmienna losowa, której kolejnymi realizacjami są liczby
takiego ciągu, jak : 0,1,1,1,0,0,1,0,1,1,0,0,0,1,0......, ma rozkład dwupunktowy
z parametrem p = 1/2 , to prawdopodobieństwo otrzymania każdej z liczb postaci :
0.0111, 0.0010, 0.1100, 0.0101 jest równe 2

-k

, a wiec otrzymany ciąg jest ciągiem

realizacji zmiennej losowej o rozkładzie równomiernym na przedziale(0,1).
Problemem związanym z eksploatacja generatorów fizycznych jest problem ich
stabilności: niewielkie zmiany własności fizycznych źródła lub zmiany warunków
otoczenia mogą pociągnąć za sobą istotne zmiany własności otrzymywanych ciągów
liczb losowych. W związku z tym generatory fizyczne wymagają dodatkowych
urządzeń testujących i korygujących, co znacznie komplikuje ich budowę.

OGÓLNA POSTAĆ

GENERATORÓW LICZB

LOSOWYCH

x

n+1

= a

0

x

n

+ a

1

x

n-1

+ ... + a

k

x

n-k

+ b (1)

Wszystkie liczby a

i

, b oraz x

i

we wzorze są liczbami całkowitymi z przedziału

[ 0,M ).

Generatory postaci będziemy nazywali generatorami liniowymi.

W szczególności:

generatory postaci: x

n+1

= cx

n

(2)

będziemy nazywali generatorami multyplikatywnymi,

generatory postaci: x

n+1

= a x

n

+ b, b  0 (3)

będziemy nazywali generatorami mieszanymi

generatory postaci: x

n+1

= x

n

+ x

n-1

(4)

będziemy nazywali generatorami Fibonacciego

Generator postaci, w którym wszystkie liczby a

i

są równe zeru lub jedności,

będziemy nazywali generatorem addytywnym lub uogólnionym generatorem
Fibonacciego.

Stałe a, b, c w powyższych wzorach są liczbami całkowitymi z przedziału (0,M).
Jeżeli stałe początkowe x

0

, x

1

,......,x

k

w generatorze(1); x

0

w generatorze (2), (3);

oraz x

0

i x

1

w generatorze (4) są liczbami naturalnymi, to wszystkie liczby x

n

otrzymywane z tych generatorów są liczbami naturalnymi. Jako liczby o rozkładzie
równomiernym na przedziale (0,1) przyjmujemy liczby :

r

n

= x

n

/ M

w ciągu (r

n

), n = 1,2,..... występuje co najwyżej M różnych liczb.

WŁASNOŚCI

STATYSTYCZNE

GENERATORÓW

Rozważając własności statystyczne generatorów traktujemy go jako pewne
„urządzenie losowe”, takie jak np.:



moneta,



urna z odpowiednim zapasem różnych kul,



ruletka

Kolejną liczbę X

n

produkowaną przez ten generator traktujemy więc jako zmienną

losową i weryfikacja, czy generator produkuje liczby losowe o żądanym rozkładzie
prawdopodobieństwa, sprowadza się do weryfikacji, czy ciąg X

o

, X

1

, ......., X

N –1

może być traktowany jako N-elementowa próbka prosta z określonej populacji, tz.
czy jest ona ciągiem niezależnych zmiennych losowych o jednakowym rozkładzie
prawdopodobieństwa.

Test statystyczne przeznaczone do weryfikacji generatorów liczb losowych można
podzielić na dwie grupy:



testy zgodności rozkładu



testy niezależności ( testy losowości próbki)

Testy uporządkowania próbki to wszelkiego rodzaju testy serii, testy statystyk
pozycyjnych, testy kombinatoryczne, takie jak np. test pokerowy . Testy te maja na
celu wykrycie ewentualnych tendencji w ciągach liczb produkowanych przez
generator, co prowadziłoby do dyskwalifikacji tego generatora.

WŁASNOŚCI ARYTMETYCZNE

GENERATORÓW

PROGRAMOWYCH

Generatory programowe

x

n+1

= f(x

n

) (1)

x

n+1

= g( x

n,

x

n-1, ......,

x

n-k+1

) (2)

argumenty funkcji f należą do zbioru liczb całkowitych; a wartości są liczbami
całkowitymi nieujemnymi, wtedy (1) jest generatorem multyplikatywny a generator
postaci (2) – generator liniowy.

Analiza arytmetycznych własności generatorów obejmuje zwykle
zagadnienie momentów, zagadnienie autokorelacji oraz zagadnienie
równomierności rozkładów wielowymiarowych.
Oceny generatorów programowych można również dokonać w inny
sposób, nie odwołując się przy tym do probalistyki. Zamiast analizować
różne własności ciągów liczb otrzymywanych z takich generatorów, takie
jak okresowość, równomierność rozkładu, autokorelacji, można ocenić
przydatność danego generatora do rozwiązania zadań określonego typu.
Generatory programowe, które spełniają wszystkie wymagania
sformułowane z punktu widzenia rozwiązania zadań określonego typu,
przyjęto nazwać generatorami liczb quasi – losowych. Generatory takie
ocenia się z punktu widzenia obliczania całek; do tego typu zadań można
sprowadzić większość zadań rozwiązywanych metodami Monte Carlo oraz
wiekszość zadań w badaniach reprezentacyjnych.

GENERATORY

LINIOWE

GENERATORY MULTYPLIKATYWNE

Generatory te zostały zaproponowane przez D. H. Lehmera w 1951 r.

Są to generatory postaci:

x

n+1

= cx

n

(mod M)

przy czym c, x

0

, oraz wszystkie x

n

, są liczbami całkowitymi z

przedziału [0,M ).

Wtedy liczby r

n

= x

n

/ M są liczbami z przedziału [0,1).

Generator multiplikatywny jest generatorem okresowym.

Przykład

Gdy M = 2

m

, m  3, max. jego okres jest równy 2

m-2

. Generator

multiplikatywny osiąga ten okres, gdy x

0

jest liczbą nieparzystą oraz

gdy c  3 (mod 8) lub c  5 (mod 8).

Zapis a  b (mod c) oznacza, że różnica a – b dzieli się przez c,

czyli że a = cv + b dla pewnego całkowitego v.

Na przykład dla m = 5, c = 11  3 (mod 8), x

0

= 1, otrzymujemy ciąg:

1, 11, 25, 19, 17, 27, 9, 3, 1,...; jest to ciąg o okresie 8.

GENERATOR MIESZANY

Generator mieszany został zaproponowany przez A. Rotenberga w 1960 r.

Jest to generator postaci:

x

n+1

= a x

n

+ b (mod M), b  0

przy czym a, b oraz x

0

są liczbami całkowitymi z przedziału [0,M ).

Za pomocą wzoru r

n

= x

n

/ M otrzymujemy liczby z przedziału (0,1).

Podobnie jak generator multiplikatywny generator mieszany jest generatorem
okresowym. W przypadku tym można jednak przez odpowiedni wybór parametrów
a oraz b uzyskać generator o pełnym okresie tzn. generator o okresie M.
Generator ma okres M, jeżeli:

(1)

b jest liczbą pierwszą względem M,

(2)

a  1 (mod p) dla każdego czynnika pierwszego p liczby M,

(3)

a  1 (mod 4), jeżeli 4 jest dzielnikiem liczby M

.

GENERATORY ADDYTYWNE

Najprostszym generatorem addytywnym jest generator Fibonacciego

x

n+1

= x

n

+ x

n-1

(mod M)

Jest to generator okresowy i w przypadku M = 2

m

jego okres jest równy 3 x 2

m-1

niezależnie od wyboru stałych początkowych x

0

i x

1

.

GENERATORY PUNKTÓW O ROZKŁADZIE

RÓWNOMIERNYM NA KOSTKACH

JEDNOSTKOWYCH W PRZESTRZENIACH

WIELOWYMIAROWYC

Jeżeli (R

n

), n = 0, 1, 2,..., jest ciągiem niezależnych zmiennych losowych o jednakowym

rozkładzie równomiernym na przedziale (0, 1), to k – wymiarowe zmienne losowe

(R

jk

, R

jk + 1

, ..., R

(j + 1)k – 1

), j = 0, 1, 2, ...,

są niezależne i mają jednakowy rozkład równomierny na kostce jednostkowej (0, 1)

k

.

Fakt ten doprowadził do sformułowania prostego algorytmu otrzymywania punktów
losowych o rozkładzie równomiernym na kostce (0, 1)

k

, jeżeli dany jest ciąg punktów

losowych na przedziale (0, 1) – kolejne wyrazy tego ciągu traktuje się jako kolejne
współrzędne generowanych punktów.

Takie postępowanie można zastosować bez żadnych
zastrzeżeń, gdy ciąg liczb losowych z przedziału (0, 1)
otrzymuje się za pomocą pewnego rzeczywiście losowego
urządzenia np. fizycznego generatora liczb losowych. W
przypadku, gdy ciąg taki otrzymuje się jako ciąg liczb
pseudolosowych

za

pomocą

pewnego

generatora

programowego, mogą pojawić się pewne odchylenia od
równomierności rozkładu produkowanych w ten sposób liczb,
a czasami otrzymanie takich punktów w opisany sposób jest
niemożliwe.
Ponieważ odchylenia od rozkładu równomiernego na kostce k
– wymiarowej pochodzą stąd, że kolejne liczby pseudolosowe
są na ogół ze sobą skorelowane, powstaje pomysł konstrukcji
ciągu punktów (r

1

, r

2

, ..., r

k

) o rozkładzie równomiernym na

kostce (0, 1)

k

w ten sposób, żeby każda współrzędna

generowanego punktu pochodziła z innego generatora liczb

Uogólniając zapiszemy generator punktów

r

(n)

= (r

1

(n)

, r

2

(n)

, ..., r

k

(n)

), n = 0, 1, 2, ...

w postaci

r

(n)

= Ar

(n-1)

+ b (mod 1)

przy czym A jest macierzą całkowitoliczbową stopnia k oraz b jest pewnym
wektorem o k składowych.

GENERATORY LICZB

LOSOWYCH

O DOWOLNYCH

ROZKŁADACH

PRAWDOPODOBIEŃST

WA

OGÓLNE METODY

KONSTRUKCJI

GENERATORÓW LICZB

LOSOWYCH O DANYM

ROZKŁADZIE

PRAWDOPODOBIEŃSTW

A

Metoda odwracania

dystrybuanty

Załóżmy, że F jest dystrybuantą pewnego rozkładu prawdopodobieństwa, a

X

i

, i = 1, 2, ...,

jest ciągiem niezależnych zmiennych losowych o rozkładzie
równomiernym na odcinku [ 0, 1]. Wówczas ciąg zmiennych losowych
zdefiniowanych jako

Y

i

= F

-1

(X

i

), i = 1, 2, ...,

jest ciągiem niezależnych zmiennych losowych o rozkładzie zadanym
dystrybuantą F.

Rozważmy dystrybuantę rozkładu wykładniczego F (x) = 1 – e

-x

Funkcją do niej odwrotną jest
F

-1

(y) = -ln (1 – y)

i dla niezależnych zmiennych losowych ciąg
Y

i

= - ln (1 – Xi), i = 1, 2, ...,

jest ciągiem niezależnych zmiennych losowych o rozkładzie wykładniczym.

Przykład

Metodę tę zaproponował J. von Neumann. Metoda ta oparta jest na tej własności
zmiennych losowych, że ich histogram z próby dąży do gęstości rozkładu.
W przypadku jednowymiarowym pozwala ona generować liczby losowe o
wartościach z przedziału (a, b) o rozkładzie zadanym gęstością prawdopodobieństwa

f(x) spełniającą warunek f(x)  c dla x (a, b). W przypadku wielowymiarowym

zmienna losowa przyjmuje wartości w kostce (a, b)

n

.

Metoda eliminacji

Algorytm dla rozkładu jednowymiarowego.

1. Generujemy dwie liczby losowe R

1

i R

2

, odpowiednio,

R

1

o rozkładzie U (a, b)

R

2

o rozkładzie U (0, c)

2. Sprawdzamy, czy R

2

 f (R

1

).

3. Jeżeli warunek jest spełniony, to przyjmujemy X = R

1

.

W przeciwnym wypadku eliminujemy wylosowany punkt i powtarzamy
losowanie z kroku 1.

Algorytm dla rozkładu wielowymiarowego

1. Generujemy n + 1 liczb losowych R

1

, R

2

, ..., R

n

, R

n + 1

, w tym

R

1

, R

2

, ..., R

n

o rozkładzie U (a, b),

R

n + 1

o rozkładzie U (0, c).

2. Sprawdzamy, czy R

n

+ 1  f ( R

1

, R

2

, ..., R

n

).

3. Jeżeli warunek jest spełniony, to przyjmujemy
(X

1

, X

2

, ..., X

n

) = (R

1

, R

2

, ..., R

n

)

W przeciwnym wypadku eliminujemy wylosowany punkt i powtarzamy
losowanie z kroku 1.

METODA SUPERPOZYCJI

ROZKŁADÓW

Metoda superpozycji rozkładów została zaproponowana przez J. W. Butlera.
Jeżeli przedstawimy gęstość f rozkładu zmiennej losowej x w postaci:

f(x) =

-





+

g

y

(x) h(y) dy

gdzie g

y

(x) jest gęstością pewnego rozkładu prawdopodobieństwa, zależną od

parametru y oraz h jest pewną gęstością prawdopodobieństwa.
Wzór ten może być odczytany w następujący sposób: zmienna losowa X ma rozkład
o gęstości g

y

zależnej od pewnego parametru y, który z kolei jest zmienną losową o

gęstości h; f jest wtedy gęstością bezwarunkowego rozkładu zmiennej losowej X.
Wynika stąd prosty sposób generowania zmiennej losowej X:

1. Wylosować y zgodnie z rozkładem gęstości h.
2. Wylosować x zgodnie z rozkładem o gęstości g

y

, z parametrem wylosowanym

w punkcie 1.

Kombinacja metody eliminacji

i metody superpozycji

Niech zmienna losowa X ma rozkład o gęstości p w postaci:



p(x) =  

n

p

n

(x)

n=0

gdzie 

n

 0, 

n

= 1,

natomiast p

n

, n = 0, 1, 2, ..., są pewnymi gęstościami prawdopodobieństwa

zależnymi od parametru n.
Każdą z gęstości p

n

przedstawimy w postaci: p

n

(x) = a

n

f

n

(x)g

n

(x)

przy czym a

n

> 0 są pewnymi stałymi,

f

n

są gęstościami prawdopodobieństwa oraz

funkcje g

n

spełniają warunki 0  g

n

(x)  1dla każdego x.

Algorytm generowania zmiennej

losowej X:

1. Wylosować n zgodnie z rozkładem P{n = i} = 

i

.

2. Dla wylosowanego w punkcie 1 parametru n wylosować x według rozkładu

prawdopodobieństwa o gęstości f

n

.

3. Wylosować liczbę R z populacji o rozkładzie równomiernym na przedziale

(0, 1).

4. Jeżeli R  g

n

(x) przyjąć x za realizację generowanej zmiennej losowej X;

w przypadku przeciwnym powtórzyć wszystkie obliczenia od punktu 1.

METODY KONSTRUKCJI

GENERATORÓW

LICZB LOSOWYCH

DLA

WYBRANYCH
ROZKŁADÓW

ROZKŁADY DYSKRETNE

Istnieją dwa sposoby generowania zmiennej losowej dyskretnej zaproponowane
przez G. Marsaglia.
Niech zmienna losowa X o wartościach a, b, ..., m ma następujący rozkład:

wartość zmiennej losowej

prawdopodobieństwo

a

b

c

d

e

f

g

h

i

j

k

m

0,023 = 0,0 + 0,02 + 0,003

0,038 = 0,0 + 0,03 + 0,008

0,074 = 0,0 + 0,07 + 0,004

0,103 = 0,1 + 0,00 + 0,003

0,148 = 0,1 + 0,04 + 0,008

0,206 = 0,2 + 0,00 + 0,006

0,140 = 0,1 + 0,04 + 0,000

0,101 = 0,1 + 0,00 + 0,001

0,093 = 0,0 + 0,09 + 0,003

0,037 = 0,0 + 0,03 + 0,007

0,026 = 0,0 + 0,02 + 0,006

0,011 = 0,0 + 0,01 + 0,001

Metoda pierwsza

Polega ona na zapamiętaniu w kolejnych miejscach pamięci 000 – 999 wartości:
„a” w miejscach 000 – 022,
„b” w miejscach 023 – 060,
„c” w miejscach 061 – 134,
...,
„m” w miejscach 989 – 999
i generowaniu wartości zmiennej losowej X jako zawartości pamięci o numerze R,
przy czym R jest zmienną losową o rozkładzie równomiernym na zbiorze liczb
{000, 001, ..., 999}

Metoda druga

Załóżmy, że są trzy urny, odpowiadające kolejnym cyfrom wartości
prawdopodobieństw.
Niech pierwsza urna zawiera: jedną kulę z wartością „d”, jedną z wartością „e”,
dwie z wartościami „f” itd.: skład poszczególnych urn:
I urna – 1d, 1e, 2f, 1g, 1h,
II urna – 2a, 3b, 7c, 4e, 4g, 9i, 3j, 2k, 1m,
III urna – 3a, 8b, 4c, 3d, ..., 1m.
Losujemy najpierw urnę: urnę I z prawdopodobieństwem 0,6, urnę II z
prawdopodobieństwem 0,35 lub urnę III z prawdopodobieństwem 0,050. Z wybranej
urny losujemy jedną kulę tak, żeby każda kula miała jednakową szansę
wylosowania. Wartość odczytana na tej kuli jest zmienną losową o danym
rozkładzie prawdopodobieństwa.

ROZKŁAD WYKŁADNICZY

Zmienna losowa W ma rozkład wykładniczy, jeżeli jej dystrybuanta wyraża się
wzorem:

P{W  w} = 1 – e

-cw

dla w  0

0 dla w < 0

gdzie c > 0 jest pewną stałą.
Niech X = cW
Zmienna losowa X ma rozkład wykładniczy z wartością oczekiwaną równą jakości.
Ponieważ ze zmiennej o rozkładzie wykładniczym z wartością oczekiwaną c = 1
można otrzymać zmienną losową o rozkładzie wykładniczym z dowolną wartością
parametru c, będziemy dalej rozpatrywali tylko zmienną losową X.

Metody generowania liczb

o rozkładzie

wykładniczym

Metoda odwracania dystrybuanty

zmiennej losowej z parametrem

równym ln 2

Algorytm generowania zmiennej losowej X:

1. Wygenerować zmienną losową p według rozkładu dyskretnego określonego

wzorem:

P{p = k} = (1/2)

k+1

, k = 0, 1, 2, ...,

2. Wygenerować zmienną losową R o rozkładzie równomiernym na przedziale

(0, 1) i obliczyć:

q = - log

2

(1 – R/2)

3. Obliczyć:

X = p + q

Metoda J. von Neumanna

metoda serii monotonicznych

Algorytm tej metody oparty jest na rejestrowaniu monotonicznych serii w ciągu
zmiennych losowych o rozkładzie równomiernym na przedziale (0, 1).
Obserwujemy kolejne serie postaci

R

0

 R

1

 R

2

 ...  R

n

< R

n+1

Numerując te serie kolejnymi liczbami 0, 1, 2, ... Numer pierwszej serii, w której n
jest liczbą nieparzystą, przyjmujemy za część całkowitą, natomiast wartość R

0

w tej

serii za część ułamkową generowanej liczby X

Metoda superpozycji

G. Marsaglia i M. Sibuya

Algorytm generowania zmiennej losowej o rozkładzie wykładniczym.

1. Wygenerować zmienną losową m zgodnie z rozkładem dyskretnym według wzoru:

p

i

= P{M = i} = (e

c

– 1) e

-c(i = 1)

, i = 0, 1, 2, ...,

2. Wygenerować zmienną losową N zgodnie z rozkładem dyskretnym według wzoru:

Q

i

= P{n = i} = c

i

/ e

c

– 1  1 / i!, i = 1, 2, 3, ...,

3. Wygenerować N zmiennych losowych R

1

, R

2

, ..., R

N

niezależnych o jednakowym

rozkładzie równomiernym na przedziale (0, 1).

4. Obliczyć u = min(R

1

, R

2

, ..., R

N

).

5. Obliczyć

X = M + u

Metoda przybliżania rozkładu

wykładniczego

za pomocą rozkładu dyskretnego

Algorytm generowania zmiennej losowej

1. Wygenerować liczbę losową R o rozkładzie równomiernym na przedziale

(0, 1). Jeżeli R < e

-4,6

= 0,010052, wykonać obliczenia według punktu 2,

w przeciwnym przypadku według punktu 3.

2. Obliczyć X = - ln R; koniec obliczeń.
3. Wygenerować zmienną losową V zgodnie z rozkładem dyskretnym

P{V = k / 10) = e

-k/10

– e

-(k+1)/10

4. Wygenerować ną losową R o rozkładzie równomiernym na przedziale (0, 1).
5. Obliczyć X = V + R/10; koniec obliczeń

ROZKŁAD NORMALNY

Ograniczymy się do rozważania zmiennej losowej X o rozkładzie normalnym
N(0, 1) z wartością oczekiwaną równą zeru i odchyleniem standardowym równym
jedności, tzn. rozkładu o gęstości:

(x) = 1 / 2  exp (- x

2

/2), - < x < +

W przypadku, gdy należy generować zmienną Z o rozkładzie normalnym N(, ),

generujemy X zgodnie z rozkładem jak wyżej i obliczamy Z według wzoru

Z = X + 

Metoda odwracania dystrybuanty

Funkcja odwrotna do dystrybuanty rozkładu normalnego nie może być
przedstawiona za pomocą łatwej do obliczeń formuły, dlatego poszukuje się zwykle
pewnych aproksymacji tej funkcji.

e

-x2/2

 4e

-kx

/ (1+e

-kx

)

2

, x>0

gdzie k = 8/. Korzystając z tej aproksymacji dla funkcji (x) na dodatniej półosi,

otrzymujemy następującą aproksymację dla dystrybuanty rozkładu normalnego
N(0, 1) uciętego do wartości dodatnich

y = (x) = (2 / 1 + e

-kx

) –1

i stąd przybliżenie dla funkcji odwrotnej

x = 1/k ln 1+y / 1 - y, 0<y<1

Jeżeli y ma rozkład równomierny na przedziale (0, 1), to x obliczone według wzoru:

1 1 + y

x =  ln

k 1 – y , 0<y<1

ma w przybliżeniu rozkład normalny ucięty do wartości dodatnich, tzn. rozkład
o gęstości:

P(x) = 2/  e

-x2

/2, x>0

a więc SX, gdzie S jest zmienną losową o rozkładzie

P{S = + 1} = P{S = -1} = ½

ma rozkład normalny N(0, 1).

Zastosowanie centralnego

twierdzenia granicznego

Najbardziej znana metoda generowania zmiennej losowej X o rozkładzie
normalnym polega na przybliżaniu jej za pomocą sumy niezależnych zmiennych
losowych R

1

, R

2

, ..., R

n

o jednakowym rozkładzie równomiernym na przedziale

(0, 1). Ponieważ ER

i

= ½ oraz D

2

R

i

= 1/12, więc dla dostatecznie dużych n zmienna

losowa
(R

1

+ R

2

= ... + R

n

) – n/2

X =
n/12

ma rozkład normalny N (0, 1).

Metoda eliminacji i superpozycji

rozkładów

G. Marsaglia i T. A. Bray zaproponowali generator liczb losowych o rozkładzie
normalnym skonstruowany metodą eliminacji i superpozycji rozkładów, przy użyciu

reprezentacji gęstości (x) tego rozkładu za pomocą sumy:

(x) = a

1

f

1

(x) + a

2

f

2

(x) + a

3

f

3

(x) + a

4

f

4

(x)

gdzie

f

1

, f

2

oraz f

3

są gęstościami skupionymi na pewnym przedziale

(-a, a), natomiast f

4

jest „ogonem” rozkładu normalnego na sumie

przedziałów (-, -a) oraz (a, +).

Losowanie z ogona rozkładu

normalnego

Losowanie z ogona (a, +) rozkładu normalnego można przeprowadzić np.

generując pary niezależnych zmiennych losowych R

1

i R

2

o jednakowym rozkładzie

równomiernym na przedziale (0, 1) dopóki nie będzie spełniony warunek

R

2

 a (a

2

– 2 ln R

1

)

-1/2

Wówczas za wygenerowaną wartość ogona (a, +) przyjąć liczbę

(a

2

– 2 ln R

1

)

1/2

,

a następnie wygenerowanej w ten sposób liczbie przypisać znak plus lub minus,
każdy z jednakowym prawdopodobieństwem

.

Wielowymiarowy rozkład normalny

G. E. Box i M. E. Muller zaproponowali generator dwuwymiarowej zmiennej
losowej o rozkładzie normalnym, korzystając z faktu, że jeżeli R1 i R2 są
niezależnymi zmiennymi losowymi o ozkładzie równomiernym na przedziale (0, 1),
to zmienne losowe

X

1

= (-2 ln R

1

)

1/2

cos2R

2

X

2

= (-2 ln R

1

)

1/2

sin2R

2

są niezależne i mają jednakowy rozkład normalny N(0, 1)

ROZKŁAD POTĘGOWY

Zmienna losowa X ma rozkład potęgowy z parametrem ( > 0), jeżeli jej

dystrybuanta F



(x) = P{X  x} wyraża się wzorem:

0 dla x < 0

F



(x) = x



dla 0  x  1

1 dla x > 1
G. Bankovi oraz A. Bekessy opracowali metody polegające na zastąpieniu

losowania według rozkładu jak wyżej z dowolnym parametrem 

kombinacją losowań z takich rozkładów z parametrem całkowitym.

Metoda pierwsza

Niech  będzie dowolną liczbą dodatnią. Dla każdego  > 0 można znaleźć taki ciąg

liczb całkowitych 1  a

1

 a

2

 ... a

N

, żeby liczba

N

1

 =



j = 1

a

j

różniła się od  o nie mniej niż . Zamiast generować zmienną o rozkładzie

potęgowym z parametrem  generujemy zmienną losową o rozkładzie z parametrem
. Można pokazać, że jeżeli R

1

, R

2

, ..., R

N

są zmiennymi losowymi niezależnymi o

rozkładzie równomiernym na przedziale (0, 1), to zmienna losowa X określona

wzorem:

X = max{R

a

1

1

, R

a

2

2

, ..., R

a

N

N

}

ma rozkład potęgowy z parametrem .

Metoda druga

Otrzymujemy następujący algorytm generowania zmiennej losowej:

1. Wygenerować zmienną losową R o rozkładzie równomiernym na

przedziale (0, 1)

2. Jeżeli R  1 - , wykonać obliczenia według punktu 3. W

przypadku przeciwnym – według punktu 4.

3. Wygenerować zmienną losową X według rozkładu potęgowego z

dystrybuantą F



(x) = x



; koniec obliczeń.

4. Wygenerować zmienną losową X

1

zgodnie z rozkładem

potęgowym o dystrybuancie F



(x) = x



oraz zmienną losową X

2

zgodnie z rozkładem o dystrybuancie F



(x) = x



.

5. Obliczyć X = X

1

X

2

; koniec obliczeń.

Metoda trzecia

Otrzymujemy następujący algorytm generowania zmiennej losowej:

1. Wylosować liczbę R zgodnie z rozkładem równomiernym na przedziale (0, 1)

i znaleźć takie k, że:

k-1

 

 

i

 R < 

i

i=1

 

2. Wylosować k + 1 liczb R

0

, R

1

, ..., R

k

i obliczyć:

X = (R

0

R

1

... R

k

)

1/

ROZKŁAD BETA

Zmienna losowa X ma rozkład beta z parametrami (, ), jeżeli gęstość jej rozkładu

prawdopodobieństwa wyraża się wzorem:
1
f(x) = x

-1

(1 – x)

-1

dla 0  x  1

B(, )

0 dla x < 0 lub x > 1

przy czym  > 0,  > 0, B(, ) = ()()/( +), () jest funkcją gamma.

Metoda pierwsza

Algorytm generowania zmiennej losowej beta z całkowitymi parametrami (, ):

1. Wygenerować  +  - 1 niezależnych zmiennych losowych R

1

, R

2

, ..., R

+-1

o jednakowym rozkładzie równomiernym na przedziale (0, 1).

2. Uporządkować wygenerowane wartości w ciąg niemalejący.

3. Wyznaczyć -tą liczbę z tego ciągu i przyjąć ją za wygenerowaną wartość

zmiennej losowej X.

Metoda druga

Algorytm generowania zmiennej losowej X o rozkładzie beta z całkowitymi

parametrami (, ):

1. Wygenerować dwie niezależne zmienne losowe U i V, jedną o rozkładzie

potęgowym F



(x) i drugą o rozkładzie potęgowym F

-1

(x).

2. Jeżeli U + V > 1, powtórzyć generowanie według punktu 1. W przypadku

przeciwnym przyjąć X = U.

Metoda trzecia

Ten sposób generowania zmiennej losowej X o rozkładzie beta z parametrami (, )

skonstruowano na podstawie twierdzenia, że jeżeli U i V są niezależnymi

zmiennymi losowymi o rozkładzie gamma, U z parametrem  oraz V z parametrem
, to zmienna losowa X określona wzorem:

X = U / U + V

ma rozkład beta z parametrami (, ).

ROZKŁAD GAMMA

Zmienna losowa X ma rozkład gamma z parametrem , jeżeli gęstość jej rozkładu

prawdopodobieństwa wyraża się wzorem:
1
f(x) = x

-1

e

-x

dla x > 0

()

0 dla x  0

gdzie  > 0 oraz () jest funkcją gamma

() =

0





x

-1

e

-x

dx

Zmienna losowa o rozkładzie gamma

z całkowitym parametrem λ

Aby otrzymać zmienną losową o rozkładzie gamma z całkowitym parametrem ,

wystarczy wygenerować  niezależnych zmiennych losowych R

1

, R

2

, ..., R



o rozkładzie równomiernym na przedziale (0, 1) i wykonać obliczenia według
wzoru:



X = ln  Ri 

i=1

Zmienna losowa o rozkładzie gamma

z całkowitym parametrem λ

Zmienną losową X o rozkładzie gamma przedstawimy w postaci:

X = X

1

+ X

2

X

3

Gdzie X

1

ma rozkład gamma z parametrem n = [], X

2

ma rozkład gamma

z parametrem równym jedności, X3 ma rozkład beta z parametrami (, 1-),

gdzie  = -[] jest liczbą z przedziału (0, 1).

ROZKŁADY RAYLEIGHA

I RICE`A

Zmienna losowa X ma rozkład Rice`a, jeżeli gęstość jej rozkładu
prawdopodobieństwa wyraża się wzorem:

x x

2

+ 

2

x

f(x) = exp (- ) I

0

( ) dla x > 0



2

2

2



2

0 dla x  0

Funkcja I

0

(x) jest zmodyfikowaną funkcją Bessela pierwszego rodzaju stopnia

zerowego
1

2



1 x

I

0

(x) =  e

x cost

dt =  ( )

2k

2

0 k = 0

(k!)

2

2

W przypadku szczególnym  = 0 otrzymujemy rozkład Rayleigha o gęstości:

y y

2

g(y) = exp( – ) dla y > 0


2

2

2

0 dla y  0

Generowanie zmiennej losowej Y

o rozkładzie Rayleigha.

Generowanie możemy przeprowadzić metodą odwracania dystrybuanty.
Otrzymujemy wtedy dla zmiennej losowej Y

Y =  - 2 lnR

gdzie R ma rozkład równomierny na przedziale (0, 1).

Generowanie zmiennej losowej

o rozkładzie Rice`a

Dla generowania zmiennej losowej o rozkładzie Rice`a można skorzystać z faktu, że
jeżeli zmienna losowa Y ma rozkład Rayleigha o gęstości g(x) oraz zmienna losowa
R ma rozkład równomierny na przedziale (0, 1) i jeżeli zmienne losowe Y i R są
niezależne, to zmienna losowa X określona wzorem:

X =  Y

2

+ 

2

– 2Y cos2R

ma rozkład Rice`a o gęstości f(x).

ROZKŁAD

PODWÓJNIE

WYKŁADNICZY

Zmienna losowa X ma rozkład podwójnie wykładniczy, jeżeli jej dystrybuanta
wyraża się wzorem:

F(x) = exp (-e

-x

), dla - < x < +

Zastosowanie metody odwrócenia

dystrybuanty

Stosując metodę odwracania dystrybuanty otrzymujemy następujący algorytm:

1. Wygenerować zmienną losową R o rozkładzie równomiernym na przedziale

(0, 1).

2. Obliczyć X = - ln(- lnR).

Korzystając z faktu, że –lnR ma rozkład wykładniczy z dystrybuantą 1– e

-x

, możemy

ten algorytm zmodyfikować:

1. Wygenerować zmienną losową W o rozkładzie wykładniczym z wartością

oczekiwaną równą jedności.

2. Obliczyć X = - lnW

ROZKŁAD WEIBULLA

Zmienna losowa X ma rozkład Weibulla z parametrami (, ), jeżeli gęstość jej

rozkładu prawdopodobieństwa wyraża się wzorem:

x

-1

exp(-x



) dla x > 0

f(x) =
0 dla x  0

gdzie  > 0,  > 0 są stałymi. Dystrybuanta tego rozkładu jest następująca:

F(x) = 1 – exp(-x



), x >0

Metoda pierwsza

Metoda pierwsza opiera się na twierdzeniu, że jeżeli zmienna losowa Y ma rozkład

wykładniczy z dystrybuantą G(y) = 1 – e

-y

, to zmienna losowa X = CY

1/,

gdzie

C = 

-1/

, ma rozkład Weibulla z parametrami (, ).

Zastosowanie tej metody prowadzi do algorytmu:
wygenerować zmienną losową Y o rozkładzie wykładniczym i obliczyć:

X = (Y/)

1/

Metoda druga

Metoda ta prowadzi do algorytmu:

1. Wygenerować zmienną losową N według rozkładu dyskretnego określonego

wzorem:

P{N = k} = 1/e



- 1  

k

/k!, k = 1, 2, ...

2. Wygenerować N niezależnych zmiennych losowych Z

1

, Z

2

, ..., Z

N

o rozkładzie

potęgowym z parametrem .

3. Wykonać obliczenia według wzoru:

X = Cmin {Z

1

, Z

2

, ..., Z

N

}

Gdzie Cmin = (/)

1/

,  > 0, ma ucięty rozkład Weibulla

ROZKŁAD FRÉCHETA

Zmienna losowa X ma rozkład Frecheta, jeżeli jej dystrybuanta wyraża się wzorem:

F(x) = exp(-x

-

), x > 0,  > 0

Odwracając dystrybuantę otrzymujemy dla zmiennej losowej X wyrażenie:

X = (-lnR)

-1/

w którym R jest zmienną losową o rozkładzie równomiernym na przedziale (0, 1).
Ponieważ zmienna losowa W = -lnR ma rozkład wykładniczy z dystrybuantą 1 – e

-x

,

otrzymujemy wzór:

X = W

-1/

TESTY STATYSTYCZNE

DLA GENERATORÓW

LICZB LOSOWYCH

TESTY ZWIĄZANE Z

MOMENTAMI

Standardowe postępowanie przy weryfikowaniu hipotezy H: (EX

N

= ½) w stosunku

do hipotezy alternatywnej K: (EX

N

 ½) jest następujące.

Dla ustalonego poziomu istotności  znajdujemy takie liczby x



oraz x



, żeby

P{X

N

 x



} = P{X

N

 > x



} = /2

Przy czym prawdopodobieństwa te obliczono przy założeniu, że hipoteza H jest

prawdziwa. Obliczenie liczby x



wymaga rozwiązania równania, którego jedną

stroną jest F

N

(x), drugą zaś liczba /2; analogicznie zaś obliczenie liczby x



wymaga rozwiązania takiego równania z liczbą 1- po prawej stronie.

Jeżeli takie liczby zostaną obliczone, to weryfikacja hipotezy sprowadza się do
porównania zaobserwowanej wartości zmiennej losowej X

N

z tymi liczbami;

zdarzenie X

N

< x



oraz zdarzenie X

N

> x



prowadzą do odrzucenia weryfikowanej

hipotezy.

TEST CHI-KWADRAT

ZGODNOŚCI ROZKŁADY (TEST

CZĘSTOŚCI)

Niech zmienna losowa  ma rozkład o dystrybuancie F takiej, że F(a) = 0 oraz

F(b) = 1. Niech a

0

= a < a

1

< a

2

< ... a

k

= b oraz p

i

= P{a

i-1

<   a

i

}, i = 1,2, ...,.

Rozważmy ciąg 

1

, 

2

, ..., 

N

liczb losowych z pewnego generatora liczb losowych

o rozkładzie z dystrybuantą F. Niech n

1

będzie liczbą takich elementów  tego

ciągu, które spełniają warunek: a

i-1

<   a

i

. Statystyka

k

(n

i

– Np

i

)

2

1

k

ni

2



2

k-1

=  = =  - N

i=1

Np

i

N

i=1

pi

ma w przybliżeniu rozkład chi-kwadrat o (k-1) stopniach swobody. Jeżeli N jest
dostatecznie duże, to statystyka ta służy do weryfikacji hipotezy o rozkładzie

zmiennej losowej  za pomocą tzw. testu chi-kwadrat

TEST ZGODNOŚCI ROZKŁADU

PAR

Test par konstruujemy w następujący sposób.
Niech n

i

będzie liczbą takich elementów X w ciągu X

1

, X

2

, ..., X

N

, które spełniają

warunek: a

i-1

< X  a

i

. Obliczamy wartość statystyki 

1

2

według wzoru:

k

N N



2

=  ( n

i

- )

2

/

1

i=1

k k

Konstruujemy ciąg par (X

1

, X

2

), (X

2

, X

3

), ..., (X

N-1

, X

N

). Niech n

ij

będzie liczbą takich

par (X, Y) w tym ciągu, które spełniają warunek: a

i-1

< X  a

i

oraz b

j-1

< Y  b

j

.

Obliczamy wartość statystyki 

2

2

zgodnie ze wzorem:

k k

N -1 N-1



2

=   ( n

ij

- )

2

/

2

i=1 j=1

k

2

k

2

Weryfikowaną hipotezę odrzucamy na poziomie istotności równym ,

gdy 

2

2

-

2

1

> 

2

(k

2

- k, ),

gdzie 

2

(, ) oznacza wartość krytyczną rozkładu chi-kwarat o  stopniach

swobody.

TESTY SERII

Teoria weryfikowania hipotezy o niezależności zmiennych X

1

, X

2

, ..., X

N

oparta na

liczbie R serii jest następująca: należy – dla ustalonego poziomu istotności
 - znaleźć takie dwie liczby krytyczne R

1

oraz R

2

, żeby

P{R < R

1

} = P{R > R

2

} = /2

Jeżeli zaobserwowana liczba serii jest mniejsza od R

1

lub większa od R

2

,

weryfikowaną hipotezę odrzucamy.

TESTY ZGODNOŚCI

ROZKŁADÓW

Jeżeli X

1

, X

2

, ... jest ciągiem liczb niezależnych zmiennych losowych o rozkładzie

równomiernym na przedziale (0, 1), to ciąg (X

1

, X

2

, ..., X

m

), (X

m+1

, X

m+2

, ..., X

2m

),...

jest ciągiem niezależnych zmiennych losowych o jednakowym rozkładzie
równomiernym na m-wymiarowej kostce jednostkowej (0, 1)

m

. Niech

y = h( x

1

, x

2

, ..., x

m

)

będzie funkcją m zmiennych, określoną na kostce jednostkowej (0, 1)

m

.

Przekształcając ciąg (X

1

, X

2

, ..., X

m

), (X

m+1

, X

m+2

, ..., X

2m

),... według tej funkcji

otrzymujemy nowy ciąg Y

j

= h(X

(j-1)m+1

, X

(j-1)m+2

, ..., X

jm

), j = 1, 2,... Jest to ciąg

niezależnych zmiennych losowych o jednakowym rozkładzie.

Niech G będzie dystrybuantą rozkładu tych zmiennych losowych

G(y) = P{Y

j

 y}

Gdy zmienne losowe X

1

, X

2

, ... są niezależne i mają jednakowy rozkład

równomierny na przedziale (0, 1). Testowanie generatora na podstawie funkcji

y = h( x

1

, x

2

, ..., x

m

)

przeprowadza się w następujący sposób: obserwuje się ciąg zmiennych losowych
X

1

, X

2

, ... i przekształca go na ciąg zmiennych losowych Y

1

, Y

2

, .... Dla ciągu

Y

1

, Y

2

,... weryfikuje się hipotezę, że jest on próbką prostą z populacji

o dystrybuancie G. Odrzucenie tej hipotezy prowadzi do dyskwalifikacji generatora
liczb losowych X

1

, X

2

,...

TESTY KOMBINATORYCZNE

Test pokerowy

Niech X

1

, X

2

, ... będzie ciągiem liczb z pewnego generatora liczb losowych

o rozkładzie z dystrybuantą F . Podzielmy zbiór wartości zmiennych losowych X na
k rozłącznych „jednakowo prawdopodobnych” przedziałów za pomocą punktów
a

0

< a

1

< a

2

< ... < a

k-1

. Jeżeli zmienne losowe X

j

mają rzeczywiście rozkład

z dystrybuantą F, to dla każdego przedziału (a

i-1

, a

i

)

P{a

i-1

< X

i

 a

i

} = 1/k

Utwórzmy nowy ciąg zmiennych losowych Y

j

zdefiniowanych wzorem:

Y

j

= i jeżeli X

j

 (a

i

, a

i+1

), i = 0, 1, ..., k-1

Zmienne losowe Y

j

przyjmują więc tylko wartości 0, 1, 2, ..., k-1, każdą

z jednakowym prawdopodobieństwem.

Podzielmy ciąg Y

1

, Y

2

, ... na piątki (Y

1

, Y

2

, ..., Y

5

), (Y

6

, Y

7

, ..., Y

10

),.... Ten nowy ciąg

zbudowany jest z k

5

różnych piątek. Będziemy wyróżniali następujące typy piątek:

abcde (bust – każda liczba w piątce jest inna);
aabcd (para – w piątce są dwie liczby jednakowe, wszystkie pozostałe są

różne);

aabbc (dwie pary);
aaabc (trójka);
aaabb (full);
aaaab (czwórka);
aaaaa (piątka).

Zgodność rozkładu piątek różnych typów sprawdza się za pomocą zwykłego testu
chi-kwadrat.

Test kolekcjonera

Utwórzmy ciąg Y

1

, Y

2

, ... tak jak w teście pokerowym. Będziemy obserwowali ten

ciąg dopóki nie pojawią się w nim wszystkie k cyfry 0, 1, 2, ..., k-1. Niech r będzie
długością zaobserwowanego odcinka ciągu. Można udowodnić, że zmienna losowa
r ma rozkład prawdopodobieństwa określony wzorem:

1

k-2

p

r

=  (-1)

j

(

k-1

)(k – 1 – j )

r-1

, r = k, k + 1, ...

k

r-1 j=0 j

Zgodność

tego

rozkładu

prawdopodobieństwa

z

rozkładem

zaobserwowanym bada się za pomocą standardowego testu chi-kwadrat

.

Test permutacji

Niech X

1

, X

2

, ... będzie ciągiem niezależnych zmiennych losowych o jednakowym

rozkładzie równomiernym na przedziale (0, 1) i rozpatrzymy ciąg (X

1

, X

2

, ..., X

m

),

(X

m+1

, X

m+2

, ..., X

2m

),.... Przekształćmy każdy z punktów

(X

(j-1)m+1

, X

(j-1)m+2

, ...X

jm

), j= 1, 2, ..., przypisując każdej współrzędnej X

r

numer n

r

,

jaki ona zajmuje w ciągu liczb X

(j-1)m+1

, X

(j-1)m+2

, ...X

jm

po jego uporządkowaniu

w ciąg rosnący.
Jeżeli ciąg X

1

, X

2

, ... jest ciągiem niezależnych zmiennych losowych, to każda

permutacja (n

1

, n

2

, ..., n

m

) liczb (1, 2, ...,

m

) jest jednakowo prawdopodobna.

Testem zgodności chi-kwadrat weryfikuje się hipotezę, że tak jest rzeczywiście.

KONIEC