Jak wylosować zmienną losową o rozkładzie
mając dane
? Metoda odwracanie dystrybuanty
w przypadku rozkładów dyskretnych (Przykład 3.6)
przyjmuje następującą postać. Obliczamy
, gdzie
. Losujemy
i szukamy przedziału
w którym leży
.
W zasadzie można to zrobić tak:
Gen ![]() ![]() |
while ![]() ![]() |
return ![]() |
Problemem jest mała efektywność tego algorytmu. Jedno z możliwych ulepszeń polega na bardziej ,,inteligentnym” lokalizowaniu przedziału
, na przykład metodą bisekcji.
Załóżmy, że mamy rozkład prawdopodobieństwa na przestrzeni
skończonej i liczby
są uporządkowane:
.
Gen ![]() |
![]() ![]() |
repeat |
![]() |
if ![]() ![]() ![]() |
until ![]() |
return ![]() |
Przedstawię teraz piękną metodę opartą na innym pomyśle.
Przypuśćmy, że mamy dwa ciągi liczb:
, gdzie
oraz
, gdzie
(to są owe ,,aliasy”). Rozaptrzmy taki algorytm:
Gen ![]() |
Gen ![]() |
if ![]() ![]() ![]() |
return ![]() |
Jest jasne, że
![]() |
Jeśli mamy zadany rozkład prawdopodobieństwa i chcemy, żeby
, to musimy dobrać odpowiednio
i
. Można zawsze
tak zrobić, i to na wiele różnych sposobów. Opracowanie algorytmu dobierania wektorów
i
do zadanego
pozostawiamy jako ćwiczenie.
Spośród obiektów chcemy wybrać losowo
tak, aby każdy z
podzbiorów miał jednakowe prawdopodobieństwo.
Oczywiście, można losować tak, jak ze zwracaniem, tylko odrzucać elementy wylosowane powtórnie.
W tablicy
zaznaczamy, które elementy zostały wybrane.
for ![]() ![]() ![]() |
![]() |
repeat |
repeat |
Gen ![]() |
until ![]() |
![]() |
![]() |
until ![]() |
Pewnym ulepszeniem tej prymitywnej metody jest następujący algorytm.
Tablica ma takie samo znaczenie jak w poprzednim przykładzie. Będziemy teraz
,,przeglądać” elementy
po kolei, decydując o zaliczeniu do
próbki kolejnego elementu zgodnie z odpowiednim prawdopodobieństwem warunkowym.
Niech
oznacza liczbę wybranych, zaś
- liczbę przejrzanych poprzednio elementów.
for ![]() ![]() ![]() |
![]() ![]() |
repeat |
Gen ![]() |
if ![]() |
begin |
![]() |
![]() |
end; |
![]() |
until ![]() |
Tablica
będzie teraz zawierała numery wybieranych elementów. Podobnie jak
poprzednio,
– oznacza liczbę elementów wybranych,
– liczbę przejrzanych.
for ![]() ![]() ![]() |
for ![]() ![]() |
begin |
Gen ![]() |
if ![]() |
begin |
Gen ![]() |
![]() |
end |
end |
Uzasadnienie poprawności tego algorytmu jest
rekurencyjne. Załóżmy, że przed -tym losowaniem każda próbka
wybrana ze zbioru
ma prawdopodobieństwo
![]() |
W kroku ta próbka ,,przeżywa” czyli pozostaje bez zmiany z prawdopodobieństwem
(jest to prawdopodobieństwo, że próbka wylosowana ze zbioru
nie zawiera elementu
. Zatem po kroku
każda próbka nie zawierająca elementu
ma prawdopodobieństwo
![]() |
Z prawdopodobieństwem ,,podmieniamy” jeden z elementów próbki (losowo wybrany) na element
. Sprawdzenie, że każda probka zawierająca element
ma po
-tym losowaniu jednakowe prawdopodobieństwo – pozostawiam jako ćwiczenie.
Przez permutację losową rozumiemy uporządkowanie elementów wygenerowane zgodnie z rozkładem jednostajnym na
przestrzeni wszystkich
możliwych uporządkowań.
Permutację liczb
zapiszemy w tablicy
.
Łatwo sprawdzić poprawność następującego algorytmu.
for ![]() ![]() ![]() |
for ![]() ![]() |
begin |
Gen ![]() |
![]() |
end |
Szczególnie często stosowany jest specjalny przypadek metody eliminacji, znany jako algorytm ,,ilorazu zmiennych równomiernych” (Ratio of Uniforms). Zaczniemy od prostego przykładu, który wyjaśni tę nazwę.
Metodą eliminacji z prostokąta otrzymujemy zmienną losową
o
rozkładzie jednostajnym na półkolu
. Kąt
pomiędzy
osią poziomą i punktem
ma, oczywiście, rozkład
.
repeat |
Gen ![]() |
Gen ![]() |
until ![]() |
![]() |
Na wyjściu , bo
![]() |
Ogólny algorytm metody ,,ilorazu równomiernych” oparty jest na następującym fakcie.
Załóżmy o funkcji , że
![]() |
Niech zbiór będzie określony następująco:
![]() |
Miara Lebesgue'a (pole) tego zbioru jest skończone, , a zatem można mówić o
rozkładzie jednostajnym
.
Jeżeli i
, to
ma gęstość proporcjonalną do
funkcji
(
).
,,Pole figury” jest równe
![]() |
Dokonaliśmy tu zamiany zmiennych:
![]() |
Jakobian tego przekształcenia jest równy
![]() |
W podobny sposób,
na mocy znanego wzoru na gęstość przekształconych zmiennych losowych obliczamy
łączną gęstość :
![]() |
Stąd dostajemy gęstość brzegową :
![]() |
Żeby wylosować stosuje się zazwyczaj eliminację z prostokąta.
Użyteczne jest następujące oszacowanie boków tego prostokąta.
Jeśli funkcje i
są ograniczone, wtedy
![]() |
gdzie
![]() |
![]() |
Jeśli to oczywiście
.
Załóżmy dodatkowo, że
i przejdżmy do zmiennych
, gdzie
.
Nierówność
jest równoważna
. Ponieważ
, więc
dostajemy
. Dla
mamy analogicznie
.
Ogólny algorytm RU jest następujący:
repeat |
Gen ![]() |
![]() ![]() |
until ![]() |
![]() |
Niech
![]() |
Wtedy
![]() |
Zauważmy, że i
. Otrzymujemy następujący algorytm:
repeat |
Gen ![]() |
![]() ![]() |
![]() |
until ![]() |
Ciekawe, że można skonstruować dokładne algorytmy eliminacji bez konieczności dokładnego obliczania docelowej gęstości .
Podstawowy pomysł jest następujący. Niech
, podobnie jak poprzednio, będzie funkcją proporcjonalną do
gęstości (nie jest potrzebna stała normująca) i
. Załóżmy, że mamy dwa ciągi funkcji, przybliżające
z dołu i z góry:
![]() |
Jeśli umiemy ewaluować funkcje i
to możemy uruchomić następujący algorytm:
repeat |
Gen ![]() |
Gen ![]() |
![]() |
repeat |
![]() |
if ![]() |
begin ![]() ![]() |
until ![]() |
until FALSE |
Poniższy algorytm jest znany jako metoda szeregów zbieżnych. Zakładamy, że
![]() |
przy czym reszty tego szeregu umiemy oszacować z góry przez znane funkcje,
![]() |
Pseudo-kod algorytmu jest taki:
repeat |
Gen ![]() |
Gen ![]() |
![]() |
![]() |
![]() |
repeat |
![]() |
![]() |
until ![]() |
until ![]() |
return ![]() |
Metoda szeregów naprzemiennych jest dostosowana do sytuacji gdy
![]() |
gdzie
.
Wiadomo, że w takiej sytuacji sumy częściowe przybliżają sumę szeregu na przemian z nadmiarem i z niedomiarem.
Ten fakt wykorzystuje algorytm szeregów naprzemiennych:
repeat |
Gen ![]() |
Gen ![]() |
![]() |
![]() |
![]() |
repeat |
![]() ![]() |
![]() |
if ![]() ![]() ![]() |
![]() ![]() |
![]() |
until ![]() |
until FALSE |
Rozkład Kołmogorowa-Smirnowa ma dystrybuantę
![]() |
i gęstość
![]() |
Możemy zastosować metodę szeregów naprzemiennych, kładąc
![]() |
oraz
![]() |
Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
Projekt współfinansowany przez Unię Europejską w ramach
Europejskiego Funduszu Społecznego.
Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.