E-book details

Metody Monte Carlo

Metody Monte Carlo

Maciej Romaniuk

Ebook

Podręcznik jest przeznaczony dla słuchaczy kierunków matematycznych i informatycznych Politechniki Warszawskiej. Jego celem jest zapoznanie czytelników z tematyką statystycznych symulacji komputerowych, ze szczególnym uwzględnieniem metod Monte Carlo i Markov chain Monte Carlo.

W kolejnych rozdziałach: omówiono podstawowe pojęcia związane z generowaniem liczb (pseudo)losowych i przedstawiono wybrane generatory programowe wraz ze sposobami testowania uzyskanych wyników pod kątem ich jakości (czyli zbliżenia do "losowości"); zaprezentowano kolejne "piętro" w generowaniu liczb (pseudo)losowych, czyli metody i algorytmy służące do przekształcania uzyskanych wcześniej wartości (najczęściej z rozkładu jednostajnego) do zmiennych z różnych praktycznych rozkładów prawdopodobieństwa; zaprezentowanono problem zmiennych wielowymiarowych, dla których stosowanie metod znanych z rozkładów jednowymiarowych okazuje się często wysoce nieefektywne (dokładniej omówiono algorytmy dla wielowymiarowego rozkładu normalnego prawdopodobieństwa); przybliżono zagadnienie generowania trajektorii dla wybranych klas procesów stochastycznych; przedstawiono także rodzinę metod symulacyjnych, znanych jako metody Monte Carlo (m.in. omówiono dwa typy zagadnień, które można rozwiązać przy użyciu takich metod, czyli kwestię całkowania oraz problem szukania ekstremum globalnego); omówiono teorię łańcuchów Markowa (dla przypadku dyskretnej oraz nieprzeliczalnej przestrzeni stanów), która stanowi podbudowę niezbędną do zrozumienia zasady działania metod Markov chain Monte Carlo (MCMC); zaprezentowano dwa najważniejsze algorytmy dla owych metod wraz z praktycznymi przykładami ich zastosowania; przedstawiono trochę inne podejście do symulacji statystycznych niż generowanie próby niezależnych zmiennych losowych, czyli metody resamplingu, na czele z boostrapem.

Przedstawiony w książce materiał wzbogacono zadaniami i problemami przeznaczonymi do samodzielnego rozwiązania.

Przedmowa 9

1. Generatory fizyczne i programowe 11

1.1. Algorytm kwadratowy von Neumanna 11

1.2. Generatory fizyczne 12

1.3. Własności generatorów programowych 13

1.3.1. Testowanie generatorów programowych 16

1.3.2. Definicja „losowości” 19

1.4. Wybrane typy generatorów programowych 20

1.4.1. Generator Lehmera 20

1.4.2. Generatory Fibonacciego 22

1.4.3. Generatory nieliniowe 23

1.4.4. Algorytm Mersenne Twister 24

1.5. Łączenie generatorów 26

1.6. Zadania 27

2. Generatory dla różnych rozkładów prawdopodobieństwa 29

2.1. Metoda odwracania dystrybuanty 30

2.2. Metoda eliminacji 33

2.2.1. Metoda szybkiej eliminacji i szeregów 38

2.2.2. Algorytm ARS 42

2.3. Metoda ilorazu równomiernego 44

2.4. Metoda superpozycji rozkładów 47

2.4.1. Ogólny przypadek metody kompozycji 47

2.4.2. Gęstości wielomianowe 49

2.5. Metody generowania z rozkładów dyskretnych 50

2.5.1. Warianty uogólnionej metody odwracania dystrybuanty 51

2.5.2. Metoda ALIAS 52

2.6. Metody szczegółowe 56

2.6.1. Generowanie rozkładu normalnego 56

2.6.2. Inne rozkłady prawdopodobieństwa 60

2.7. Zadania 60

3. Wielowymiarowe zmienne losowe 65

3.1. Rozkład jednostajny na kuli 66

3.1.1. Przekleństwo wymiaru 66

3.1.2. Zmienne biegunowe 68

3.1.3. Redukcja wymiaru 69

3.1.4. Wykorzystanie rozkładu normalnego 71

3.2. Wielowymiarowy rozkład normalny 71

3.3. Inne podejścia 73

3.4. Zadania 75

4. Generowanie procesów stochastycznych 77

4.1. Jednorodny proces Poissona 77

4.2. Niejednorodny proces Poissona 79

4.3. Proces Wienera 81

4.4. Zadania 83

5. Metody Monte Carlo 85

5.1. Przykłady prostych zastosowań 86

5.2. Zagadnienie całkowania metodą MC 88

5.2.1. Wprowadzenie 89

5.2.2. Geometryczne Monte Carlo 90

5.2.3. Proste Monte Carlo 92

5.2.4. Aproksymacja riemannowska 94

5.3. Metody redukcji wariancji 96

5.3.1. Próbkowanie ważone 98

5.3.2. Zmienne antytetyczne 101

5.3.3. Zmienne kontrolne 102

5.3.4. Wykorzystanie nierówności Rao-Blackwella 104

5.4. Zagadnienie optymalizacji metodą MC 105

5.4.1. Podejście naiwne 105

5.4.2. Symulowane wyżarzanie 106

5.4.3. Metoda EM 109

5.4.4. Inne podejścia optymalizacyjne 113

5.5. Zastosowanie metod MC w testach statystycznych 115

5.6. Zastosowanie metod MC w wycenie instrumentów finansowych 119

5.6.1. Wycena opcji europejskiej call 119

5.6.2. Wycena obligacji katastroficznych 123

5.7. Zadania 125

6. Wprowadzenie do łańcuchów Markowa 129

6.1. Dyskretna przestrzeń stanów 129

6.2. Nieprzeliczalna przestrzeń stanów 134

6.3. Twierdzenia ergodyczne 139

6.4. Zadania 140

7. Metody Markov chain Monte Carlo 141

7.1. Algorytm Metropolisa-Hastingsa 142

7.1.1. Zbieżność wygenerowanego ŁM 143

7.1.2. Wybór gęstości proponującej 145

7.1.3. Estymator rao-blackwellizowany 150

7.1.4. Algorytm ARMS 152

7.1.5. Algorytmy typu DE-MC 153

7.2. Dwuwymiarowy próbnik Gibbsa 157

7.2.1. Zbieżność algorytmu 158

7.2.2. Własność przeplotu 160

7.2.3. Parametryczna Rao-Blackwellizacja 161

7.2.4. Algorytm EM a próbnik Gibbsa 162

7.3. Wielowymiarowy próbnik Gibbsa 164

7.4. Algorytm MH a próbnik Gibbsa 167

7.5. Przykładowe zastosowania metody MCMC 170

7.5.1. Modele hierarchiczne 170

7.5.2. Model Isinga 172

7.5.3. Odszumianie obrazów 173

7.6. Zalety i wady metod MCMC 177

7.7. Diagnostyka zbieżności 178

7.7.1. Zbieżność do rozkładu stacjonarnego 179

7.7.2. Zbieżność średniej 181

7.7.3. Inne kryteria i metody diagnozy zbieżności 184

7.8. Zadania 185

8. Resampling 187

8.1. Bootstrap 187

8.2. Jackknife 191

8.3. Uogólnione podejście 193

8.4. Zastosowanie resamplingu w testach statystycznych 193

8.4.1. Przykładowe metody resamplingu 194

8.4.2. Test równości dwóch średnich 196

8.4.3. Podwójny bootstrap 199

8.5. Zadania 201

A. Rozwiązania wybranych zadań 203

Spis algorytmów 213

Spis rysunków 215

Skorowidz 217

Bibliografia 227