I metodi Monte Carlo: il punto di incontro tra la matematica e il caso

Può il caso avere un ruolo in un calcolo matematico?

Apparentemente no, siamo abituati a pensare a un algoritmo matematico come qualcosa di deterministico. Ci sono dei dati di input e un risultato finale, se si esegue nuovamente il calcolo con gli stessi input si ottiene lo stesso risultato.

Eppure, esiste una vasta categoria di algoritmi che per funzionare usano il caso e per i quali ogni volta che si ripete il calcolo si ottiene un risultato diverso. Ma che utilità può avere un algoritmo di questo tipo?

Il punto è che nel campo della matematica applicata l’obiettivo è quello di risolvere problemi concreti. In questi casi, se non si riesce a trovare la soluzione teorica, trovarne una sufficientemente buona può essere comunque accettabile. Per questo motivo se la volta successiva l’algoritmo mi fornisce un risultato diverso ma ancora sufficientemente buono va bene lo stesso (cosa significhi sufficientemente buono dipende dalla particolare applicazione).

Gli algoritmi in questione si chiamano metodi Monte Carlo e potremmo definirli a grandi linee come tutti quegli algoritmi che per funzionare usano estrazioni di numeri casuali.

Esempio di simulazione Monte Carlo

Vediamo un esempio classico che serve a capire l’utilità e le caratteristiche principali di questi metodi: il calcolo di un’approssimazione di $\pi$ tramite una simulazione Monte Carlo.

Supponiamo di avere la possibilità di generare numeri casuali distribuiti in modo uniforme nell’intervallo $[0,1]$ (tutti i linguaggi di programmazione hanno funzioni che permettono farlo).

Se estraiamo una coppia di valori $(x,y)$ entrambi distribuiti in modo uniforme nell’intervallo $[0,1]$ possiamo interpretare $(x,y)$ come un punto estratto a caso all’interno del quadrato di lato 1 con vertici nei punti $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$.

Generando $n$ punti $(x_1,y_1), \ldots, (x_n,y_n)$ di questo tipo possiamo controlllare quali si trovano all’interno della circonferenza di raggio 1 centrata nell’origine del piano. Sono quelli per cui la distanza dall’origine $\sqrt{x_i^2+y_i^2}$ è minore di 1.

Osservazione importante: siccome i punti sono distribuiti uniformemente nel quadrato, la probabilità che uno di questi cada all’interno della circonferenza è uguale al rapporto tra l’area del settore circolare e l’area del quadrato.

Il quadrato ha area 1 mentre il settore circolare ha area $\pi/4$ (un quarto dell’area di un cerchio di raggio 1) per cui la probabilità che un singolo punto cada all’interno del cerchio è data da:

$$\displaystyle\frac{\text{AreaCerchio}}{\text{AreaQuadrato}} = \frac{\pi}{4}$$

Di conseguenza il rapporto tra il numero di punti che cadono dentro al cerchio e i punti totali tenderà a essere uguale a questo valore:

$$\displaystyle\frac{\text{numero di punti interni al cerchio}}{\text{numero di punti totali}} \longrightarrow\frac{\pi}{4}$$

Ma allora potrei:

1. estrarre moltissimi punti all’interno del quadrato;
2. contare quanti soddisfano $\sqrt{x^2+y^2} < 1$, cioè quanti si trovano all’interno della circonferenza;
3. calcolare il rapporto tra i punti che si trovano all’interno della circonferenza sul totale e moltiplicarlo per 4

ottenendo in questo modo un’approssimazione di $\pi$. Di seguito un’animazione che rende bene l’idea di cosa succede.

È un esercizio facile da fare anche con Excel, ecco un file di esempio: MonteCarloPi.xls.

Va chiarito che questo metodo ha solamente uno scopo didattico perché esistono algoritmi deterministici per il calcolo di $\pi$ molto più efficienti.

Tuttavia, è utile per capire la logica dei metodi Monte Carlo e il fatto che il risultato dell’algoritmo è casuale ma si avvicina gradualmente al risultato teorico aumentando il numero delle simulazioni.

Si può dimostrare che l’errore di stima di una simulazione Monte Carlo ha un andamento del tipo $1/\sqrt{n}$ dove $n$ è il numero di simulazioni effettuate. Per dimezzare l’errore bisogna quadruplicare il numero di simulazioni.

La più antica simulazione Monte Carlo

La più antica simulazione Monte Carlo potrebbe essere considerata l’esperimento dell’ago di Buffon ideato nel 1700.

Immaginiamo di avere un foglio su cui sono tracciate varie righe parallele equidistanziate tra loro e di gettare in modo casuale un bastoncino su questo foglio. Il bastoncino può cadere in modo da essere completamente contenuto tra due rette oppure può intersecare una o (se abbastanza lungo) più parallele.

Se il bastoncino è più corto della distanza tra le parallele si può dimostrare che la probabilità che il bastone intersechi una retta è data da

$$\displaystyle P = \frac{2l}{\pi d}$$

dove $l$ è la lunghezza del bastoncino e $d$ è la distanza tra le parallele. Visto che nella formula compare $\pi$, l’esperimento può essere usato per creare delle stime di $\pi$ in modo analogo a prima. Basta lanciare molte volte il bastoncino per stimare la probabilità $P$, $l$ e $d$ sono note per cui è possibile invertire la formula e ricavare una stima di $\pi$.

La rivoluzione informatica

Gli esperimenti tipo l’ago di Buffon non ebbero alcuna utilità reale poiché richiedevano un numero di ripetizioni troppo grande per ottenere risultati che avessero un buon grado di approssimazione.

Le cose cambiarono drasticamente verso la metà del secolo scorso con l’avvento dei computer. La nuova tecnologia permetteva di eseguire simulazioni con una velocità sufficiente per cominciare a risolvere alcuni problemi pratici non risolvibili in altro modo.

I pionieri dei metodi Monte Carlo sono stati Stanislaw Ulam e John Von Neumann. Nel 1946 entrambi lavoravano al progetto Manhattan per la costruzione della bomba atomica e utilizzarono dei metodi Monte Carlo per eseguire un calcolo sulla probabilità di assorbimento della radiazione da neutroni che non erano riusciti a risolvere con metodi teorici.

L’idea venne a Ulam mentre era convalescente da una malattia. Per passare il tempo giocava a un solitario con le carte e si chiese quale fosse la probabilità di completarlo correttamente. Le regole del solitario rendevano difficile il calcolo di questa probabilità.

Pensò che si sarebbero potute simulare con un computer molte disposizioni casuali di un mazzo di carte e controllare in quanti di questi casi si riusciva a completare il solitario. In questo modo si poteva calcolare la probabilità di vincere al solitario in modo empirico.

Ulam ne parlò con Von Neumann il quale, essendo un tipo piuttosto sveglio, comprese il potenziale di questa intuizione e sviluppò il primo algoritmo che permetteva di generare numeri casuali con un computer.

Rientrando nei piani segreti per la costruzione della bomba atomica bisognava assegnare un nome in codice al progetto. Visto che il caso svolgeva un ruolo importante nel metodo di stima, fu scelto il nome in codice Monte Carlo, sede del famoso casinò, e questo è il motivo per cui ancora oggi si usa questa terminologia.

Da allora questi metodi sono stati utilizzati nei più disparati campi: previsioni meteorologiche, fisica delle particelle elementari, astrofisica, chimica molecolare, elettronica, dinamica dei fluidi, biologia, computer grafica, intelligenza artificiale, finanza, valutazione di progetti… e molti altri!

Nonostante la varietà di applicazioni i metodi Monte Carlo rientrano grossomodo in tre famiglie: integrazione numerica, ottimizzazione, generazione di distribuzioni di probabilità.

Per altri esempi di simulazioni Monte Carlo vedi l’articolo I metodi Monte Carlo in azione.