Ilmetodo Monte Carlo è un'ampia classe di metodi computazionali basati sul campionamento casuale per ottenere risultati numerici. Può essere utile per superare i problemi computazionali legati aitestesatti (ad esempio i metodi basati sulladistribuzione binomiale ecalcolo combinatorio, che per grandi campioni generano un numero dipermutazioni eccessivo).
Il metodo è usato per trarre stime attraverso simulazioni.Si basa su unalgoritmo che genera una serie di numeri tra loro non correlati, che seguono ladistribuzione di probabilità che si suppone abbia il fenomeno da indagare.La non correlazione tra i numeri è assicurata da untest chi quadrato.
La simulazione Monte Carlo calcola una serie di realizzazioni possibili del fenomeno in esame, con il peso proprio della probabilità di tale evenienza, cercando di esplorare in modo denso tutto lo spazio dei parametri del fenomeno. Una volta calcolato questo campione casuale, la simulazione esegue delle 'misure' delle grandezze di interesse su tale campione. La simulazione Monte Carlo è ben eseguita se il valore medio di queste misure sulle realizzazioni del sistema converge al valore vero.
L'algoritmo Monte Carlo è un metodo numerico utilizzato per trovare le soluzioni di problemi matematici a molte variabili e che non possono essere risolti facilmente, per esempio ilcalcolo integrale. L'efficienza di questo metodo aumenta rispetto agli altri metodi quando ladimensione del problema cresce.
Un primo esempio di utilizzo del metodo Monte Carlo è rappresentato dall'esperimento dell'ago di Buffon; il suo più famoso utilizzo fu quello diEnrico Fermi, che nel1930 usò un metodo casuale per problemi di trasporto neutronico[1].
Il metodo Monte Carlo può essere illustrato come unabattaglia navale. Prima un giocatore spara colpi a caso. Successivamente applica alcuni algoritmi (es. la corazzata è di quattro punti nella direzione verticale o orizzontale). Infine, sulla base dei risultati del campionamento casuale e degli algoritmi, il giocatore può determinare le posizioni probabili delle navi degli altri giocatori.
Non c'è un solo metodo Monte Carlo; il termine descrive una classe di approcci utilizzati per una larga categoria di problemi. Tuttavia, questi approcci tendono a seguire un particolare schema:
I metodi deterministici diintegrazione numerica operano considerando un numero di campioni uniformemente distribuiti. In generale questo metodo lavora molto bene per funzioni di una variabile. Tuttavia, per funzioni divettori, i metodi deterministici di quadratura possono essere inefficienti. Per integrare numericamente una funzione di un vettore bidimensionale sono richieste griglie di punti equispaziati sulla superficie stessa. Per esempio una griglia di 10x10 richiede 100 punti. Se il vettore è a 100 dimensioni, la stessa spaziatura sulla griglia dovrebbe richiedere 10100 punti – troppo dispendioso computazionalmente. Le 100dimensioni non hanno un significato irragionevole, poiché in molti problemi di fisica, una "dimensione" è equivalente a ungrado di libertà.
I metodi di Monte Carlo forniscono una soluzione a questo problema di crescita del numero di gradi di libertà. Finché la funzione in questione ha un buon comportamento, può essere valutata selezionando in modo casuale i punti in uno spazio 100-dimensionale, e prendendo alcune tipologie di medie dei valori della funzione in questi punti. Per ilteorema del limite centrale, questo metodo mostrerà ordine di convergenza; per esempio quadruplicando il numero dei punti equispaziati si dimezza l'errore, nonostante il numero delle dimensioni.
Una caratteristica di questo metodo è quella di scegliere i punti in modo casuale, ma vengono scelti con maggior probabilità i punti che appartengono alle regioni che contribuiscono maggiormente al calcolo dell'integrale rispetto a quelli che appartengono a regioni di basso contributo. In altre parole, i punti dovrebbero essere scelti secondo una distribuzione simile in forma alla funzione integranda. Comprensibilmente, fare ciò è difficile tanto quanto risolvere l'integrale, ma ci sono altri metodi di approssimazione possibili, a partire da quelli che costruiscono unafunzione integrabile simile a quella da integrare, fino ad arrivare ad una delle procedure adattive.
Un simile approccio implica l'uso dilow-discrepancy sequences piuttosto delmetodo quasi-Monte Carlo. I metodi Quasi-Monte Carlo spesso possono essere più efficienti comemetodi di integrazione numerica poiché la successione di valori generata riempie meglio l'area e le successive valutazioni possono far convergere più velocemente la simulazione alla soluzione.
Per un modello stocastico sia θ la quantità da determinarsi. Si esegua una simulazione, generando lavariabile casuale in modo che θ sia ilvalore atteso di Consideriamo una seconda simulazione, generando una variabile casuale tale che il suo valore atteso sia sempre θ. Proseguiamo con simulazioni, generando fino a variabili casuali con Come stimatore di θ possiamo prendere la media aritmetica delle variabili casuali generate, cioè
in quanto Qual è il valore più appropriato di? Supponiamo di avere variabili aleatorie indipendenti, aventi la stessa distribuzione. Sia σ2 la varianza della variabile e θ il valore atteso, ossia
Pertanto è una variabile aleatoria con media θ e varianza ne segue che è uno stimatore efficiente quando è piccolo. Fissata una tolleranza per ed avendo stimato si può in tal modo stimare
Si può imporre che il valore atteso ottenuto con lo stimatore stia dentro un ben definitointervallo di confidenza. Si può a tale scopo utilizzare una conseguenza delteorema del limite centrale. Sia una successione di variabili casualiindipendenti e distribuite identicamente aventi la media finita μ e la varianza finita σ2. Allora
Quando il teorema del limite centrale ci dice che la variabile
è approssimativamente distribuita come una variabile aleatoria normale unitaria, indicata con cioè con media zero e varianza 1. Sia ora dove quel numero tale che, per una variabile normale unitaria, si abbia
Allora, dal teorema del limite centrale si ha che, asintoticamente per grande
che afferma che la probabilità che la media θ sia compresa nell'intervallo
è 1-α. Perciò, assegnato 1-α e conoscendo σ, si può stimare il minimo valore di necessario.
Nasce quindi il problema di come stimare la varianza σ2 = E[(X - θ)2].
Definizione. La varianza del campione S2 è definita da
Vale il seguente risultato.
Proposizione. E[S2]= σ2Infatti si ha:
ne segue
Per una variabile aleatoria si ha:
e quindi
Inoltre
Ne segue
Supponiamo ora di avere variabili aleatorie indipendenti aventi la stessa funzione di distribuzioneF e di volere stimare il parametro θ(F) (per evidenziare che tale quantità deve essere calcolata rispetto alla funzione di distribuzioneF). Sia lo stimatore proposto per θ(F); se questo non corrisponde al valore medio, il metodo precedentemente esposto per stimare la varianza dello stimatore non si può applicare. Vediamo come si può stimare l'errore quadratico medio che si commette quando si usa questo stimatore:
dove il pediceF significa che il valore d'aspettazione viene calcolato rispetto alla funzione di distribuzioneF che per il momento è incognita.
Un metodo per stimare tale quantità è quello delbootstrap, utilizzando la funzione di distribuzione empiricaFe(x) definita da:
La legge forte dei grandi numeri afferma che per molto grande, con probabilità 1,Fe(x) tende aF(x). Allora un valore approssimato di EQM(F) è dato da (approssimazione di bootstrap):
Va rilevato, da un punto di vista operativo, che ildimensionamento della simulazione si supera facilmente grazie alla crescente disponibilità di potenza di calcolo.In altre parole, procedendo all'uso del metodo su calcolatore, sarà sufficiente generare una serie di prove di ampiezza sicuramente ridondante per assicurarsi la significatività della stima.
Si voglia stimare il rendimento mensile di untitolo azionario. Il titolo esiste da cinque anni, quindi si hanno a disposizione solo 60 rendimenti mensili. Supponiamo che i rendimenti si distribuiscano seguendo unavariabile casuale normale.
Con un modello diregressione lineare cercheremo di stimare lamedia a un mese. Successivamente, si andranno a generare attraverso l'algoritmo Monte Carlo una serie di medie "sperimentali" che saranno ricavate da una distribuzione normale (perché si è ipotizzato che i rendimenti seguano questa distribuzione) con media pari alla media stimata e scarto quadratico medio pari allo scarto quadratico medio campionario a un mese.
Una strategia per procedere e stimare la vera media del fenomeno, a questo punto, può essere quella di ricavare la media generale di tutte le medie sperimentali ottenute.I dati ottenuti forniscono stime tanto migliori quanto maggiore è il numero delle prove fatte.
Il metodo Monte Carlo applicato nell'approssimazione del valore di π.
Sia un punto di coordinate con e e scegliamo casualmente i valori di e
Se allora il punto appartiene al settore di disco (un quarto del cerchio a cui appartiene) di centro di raggio 1.
L'area del settore di disco è il raggio elevato al quadrato per diviso 4. Nell'esempio il raggio è uguale a uno e quindi l'area di interesse è Il punto può cadere quindi o nel quarto di cerchio o nel quadrato circoscritto al settore di disco. La probabilità che il punto cada all'interno del settore di disco è quindi uguale al rapporto tra l'area del settore e l'area del quadrato circoscritto al settore di disco che è uguale a 1; quindi la probabilità è
Facendo il rapporto del numero dei punti che cadono nel settore di disco con il numero dei tiri effettuati si ottiene un'approssimazione del numero se il numero dei tiri è grande.
Eseguendo numericamente l'esempio si ottiene un andamento percentuale dell'errore mostrato nel grafico sottostante.
Andamento percentuale dell'errore tra il teorico e il calcolato. Il programma ha eseguito 1370 milioni di lanci. Si noti che all'inizio l'errore è molto elevato ma rapidamente tende a decrescere. Essendo un metodo statistico ci possono essere dei temporanei innalzamenti dell'errore ma la tendenza è la sua diminuzione all'aumento dei lanci.
Questo è un esempio classico della divulgazione del metodo Monte-Carlo. Sia data una zona rettangolare o quadrata di cui la lunghezza dei lati è conosciuta. Al centro di quest'area si trova un lago la cui superficie è sconosciuta. Grazie alle misure dei lati della zona, si conosce l'area del rettangolo. Per determinare l'area del lago, si chiede ad una truppa armata di tirare colpi di cannone in modo aleatorio su questa zona. Contiamo in seguito il numero di palle che sono restate sulla terra, possiamo quindi determinare il numero di palle che sono cadute dentro il lago: È sufficiente quindi stabilire un rapporto tra i valori:
Per esempio, se il terreno ha superficie di 1000 m2, e supponiamo che l'armata tiri 500 palle e che 100 proiettili sono caduti dentro il lago allora la superficie del lago è di: 100*1000/500 = 200 m2.
Stima della superficie del lago grazie a dei tiri di cannone casuali
Naturalmente, la qualità della stima migliora aumentando il numero dei tiri ed assicurandosi che l'artiglieria non miri sempre lo stesso posto ma copra bene la zona. Questa ultima ipotesi coincide con l'ipotesi di avere un buongeneratore di numeri aleatori, questa condizione è indispensabile per avere dei buoni risultati con il metodo Monte Carlo. Un generatore distorto è un po' come un cannone il cui tiro tende a indirizzarsi verso alcune zone rispetto ad altre: le informazioni che se ne possono ricavare sono anch'esse distorte.
È molto potente se usato in combinazione con altri metodi non parametrici come ilresampling.
Un altro esempio particolare dell'utilizzo del Metodo Monte Carlo è l'impiego del metodo nell'analisiscacchistica. Negli ultimi anni alcuniprogrammi scacchistici in commercio implementano delle opzioni d'analisi che utilizzano "Monte Carlo analisi". Per valutare una posizione, si fanno giocare al computer migliaia di partite partendo dalla posizione da analizzare, facendo eseguire al PC delle mosse "casuali" (una scelta casuale tra le mosse che il programma giudica più logiche).La media dei risultati ottenuti in queste partite è un'indicazione plausibile della mossa migliore.[2]
Il metodo Monte Carlo trova un'applicazione di successo ancora maggiore nelgioco del go. In tal caso l'applicazione del metodo è ancora più diretta: molti programmi raggiungono un buon livello di gioco senza aver bisogno di restringere la selezione casuale a un sottoinsieme di mosse legali determinato da una funzione di valutazione (esempio di programma che usa questo metodo in unione con ilmachine learning èAlphaGo).
W. K. Hastings,Monte Carlo sampling methods using Markov chains and their applications, Biometrika, 1970, pp. 97-109.
Bernd A. Berg,Markov Chain Monte Carlo Simulations and Their Statistical Analysis (With Web-Based Fortran Code), World Scientific 2004,ISBN981-238-935-0.
P. Kevin MacKeown,Stochastic Simulation in Physics, 1997,ISBN 981-3083-26-3
Harvey Gould & Jan Tobochnik,An Introduction to Computer Simulation Methods, Part 2, Applications to Physical Systems, 1988,ISBN 0-201-16504-X
C.P. Robert and G. Casella. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, 2004,ISBN 0-387-21239-6
Morin, L. Richard,Monte Carlo Simulation in the Radiological Sciences, CRC Press,ISBN 0-8493-5559-1.
Arnold Kaufmann,La fabbricazione artificiale del caso; il metodo di Monte Carlo, inLe tecniche decisionali. Introduzione alla Praxeologia, traduzione diGiampaolo Barosso, Milano,il Saggiatore, 1968,SBNSBL0076985.
