Metody Monte Carlo — Jak Losowość Rozwiązuje Realne…

Czym jest metoda Monte Carlo?

Nazwa pochodzi od kasyna w Monako — metoda została nazwana na cześć miasta słynącego z hazardowej losowości, nie samego miasta jako takiego. Metody Monte Carlo to każdy algorytm, który wykorzystuje losowe próbkowanie, by uzyskać wyniki numeryczne. Są szczególnie przydatne, gdy:

Deterministyczny wzór nie istnieje albo jest zbyt złożony, by go obliczyć.
Problem żyje w wielu wymiarach (gdzie metody siatkowe są niepraktyczne).
Przybliżona odpowiedź jest akceptowalna, a stać cię na wiele losowych próbek.

Dokładność oszacowania Monte Carlo poprawia się jak $\frac{1}{\sqrt{N}}$ — podwojenie dokładności wymaga czterokrotnie więcej próbek. Brzmi to wolno, ale w przestrzeniach wysokowymiarowych bije każdą konkurencyjną metodę.

Szacowanie π przez rzucanie lotkami

Najsłynniejsza demonstracja Monte Carlo dotyczy okręgu jednostkowego wpisanego w kwadrat 2×2. Jeśli rzucasz lotkami równomiernie w kwadrat, ułamek trafień wewnątrz okręgu równa się $\pi/4$ — ponieważ pole okręgu wynosi $\pi r^2 = \pi$, a pole kwadratu $4$.

1
Próbkuj: Wybierz losowy punkt $(x, y)$ z $x, y \in [-1, 1]$.
2
Testuj: Oblicz $d = x^2 + y^2$. Punkt jest wewnątrz okręgu, jeśli $d \le 1$.
3
Licz: Śledź trafienia $h$ i łączną liczbę rzutów $N$.
4
Szacuj: $\pi \approx 4 \cdot h / N$. Powtarzaj w nieskończoność — oszacowanie zbiega.

Zbieżność π: Jak liczba próbek wpływa na dokładność

N = 100

≈ 3.16

N = 1 tys.

≈ 3.14

N = 10 tys.

≈ 3.141

N = 1 mln

≈ 3.1416

Zwróć uwagę, że długości pasków nie osiągają 100% — oszacowanie zbiega, ale nigdy nie osiąga dokładnej wartości. Błąd $\sigma \propto 1/\sqrt{N}$ oznacza, że 100× więcej próbek daje tylko jedno dodatkowe miejsce po przecinku.

          function estimatePi(N)
          { let hits = 0;
          for (let i = 0; i <
          N; i++) { const x = Math.random() * 2 - 1;
          // [-1, 1] const y =
          Math.random() * 2 - 1; if (x*x + y*y <= 1)
          hits++; // wewnątrz okręgu jednostkowego?
          }
          return 4 * hits / N;
          // π ≈ 4 · (pole_okręgu / pole_kwadratu)
          }
        

Całkowanie Monte Carlo

Idea rzucania lotkami uogólnia się. Aby scałkować dowolną funkcję $f(x)$ na przedziale $[a, b]$:

Wylosuj $N$ próbek $x_i$ równomiernie z $[a, b]$.
Oblicz średnią: $\bar{f} = \frac{1}{N} \sum f(x_i)$.
Oszacuj: $\int_a^b f(x)\, dx \approx (b - a) \cdot \bar{f}$.

Działa to, ponieważ średnia z $f$ pomnożona przez szerokość przedziału równa się całce. Co ważniejsze, dla całki $d$-wymiarowej błąd wciąż wynosi $O(1/\sqrt{N})$ niezależnie od $d$ — podczas gdy kwadratura siatkowa kosztuje $O(N^{1/d})$ na wymiar. W 20 wymiarach Monte Carlo wygrywa z ogromnym marginesem.

Gdzie na tej stronie używamy Monte Carlo

Symulacja Monte Carlo π

Symulacja Monte Carlo π uruchamia algorytm rzucania lotkami na żywo, wykreślając zbieżność oszacowania w czasie rzeczywistym. Możesz obserwować, jak pasek odchylenia standardowego kurczy się w miarę wzrostu $N$.

Rozprzestrzenianie się choroby (stochastyczny SIR)

Symulacja Rozprzestrzenianie się choroby używa losowych zdarzeń kontaktowych zamiast równań różniczkowych. W każdym kroku czasowym każdy zainfekowany agent kontaktuje się z $k$ losowymi innymi — makroskopowe krzywe S/I/R wyłaniają się z tysięcy indywidualnych losowań Monte Carlo.

Wyszukiwanie nonce w kopaniu Bitcoina

Symulacja Kopanie Bitcoina to w istocie przeszukiwanie hashy metodą Monte Carlo: próbuj losowych nonce, aż jeden spełni cel trudności. Pokazuje, dlaczego kopanie jest probabilistyczne.

Agregacja ograniczona dyfuzją

Dyfuzja i wzrost kryształów wykorzystują błądzenia losowe (proces Monte Carlo) do wyznaczania trajektorii cząstek, które wspólnie tworzą fraktalne, rozgałęzione struktury krystaliczne.

Redukcja wariancji: więcej za mniej

Podstawowa metoda Monte Carlo rzuca lotkami równomiernie. Ale sprytniejsze strategie mogą osiągnąć tę samą dokładność przy mniejszej liczbie próbek:

Próbkowanie warstwowe: podziel dziedzinę na równe podregiony i próbkuj z każdego — zmniejsza klastrowanie.
Próbkowanie istotnościowe: rzucaj więcej lotek tam, gdzie funkcja jest największa, a następnie skoryguj wagi. Kluczowe w śledzeniu ścieżek (renderowanie 3D).
Zmienne kontrolne: użyj analitycznie znanej powiązanej funkcji, by zmniejszyć wariancję wokół oszacowania.
Quasi-Monte Carlo: zastąp liczby pseudolosowe sekwencjami o niskiej rozbieżności (Halton, Sobol) dla lepszego pokrycia i błędu $O((\log N)^d / N)$.

Metody Monte Carlo napędzają globalne oświetlenie w każdym współczesnym filmie i grze 3D. Śledzenie ścieżek (path tracing) — podstawowy algorytm stojący za Pixarem i NVIDIA RTX — to całkowanie Monte Carlo równania renderowania po kierunkach półkuli. Każde „odbicie” to losowa próbka.

Kiedy nie używać Monte Carlo

Monte Carlo to przesada dla niskowymiarowych, gładkich całek, gdzie kwadratura Gaussa lub reguła Simpsona zbiega szybciej. To też słaby wybór, gdy potrzebujesz deterministycznego, powtarzalnego wyniku za każdym razem. I nie potrafi powiedzieć ci dlaczego odpowiedź zbiega do tego, do czego zbiega — jeśli chodzi o wgląd, metody analityczne zawsze wygrywają.

Jako zasada kciuka: jeśli wymiary $d > 4$, a dokładność do 2-3 cyfr znaczących wystarcza, Monte Carlo jest właściwym narzędziem.