I metodi Monte Carlo in azione

Nell’articolo I metodi Monte Carlo: il punto di incontro tra la matematica e il caso abbiamo ripercorso la storia dei metodi Monte Carlo. Nonostante la grande varietà di applicazioni possibili, essi rientrano grossomodo in tre grandi famiglie:

• integrazione numerica
• ottimizzazione
• generazione di distribuzioni di probabilità

Oggi vediamo i metodi Monte Carlo in azione e analizziamo degli esempi di applicazione per ciascuna di queste tipologie.

Integrazione Monte Carlo

Un semplice metodo Monte Carlo permette di calcolare un valore approssimato per l’area di un settore circolare. Per prima cosa si generano molti punti casuali all’interno di un quadrato di lato 1. Poi si conta il numero di punti che cadono all’interno della circonferenza di raggio 1.

Il rapporto tra i punti che cadono all’interno e i punti totali è proporzionale al rapporto tra l’area del settore circolare e l’area del quadrato. Essendo l’area del quadrato uguale a 1 aumentando i punti questo rapporto si avvicina sempre più all’area del settore circolare.

È intuibile come questo approccio si possa generalizzare per calcolare aree di forma diversa.

Dalle nostre conoscenze di analisi sappiamo che un’area può essere calcolata anche tramite integrali definiti del tipo

$$A =\displaystyle \int_a^b f(x) dx$$

Ma allora quando utilizziamo il metodo Monte Carlo per calcolare delle aree non stiamo facendo altro che calcolare un’approssimazione di un integrale definito.

Questo approccio non è molto utile quando si vogliono calcolare integrali in una dimensione, in questo caso esistono metodi di calcolo deterministici molto più efficienti, nel senso che in meno tempo restituiscono risultati che hanno meno incertezza rispetto ai metodi Monte Carlo.

Tuttavia, se si vogliono calcolare integrali su molte dimensioni i metodi deterministici diventano meno efficienti mentre i metodi Monte Carlo sono a questo punto competitivi.

A cosa è dovuto questo strano fenomeno?

Dato un certo grado di precisione che si vuole raggiungere nel calcolo, i metodi deterministici richiedono un numero di passaggi elementari che cresce in modo esponenziale al crescere del numero di dimensioni. Nei metodi Monte Carlo invece l’errore che ci si aspetta dalla stima dipende solo dal numero di estrazioni totali e non dal numero di dimensioni.

Ad esempio, per calcolare un integrale in 100 dimensioni gli approcci deterministici richiederebbero una tale mole di calcoli da risultare inutilizzabili mentre i metodi Monte Carlo sono ancora applicabili.

Ma in che casi è necessario calcolare integrali con così tante dimensioni? Succede tipicamente in meccanica statistica, branca della fisica teorica che studia i sistemi con molti gradi di libertà. Ad esempio, un gas racchiuso in una scatola ha moltissimi gradi di libertà, dovuti al gran numero di particelle presenti. Per calcolare il valore che assumono le grandezze macroscopiche come temperatura o pressione, vanno calcolati integrali con un numero di dimensioni proporzionale al numero di particelle coinvolte.

Il numero di dimensioni su cui vengono calcolati questi integrali può diventare molto grande e in questi casi i metodi Monte Carlo sono più efficienti di quelli deterministici.

Ottimizzazione numerica

Ci sono vari algoritmi utilizzati per trovare i minimi locali di una funzione. Tipicamente questi algoritmi

1. partono da un punto assegnato;
2. controllano in che direzione la funzione tende ad avere valori più piccoli di quello attuale;
3. spostandosi in questa direzione trovano un nuovo punto in cui la funzione ha valore minore del precedente;

e continuano a ripetere queste operazioni fino a quando raggiungono un minimo (in questo caso al punto 2 non è possibile determinare in che direzione spostarsi).

Cosa succede però se abbiamo una funzione con molti minimi locali e vogliamo trovare il punto che globalmente minimizza la funzione?

Un algoritmo di ricerca locale potrebbe fermarsi in qualsiasi dei molti minimi locali della funzione.

Come potrebbe capire un algoritmo se ha trovato uno dei tanti minimi locali o il minimo globale? In realtà non c’è modo di stabilirlo rigorosamente. L’unica possibilità pratica è quella di esplorare diverse zone del dominio di ricerca per aumentare la probabilità di trovare, tra i vari minimi locali, quello globale.

In questa ottica sono stati sviluppati diversi metodi realizzare questa idea di “esplorare” domini che possono essere molto complicati (a molte dimensioni e con vincoli da rispettare). In particolare vanno molto di moda quelli che sono noti come algoritmi genetici e che si ispirano a logiche evoluzionistiche.

Questi sono di fatto dei metodi Monte Carlo tramite i quali si crea una popolazione iniziale di punti appartenenti al dominio, la si fa evolvere definendo degli algoritmi di accoppiamento tra i punti (dalle coordinate di due punti genero un nuovo punto) nei quali intervengono anche delle mutazioni genetiche casuali. Nella simulazione delle diverse generazioni di punti interviene un processo di selezione che mantiene solo i punti migliori (quelli che danno valori più bassi della funzione da minimizzare).

Ad ogni generazione si tiene traccia di qual è il punto che rappresenta il migliore “esemplare” di sempre.

Continuando con questo processo i punti tendono a spostarsi verso i minimi locali ma esplorando molte zone del dominio di ottimizzazione. Il procedimento può continuare in modo indefinito, a un certo punto viene fermato (solitamente mettendo un limite al numero di generazioni) e il migliore esemplare di sempre viene preso come stima del minimo globale (di solito questo viene usato come punto di partenza per un successivo algoritmo di ottimizzazione locale).

Generazione di distribuzioni di probabilità

L’ultimo tipo di applicazione riguarda la generazione di distribuzioni di probabilità che non si riescono a trovare con metodi analitici.

Esempio: stimare la distribuzione di probabilità dei danni provocati dai tornado in un anno negli Stati Uniti.

In questo tipo di analisi ci sono due fonti di incertezza: quanti tornado ci saranno in un anno e ciascun tornado quanti danni farà. Anche se si riesce ad assegnare una distribuzione di probabilità a questi due livelli logici, non sempre con metodi analitici è possibile mettere assieme queste informazioni per ricavare la distribuzione delle perdite annuali.

È più semplice invece fare una simulazione Monte Carlo di questo tipo:

1. si estrae un numero casuale dalla distribuzione del numero di eventi annuali;
2. se dal punto precedente risultano $n$ eventi, si fanno $n$ estrazioni dalla distribuzione delle perdite;
3. si sommano i valori delle $n$ estrazioni del punto 2) ottenendo un valore che rappresenta una perdita annuale causata da $n$ eventi.

Ripetendo ciclicamente questi tre punti si genera un campione di perdite annuali dal quale si può stimare la distribuzione di probabilità che non si riusciva a ricavare in modo analitico.