1 Metody Symulacyjne w Telekomunikacji (MEST) Wykład 4: Generowanie zdarzeń Dr inż. Halina Tarasiuk p. 337, tnt.tele.pw.edu.pl
2 Zagadnienia Wstęp Planowanie zdarzeńGenerowanie zdarzeń a zmienne losowe Generatory liczb losowych Generowanie wartości zmiennych losowych dla wybranych rozkładów
3 Zagadnienia Wstęp Planowanie zdarzeńGenerowanie zdarzeń a zmienne losowe Generatory liczb losowych Generowanie wartości zmiennych losowych dla wybranych rozkładów
4 Wstęp (1) Symulacja, która ma jakiekolwiek losowe elementy musi angażować pewne próbki lub generować liczby losowe z rozkładów prawdopodobieństwa Rozkłady są często wynikiem dopasowania pewnych rozkładów, np. rozkładu wykładniczego, gamma, Poissona, do danych pochodzących z obserwacji rzeczywistego systemu
5 Wstęp (2) Źródła losowości dla przykładowych systemów PrzemysłCzas życia maszyn, czas naprawy maszyn Komunikacja Odstęp między wiadomościami, typ wiadomości, długość wiadomości Transport Czas załadunku statku, odstęp między klientami przybywającymi do odprawy
6 Zagadnienia Wstęp Planowanie zdarzeńGenerowanie zdarzeń a zmienne losowe Generatory liczb losowych Generowanie wartości zmiennych losowych dla wybranych rozkładów
7 Planowanie zdarzeń – przykład (1)Symulacja prostego systemu kolejkowego z jednym serwerem obsługi i jedną kolejką Napływ klientów Kolejka Serwer obsługi Wypływ klientów Rys. 1: Prosta reprezentacja modelu systemu
8 Planowanie zdarzeń - przykład(2)Graf zdarzeń, model kolejkowy Przybycie do systemu Opuszczenie systemu inicjalizacja Możliwe przejście
9 Zagadnienia Wstęp Planowanie zdarzeńGenerowanie zdarzeń a zmienne losowe Generatory liczb losowych Generowanie wartości zmiennych losowych dla wybranych rozkładów
10 Generowanie zdarzeń a zmienne losoweSymulacja systemów o parametrach wejściowych opisanych pewnymi zmiennymi losowymi wymaga określenia rozkładów prawdopodobieństwa tych zmiennych Przykłady Zmienne losowe opisujące: Odstępy między klientami napływającymi do systemu kolejkowego Czas obsługi klientów w systemie kolejkowym
11 Zmienne losowe a generowanie zdarzeńZałożenie parametry wejściowe modelu symulacyjnego zmienne losowe opisane danym rozkładem Przebieg symulacji wartości zmiennych losowych generowane zgodnie z przyjętym rozkładem
12 Zmienne losowe i ich własnościOznaczenia zmiennych losowych X, Y, Z Założenia Eksperyment – pewien proces, którego wynik nie jest znany Zbiór wszystkich możliwych wyników jest określany zbiorem próbek, S Zmienna losowa jest pewną funkcją, która przypisuje wartość ze zbioru liczb rzeczywistych każdemu z wyników eksperymentu ze zbioru S Wartości, które może przyjmować zmienna losowa x, y, z
13 Zmienne losowe i ich własnościDystrybuanta zmiennej losowej X jest zdefiniowana dla każdego x, jako Gdzie P(X≤x) oznacza prawdopodobieństwo skojarzone ze zdarzeniem, że {X≤x} Własności dystrybuanty 0 ≤F(x) ≤1 dla wszystkich x F(x) nie jest malejąca
14 Zmienna losowa dyskretna
15 Zmienna losowa ciągła (1)Zmienna losowa X jest zmienną losową ciągłą, jeżeli istnieje nieujemna funkcja f(x) taka, że dla dowolnego zbioru liczb rzeczywistych
16 Zmienna losowa ciągła (2)f(x) – funkcja gęstości f(x)=F’(x) Ponadto jeżeli I=[a,b] dla każdej liczby rzeczywistej a i b, takiej że a < b,
17 Rozkład równomierny Funkcja gęstości dla rozkładu równomiernego na odcinku [0,1] 1 x f(x)
18 Rozkład wykładniczy Funkcja gęstości Dystrybuanta
19 Zagadnienia Wstęp Planowanie zdarzeńGenerowanie zdarzeń a zmienne losowe Generatory liczb losowych Generowanie wartości zmiennych losowych dla wybranych rozkładów
20 Generatory liczb losowychGenerowanie liczb losowych Umożliwia otrzymywanie wartości zmiennych losowych z przyjętego rozkładu Załóżmy, że rozkład jest znany Chcemy wygenerować liczby losowe zgodnie z danym rozkładem, aby przeprowadzić symulację dla przyjętego modelu symulacyjnego
21 Ciągi losowe Wyróżniamy trzy typy ciągów losowych Prawdziwie losoweGenerowane przez losowy proces fizyczny Pseudolosowe Liczby generowane wg ścisłej procedury matematycznej, czyli reprodukowalne Quasilosowe Ciągi, które nie muszą spełniać kryteriów losowości, ale jedynie dawać poprawne rozwiązania problemów Ciągi quasilosowe tworzy się na użytek już postawionych zadań
22 Metody generowania liczb losowychDla celów badań symulacyjnych, w których opisujemy zmienne losowe za pomocą rozkładów prawdopodobieństwa stosujemy metody generowania liczb pseudolosowych Jednak w dalszej części liczby pseudolosowe będziemy określać jako liczby losowe W praktyce nie przeprowadzamy badań symulacyjnych z ciągiem liczb prawdziwie losowych Interesują nas wyniki w pewien sposób powtarzalne Np. aby porównać dwa systemy
23 Metodologia generowania liczb losowychPierwszy generator arytmetyczny Generator von Neumanna i Metropolisa (lata 40-te XX wieku) Bazujący na metodzie średniokwadratowej
24 Wymagania na arytmetyczny generator liczb losowychPrzede wszystkim, generowane liczby powinny Pokrywać się z rozkładem równomiernym na odcinku [0,1] Nie powinny wykazywać korelacji, w przeciwnym przypadku wyniki symulacji nie będą prawidłowe Powinniśmy móc otrzymać taki sam ciąg liczb powtórnie Np. w celu powtórzenia eksperymentu symulacyjnego Lub w celu porównania działania dwóch systemów Generator powinien umożliwić łatwe generowanie kilku oddzielnych ciągów liczb losowych (jeden ciąg dedykowany dla jednego źródła losowego)
25 Przykład – metoda średniokwadratowaRozpocznijmy od czterocyfrowej dodatniej liczby całkowitej Z0 Podnieśmy ją do kwadratu, aby uzyskać liczbę całkowitą ośmiocyfrową (jeżeli konieczne uzupełnijmy zerami z lewej strony) Należy wybrać cztery środkowe cyfry, które będą stanowić kolejną czterocyfrową liczbę całkowitą Z1 Aby uzyskać pierwszą liczbę losową z rozkładu równomiernego U1(0,1) tworzymy w oparciu o Z1 liczbę dziesiętną
26 Przykład – metoda średniokwadratowa
27 Przykład – metoda średniokwadratowaOcena metody Metoda ma tendencję dążenia do zera i pozostawania w tym stanie Można to zaobserwować np. w rozważanym przykładzie dla większej liczby kroków lub np. dla Z0=1009
28 Metody generowania liczb losowychMetoda generowania zmiennych losowych z rozkładu równomiernego na odcinku [0,1] 1 x f(x)
29 Generatory kongruencyjne linioweWiele generatorów liczb losowych stosowanych obecnie to generatory kongruencyjne liniowe, LCG (Linear Congruential Generator) Sekwencja liczb całkowitych Z1, Z2, ... jest wyznaczana następująco: Gdzie m, a, c, Z0 - wartość początkowa, są to liczby całkowite nieujemne
30 Generatory kongruencyjne linioweAby otrzymać żądaną liczbę losową stosujemy wzór: gdzie 0
31 Przykład Rozważmy generator LCG o parametrach m=16, a=5, c=3, Z0=7
32 Przykład PodsumowanieW rozważanym przypadku obserwujemy cykliczne powtarzanie się otrzymywanych wyników Długość cyklu jest określana jako okres W rozważanym przykładzie okres wynosi 16
33 Generator LCG Generator LCG jest generatorem pełno-okresowymJeżeli generator jest pełno-okresowy dowolny wybór wartości Z0 z przedziału {0, 1, ..., m-1} będzie generował pełny ciąg
34 Generator LCG Twierdzenie Generator LCG opisany wzoremma pełny okres wtedy i tylko wtedy, jeżeli spełnione są następujące warunki Jedyną dodatnią liczbą całkowitą, która dzieli bez reszty m i c jest 1 Niech q będzie liczbą pierwszą, jeżeli m jest podzielne przez q, wówczas a-1 jest również podzielne przez q Jeśli m jest podzielne przez 4 wówczas a-1 jest również podzielne przez 4
35 Przykład – generator rand()
36 Przykład – generator rand()
37 Zagadnienia Wstęp Planowanie zdarzeńGenerowanie zdarzeń a zmienne losowe Generatory liczb losowych Generowanie wartości zmiennych losowych dla wybranych rozkładów
38 Generowanie wartości zmiennych losowychZałóżmy, iż chcemy wygenerować zmienną losową X, która jest zmienną losową ciągłą Zmienna ta ma dystrybuantę F, która jest ciągła i rosnąca, gdy 0
39 Generowanie wartości zmiennych losowychMetodologia Wówczas algorytm generowania zmiennej losowej X mającej dystrybuantę F jest następujący Generujemy Zwracamy
40 Rozkład wykładniczy Funkcja gęstości Dystrybuanta
41 Przykład Niech X będzie zmienną losową mającą rozkład wykładniczy z wartością średnią Dystrybuanta rozkładu dana jest funkcją Aby znaleźć F-1, przyjmujemy u=F(x) i w ten sposób znajdujemy x
42 Przykład Funkcja odwrotna przyjmuje wartość
43 Przykład – kod C++