Blog divulgativo sulla matematica applicata

I metodi Monte Carlo (seconda parte)

roulette

Ci siamo lasciati la volta scorsa  dicendo che, nonostante la grande varietà di applicazioni possibili, i metodi Monte Carlo rientrano grossomodo in tre grandi famiglie: integrazione numerica, ottimizzazione, generazione di distribuzioni di probabilità. Vediamo ora tre esempi di queste tipologie.

Anticipo che gli argomenti sono potenzialmente molto estesi per cui il post sarà piuttosto discorsivo... giusto una chiaccherata per avere un'idea sulle possibili applicazioni dei metodi Monte Carlo.

Integrazione Monte Carlo

Nel post precedente abbiamo visto un metodo Monte Carlo con cui calcolare un valore approssimato per l'area di un settore circolare. Il trucco stava nel contare quanti punti estratti a caso all'interno del quadrato di lato 1 ricadevano dentro alla circonferenza.

simulazione

 

È intuibile come questo approccio si possa generalizzare in modo 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 sistema di molte particelle chiuse in una scatola. Per calcolare il valore che assumono le grandezze macroscopiche come temperatura o pressione, è necessario svolgere integrali con un numero di dimensioni proporzionale al numero di particelle coinvolte.

Capite che il numero di dimensioni su cui vengono calcolati questi integrali può diventare molto grande, in questi casi i metodi Monte Carlo sono più utilizzati 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).

LocalOptimization

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

LocalMinima

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.

Nel prossimo post vedremo (e questa volta con qualche dettaglio matematico in più) come vengono usate le simulazioni Monte Carlo per assegnare un prezzo ai derivati finanziari.

Ciao!

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Similar posts

Nessun commento ancora

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Canale Telegram dedicato alla Matematica

Iscriviti sul nostro canale Telegram

MIA15 - Nomination

Rimani aggiornato sui più interessanti articoli di divulgazione matematica e non solo!

Iscriviti alla nostra newsletter

Resta aggiornato sui nostri post e su quello che facciamo.

Seguici su Twitter

Tag Cloud

Grazie per il sostegno ai #MIA2015

Grazie a tutti per averci votato ai "Macchia Nera Awards 2015" nella categoria "Miglior Sito Tecnico-Divulgativo".

Siamo arrivati in finale grazie al vostro sostegno!

MIA15 - Nomination