Monte Carlo-Metod: Klass av algoritmer som simulerar fysiska och matematiska system

Monte Carlo-metoder kan användas för att lösa vissa problem som är svåra att lösa med konventionella deterministiska metoder, bland annat för att simulera fysikaliska system (till exempel molekyldynamik) eller göra vissa statistiska beräkningar. Idén med att använda slumpen i beräkningarna är att göra beräkningar som i genomsnitt ger det rätta svaret, även om resultatet för varje enskild beräkning är slumpmässig. Monte Carlo-metoder har därför ofta en upprepande natur, och den stora mängden beräkningar gör dem lämpliga att utföras av datorer.

Idén att använda slumptal för att utföra beräkningar utvecklades i Manhattanprojektet under andra världskriget. Syftet var att simulera hur grupper med fysikaliska partiklar rör sig, som ett led i utvecklingen av atombomben. Mer specifikt var syftet att lösa diffusionsekvationen i samband med bestämning av reaktorfysikaliska parametrar, i första hand multiplikationskonstanten i termiska, heterogena kärnreaktorer. Sedan dess har metoderna utvecklats i flera olika riktningar, och hittat tillämpningar inom många olika områden där olika typer av beräkningar behöver utföras.

Namnet Monte Carlo-metod myntades från kasinot i Monte Carlo, där beteendet hos upprepade slumpmässiga experiment också är centralt.

 

En Monte Carlo-metod kan användas för att bilda ett närmevärde för π: enligt formeln för cirkelns area är arean av en kvartscirkel med radien 1 exakt ¼π. Placeras en kvartscirkel i en kvadrat med sidan och arean 1, som i figuren, kommer andelen av kvadraten som ligger i kvartscirkeln att vara samma som dess area. Genom att slumpmässigt generera likformigt fördelade punkter i kvadraten och räkna hur många av dem som hamnar inuti kvartscirkeln kan andelen uppskattas, och därmed arean på kvartscirkeln. Ju fler punkter som genereras desto bättre blir uppskattningen, enligt de stora talens lag. Om uppskattningen multipliceras med 4 får man en uppskattning av π.

Det saknas konsensus om hur Monte Carlo-metoder ska definieras, men det är åtminstone beräkningar som innefattar slumptal på något sätt. Många Monte Carlo-metoder kan formuleras som att de i något steg approximerar integralen

$${\displaystyle I=\int _{\Omega }f(x)\mu (dx)}$$

 

${\displaystyle f}$ 

${\displaystyle \mu }$ 

${\displaystyle \Omega }$ 

$${\displaystyle {\widehat {I}}={\frac {1}{N}}\sum _{i=1}^{N}f(x^{i}),}$$

 

${\displaystyle \{x^{i}\}_{i=1}^{N}}$ 

${\displaystyle N}$ 

${\displaystyle \mu }$ 

${\displaystyle {\widehat {I}}}$ 

${\displaystyle I}$ 

${\displaystyle N\to \infty }$ 

${\displaystyle x}$ 

Den tekniska utmaningen i att konstruera en Monte Carlo-metod för ett problem är ofta att generera slumptalen ${\displaystyle \{x^{i}\}_{i=1}^{N}}$ .

Markovkedje-Monte Carlo

Markovkedje-Monte Carlo (eller på engelska, Markov Chain Monte Carlo, MCMC) är en familj med metoder för att generera slumptal från sannolikhetsfördelningar. MCMC är framför allt användbara när fördelningen endast går att utvärdera punktvis, vilket till exempel kan vara fallet för statistiska modeller. De två grundläggande metoderna är Gibbs sampling (från 1980-talet) och Metropolis-Hastings-samplern (som i princip kom med de första Monte Carlo-metoderna från 1940-talet). Några senare utvecklade metoder är Hamiltonsk Monte Carlo, slice sampling och bouncy particle sampler.

Sekventiell Monte Carlo

Sekventiell Monte Carlo (SMC) är, likt MCMC, en metod för att generera slumptal från sannolikhetsfördelningar. SMC utvecklades inom signalbehandling på 90-talet för att göra filtrering i tillståndsmodeller och har sedan 00-talet generaliserats till att bli ett lika mångsidigt verktyg som MCMC, som har blivit populärt inom bland annat maskininlärning.

Monte Carlo-metoder används för att lösa problem inom många olika vetenskaper, bland annat fysik, maskininlärning, signalbehandling, mekanik, beräkningsbiologi, klimatologi, datorgrafik, tillämpad statistik, artificiell intelligens och ekonometri.

• "Monte Carlo Statistical Methods", Christian Robert och George Casella, 2004
• Art B. Owen (2013). ”Monte Carlo theory, methods and examples”. http://statweb.stanford.edu/~owen/mc/. 

•   Wiki Commons har media som rör Monte Carlo-metod.
  Bilder & media