Metoda Monte Carlo wykorzystuje losowość do rozwiązywania problemów, które trudno policzyć wprost
Metoda Monte Carlo brzmi jak przeciwieństwo precyzyjnej matematyki: zamiast usuwać przypadek, celowo generuje losowe próby. Stanisław Ulam i John von Neumann należeli do ludzi, którzy pod koniec lat 40. XX wieku rozwinęli komputerowe użycie takiego podejścia podczas prac nad problemami fizyki jądrowej. Jeśli potrafimy skonstruować losowy eksperyment odpowiadający badanemu problemowi, wielokrotne próby mogą dać dobre przybliżenie szukanej wielkości. Im więcej niezależnych próbek, tym zwykle mniejszy błąd statystyczny. Nazwa odwołuje się do Monte Carlo i kasyn — ale zamiast hazardu chodzi o kontrolowane wykorzystanie prawdopodobieństwa.
Jak przypadek może prowadzić do wyniku
Prosty przykład można zbudować z kwadratu i wpisanego w niego ćwiartki koła. Jeśli losujemy wiele punktów równomiernie w kwadracie i sprawdzamy, jaka część wpada do koła, proporcja tych punktów zbliża się do stosunku pól. Z niego można przybliżyć liczbę pi. Taki sposób jest fatalny, jeśli zależy nam tylko na szybkim obliczeniu pi, ale świetnie pokazuje zasadę: trudną wielkość zamieniamy na prawdopodobieństwo zdarzenia, a następnie szacujemy je przez dużą liczbę losowych prób.
Dlaczego Ulam zainteresował się takim podejściem
W Los Alamos Ulam i inni badacze mierzyli się z procesami, w których ogromna liczba możliwych dróg cząstek czyniła dokładne rachunki bardzo trudnymi. Losowe symulowanie pojedynczych historii — na przykład zderzeń, rozproszeń i pochłaniania — pozwalało uzyskać statystyczny obraz całego procesu. Encyclopedia of Mathematics wskazuje prace von Neumanna i Ulama związane z obliczeniami reaktorowymi jako źródło nowoczesnej metody Monte Carlo około 1949 roku. Rozwój komputerów sprawił, że można było wykonywać tysiące i miliony takich prób.
Losowość jest tu kontrolowana
Monte Carlo nie oznacza „zgadnij wiele razy i wybierz odpowiedź”. Trzeba określić właściwy rozkład losowania, związek między próbką a badaną wielkością oraz sposób estymacji błędu. Wynik jest statystyczny: nawet przy poprawnym algorytmie dwie serie losowań mogą dać nieco inne liczby. Teoria prawdopodobieństwa pozwala jednak ocenić, jak duża powinna być ta zmienność. Często błąd maleje mniej więcej jak odwrotność pierwiastka z liczby niezależnych prób, więc zwiększenie dokładności bywa kosztowne obliczeniowo.
Gdzie metoda sprawdza się najlepiej
Największa zaleta pojawia się w problemach wielowymiarowych i skomplikowanych geometrycznie. Klasyczne metody numeryczne mogą wymagać siatki obejmującej ogromną liczbę kombinacji, podczas gdy losowanie pozwala badać tylko wybrane ścieżki. Monte Carlo stosuje się w fizyce transportu promieniowania, finansach, statystyce, grafice komputerowej, optymalizacji i wielu gałęziach nauki. W renderowaniu obrazu losowane ścieżki światła pomagają symulować realistyczne oświetlenie; w fizyce — propagację cząstek.
Dlaczego nazwa jest trafna i myląca jednocześnie
Kasyno kojarzy się z przypadkiem, ale jego właściciel opiera działalność na matematyce prawdopodobieństwa. Podobnie Monte Carlo wykorzystuje pojedyncze losowe zdarzenia, by uzyskać przewidywalne własności całej populacji prób. To jeden z tych pomysłów, w których intuicja „przypadek psuje dokładność” wymaga korekty. Przypadek może być źródłem szumu, ale odpowiednio kontrolowany staje się narzędziem obliczeniowym właśnie dlatego, że prawa statystyki są regularne.
Dlaczego cztery razy więcej prób daje tylko około dwa razy mniejszy błąd
W wielu prostych estymatorach Monte Carlo typowy błąd statystyczny maleje proporcjonalnie do 1/√N, gdzie N jest liczbą niezależnych próbek. To oznacza, że aby zmniejszyć błąd około dziesięciokrotnie, trzeba wykonać mniej więcej sto razy więcej losowań. Metoda bywa więc obliczeniowo kosztowna. Jej przewaga nie polega na cudownie szybkim osiąganiu dowolnej precyzji, ale na tym, że tempo zbieżności często nie pogarsza się dramatycznie wraz ze wzrostem liczby wymiarów problemu — a to w skomplikowanych symulacjach jest ogromną zaletą.