Metody Monte Carlo

Metody Monte Carlo

rok wydania: 2019
ilość stron: 240
ISBN: 978-83-7814-864-7
oprawa: miękka

Opis

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; zaprezentowano 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.

Spis treści

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