Monte Carlo-metod

Monte Carlo-metoder är ett samlingsnamn för en viss typ av matematiska algoritmer som bygger på slumptal. 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.

Historia  
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.

Exempel

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 π.

Definition 
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  där  är en godtycklig funktion och  är mått över  (till exempel en sannolikhetsfördelning), med den numeriska approximationen  där  är  (möjligen viktade) slumptal med fördelning enligt . Med hjälp av stora talens lag kan man bevisa att approximationen  konvergerar mot  när . Typiskt används Monte Carlo-metoder när integralen inte går att lösa analytiskt, utan numeriska approximationer krävs. I förhållande till andra numeriska approximationer som inte bygger på slumptal är Monte Carlo-metoder jämförelsevis effektivare när problemets dimensioner (dimensionen på  ovan) ökar.

Den tekniska utmaningen i att konstruera en Monte Carlo-metod för ett problem är ofta att generera slumptalen .

Avancerade Monte Carlo-metoder

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.

Tillämpningar 

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.

Litteratur 
 "Monte Carlo Statistical Methods", Christian Robert och George Casella, 2004

Referenser

Externa länkar 

Statistik
Numerisk analys
Vetenskapshistoria
Teknikhistoria
Beräkningsfysik