Baza teoretica
Metoda Monte Carlo se bazeaza pe legea numerelor mari si teorema limitei centrale. Estimarea θ̂ = (1/N)·Σf(xi) converge la θ cu rata √(Var(f)/N). Eroarea scade cu 1/√N — pentru o zecimala in plus ai nevoie de 100× mai multe esantioane.
Varianta redusa (Variance Reduction)
Tehnici de reducere a variantei:
- Importance sampling: esantionezi dintr-o distributie care pune mai multa masa in zonele importante
- Stratified sampling: imparti domeniul in straturi si esantionezi proportional
- Control variates: folosesti o functie cunoscuta corelata cu cea estimata
MCMC (Markov Chain Monte Carlo)
MCMC construieste un lant Markov a carui distributie stationara e distributia tinta. Algoritmul Metropolis-Hastings:
- Porneste de la o valoare initiala x0
- Propune o noua valoare x* din distributia de proposal q(x*|xt)
- Accepta cu probabilitatea min(1, π(x*)·q(xt|x*) / (π(xt)·q(x*|xt)))
MCMC e esential in statistica bayesiana, unde distributia posterioara e adesea imposibil de calculat analitic.
Monte Carlo Tree Search
MCTS combina cautarea in arbore cu esantionarea aleatoare. Eficienta vine din Upper Confidence Bound (UCT): UCT = W/n + c·√(ln(N)/n)
Unde W = castiguri, n = vizite locale, N = vizite totale, c = constanta de explorare.
AlphaGo a folosit MCTS + retele neuronale pentru a atinge nivel suprauman in Go.