Metodo Montecarlo

Seminario di Metodi Matematici per l’Ottimizzazione

Giuseppe Sammatrice Daniele Licitra

AA 2011/12

Indice

• Introduzione• Integrazione numerica

– Approssimazione rettangolare– Regola del trapezio– Regola di Simpson

• Metodi Montecarlo– Hit or Miss– Sample Mean– Confronti

Indice

• Efficienza del Metodo Montecarlo

• Tecniche di riduzione della varianza– Variabili antitetiche

• Numeri casuali e pseuocasuali

• Calcolo di un integrale

• Stima del valore di un titolo quotato in borsa

• Conclusioni

Descrizione

Il metodo Montecarlo consiste nell’effettuare una simulazione utilizzando N campioni casuali per studiare un processo.

Di seguito, un possibile algoritmo• 1. Definire un dominio di applicazione.• 2. Generare Variabili Aleatorie con una

determinata funzione di distribuzione.• 3. Elaborare i dati in input.• 4. Stimare il valore ottenuto.

Cenni storici

• Enrico Fermi negli anni ’30 studiò il moto dei neutroni utilizzando stime ottenute con tecniche di campionamento statistico;

• Il metodo Monte Carlo fù formalizzato negli anni ’40 da J. Von Neumann e S. Ulam che parteciparono al progetto Manhattan per lo studio della dinamica dell’esplosione nucleare;

• Il nome Monte Carlo fu coniato da Nicholas Costantine Metropolis in riferimento a Montecarlo, sede del celebre casinò;

Fenomeni nucleari

• Negli esperimenti nucleari una particella colpisce il nucleo di un atomo: questo si frantuma in particelle che vanno a colpire i nuclei di altri atomi vicini, che si frantumano a loro volta secondo una reazione a catena.

• Il processo durerà all’infinito o si arresterà dopo un certo numero di reazioni?

• I fisici di allora erano certi del fatto che la reazione avrebbe avuto termine?

Applicazioni

• Fisica : moto delle particelle, reazioni nucleari;

• Medicina: radioterapia;

• Finanza: simulazione dei mercati;

• Matematica: calcolo di integrali ed aree, simulazioni stocastiche;

Integrazione Numerica

Si cerca di approssimare l’integrale

);()()( aFbFdxxfIb

a

con una procedura numerica come:

• approssimazione rettangolare;

• regola del trapezio;

• formula di Simpson;

Approssimazione rettangolare

1

0

;)(n

ii hxfr

Approssimazione rettangolare

1

0

;)(n

ii hxfr

;,...,2,1;1 nixxh ii

• Il costo computazionale di questo metodo numerico è di O(n) dove n è il numero di intervalli presi in considerazione;

• Se p(x) è l’approssimazione della f(x), l’errore è:

n

xhfab

dxxpxfrIEb

a

1)(

2)()( 1

Regola del trapezio

hxfxfxfr n

n

ii

)()()( 21

1

102

1

Regola del trapezio

hxfxfxfr n

n

ii

)()()( 21

1

102

1

;,...,2,1;1 nixxh ii

• Il costo computazionale è di O(n);

• L’errore in questo caso è:

;1

)(''2 2

2

nxfh

abE

Regola di Simpson

;)()(4...)(4)( 2121032 nnh

n xfxfxfxfS

• Il costo computazionale è di O(n);

• L’errore in questo caso è:

;1

)(180 4

4

nxfh

abE IV

Metodi Montecarlo

Esistono due metodi Montecarlo per calcolare il valore approssimato di un integrale definito di una funzione I:

– Metodo “Hit or Miss”;

– Metodo di “Sampling” o “Sample Mean”;

Metodo Hit or Miss

• Sia f(x) definita in [a,b] e limitata, cioè∃c R : 0 ≤ f (x) ≤ c.∈

• Consideriamo il rettangoloΩ = { (x, y) | a ≤ x ≤ b, 0 ≤ y ≤ c }

e quindi il vettore (x,y) di numeri casuali uniformemente distribuiti in Ω.

• La probabilità p che il vettore (x,y,) cada sotto la curva f(x) è

;)()(

)(

abc

I

abc

dxxf

area

areaSp

b

a

Metodo Hit or Miss

Pseudo-codice Hit or Miss

HIT_MISS(f,a,b,c,N)per i = 1 → N

xi ←R [a,b];

yi ←R [0,c];

Pi ← (xi, yi);fine per

NH ← 0

per ogni Pi

if f(xi)>yi

NH ← NH+1;

fine per

p= NH / N;Return c(b-a)p;

• Genero N vettori casuali (xi,yi)

• Verifico, per ogni (xi,yi) se f(xi)>yi , in questo caso incremento di 1 il numero di hit;

• Calcolo p = NH / N;

• Stimo l’integrale con:

pabc )(

Metodo Hit or Miss

• Per le sue iterazioni, il metodo ha un costo computazionale di O(N);

• Più è grande N, maggiore sarà la probabilità di ottenere una buona approssimazione;

Metodo Sample Mean• E’ un metodo per la stima di un integrale• Deriva dall’approssimazione rettangolare

b

adxxfI )(

Nell’approssimazione rettangolare, l’intervallo (a,b) viene suddiviso in N sotto-intervalli regolari;

Nel metodo Sample Mean si generano N punti nell’intervallo (a,b) con distribuzione uniforme e se ne valuta la f(x).

Pseudo-Codice Sample Mean

SAMPLE_MEAN(f,a,b,N)per i = 1 → N

Ui ←R [0,1];

xi ← a+Ui(b-a);fine persum ← 0;per i = 1 → N

sum←sum+f(xi);fine pertheta ← (b-a)sum/N;return theta;

• Si scelgono N numeri casuali uniformemente in [0,1];

• Si adattano i valori all’intervallo;

• Si approssima l’integrale con:

N

i iN xfab1

1 );()(

Metodo Sample Mean

• Per le sue iterazioni, il metodo ha un costo computazionale di O(N);

• Più è grande N, maggiore sarà la probabilità di ottenere una buona approssimazione;

• Non sempre il metodo converge alla soluzione!

Tempi a confronto

• Approssimazione rettangolare : O(n);• Approssimazione trapezoidale: O(n);• Approssimazione con Simpson: O(n);• Hit or Miss: O(n);• Sample Mean: O(n);

• Tutti i metodi impiegano un tempo lineare nell’approssimare gli integrali.

Errori a confronto• Sia d il numero di dimensioni dell’integrale:

• Errore rettangoli

• Errore trapezi

• Errore Simpson

• Errore Montecarlo

;21dn

E

;41dn

E

;11dn

E

dEn

;1

Confronto

• Dato che tutti i metodi hanno costo computazionale pari a O(N), è preferibile usare formule con gli errori minori;

• Nel caso di una dimensione usiamo Simpson;

• Al crescere di d scegliamo i metodi Montecarlo;

Efficienza del Metodo Montecarlo

• Hit or Miss genera una stima θ1 mentre Sample mean genera un’altra stima θ2 tali che

E[θ1] = E[θ2] = I

V [θ1] ≠ V [θ2]

• Siano t1 e t2 i tempi di calcolo per θ1 e θ2. Il primo metodo è più efficiente del secondo se

1][

][

22

11

Vt

Vt

Efficienza del Metodo Montecarlo

Varianza Hit or Miss:

Varianza Sample Mean:

];)([1

][ 1 IabcN

V

];)()[(1

][ 222 Idxxfab

NV

b

a

Efficienza del Metodo Montecarlo

Teorema:

V [θ2] < V [θ1]Dim:

])([1

])()[(1 22 Iabc

NIdxxfab

N

b

a

])()[(][][ 2121

b

aN dxxfcIabVV

Efficienza del Metodo Montecarlo

Poiché f(x)≤c, allora f(x)f(x) ≤f(x)c, integrando

Allora V [θ2] < V [θ1] .

Se t1 ≈ t2, allora il metodo di Sampling è più efficiente del metodo Hit or Miss

b

acIdxxf )(2

Tecniche di Riduzione della Varianza

• Si può ridurre la varianza soltanto se si hanno informazioni sul problema da trattare. Ad esempio si possono ottenere informazioni effettuando un analisi grossolanda del problema.

• Alcuni utili metodi sono:– Importanza del Campionamento– Variate di Controllo– Campionamento Stratificato– Variabili Antitetiche

• Analizzeremo in dettaglio il metodo delle variabili antitetiche.

Variabili Antitetiche

• Con questa tecnica si cercano due stimatori dell’ Integrale I, tali che abbiano una forte correlazione negativa.

• Osservazione: se Ui è una variabile casuale distribuita uniformemente in [0,1], allora anche 1 − Ui è una variabile distribuita uniformemente nello stesso intervallo.

Variabili Antitetiche

• Uno stimatore di I è

• Affinchè questo stimatore sia più efficentedi quello del metodo di Sampling θ2 occore che:

• Poiché tA = 2t2, segue che V[θA] ≤ ½ V[θ2];• Si dimostra che questo risultato è valido sse f(x) è una

funzione continua e monotona non crescente con derivata prima continua.

N

i iiNA UfUf12

1 )]1()([

1][

][

22

Vt

Vt AA

Numeri casuali ?

• In teoria si lavora con numeri casuali;

• Sono generati dall’estrazione da un’urna, da una roulette, dal lancio di un dado o di una moneta…

• I computer sono strumenti deterministici, non conoscono il concetto di casualità;

• Può un computer generare numeri casuali?

Numeri pseudo-casuali

• In pratica il computer utilizza numeri pseudo-casuali;

• Sono generati secondo una sequenza:

S → r0 → r1 →…

• Il numero s è detto seed. Utilizzando lo stesso seed avremo la stessa sequenza di numeri casuali;

• Questo processo è chiamato Markov-Chain;

Una buona funzione casuale

• Una funzione pseudo-casuale (PRF) è una funzione del tipo F: KxD → R;– K è l’insieme delle chiavi o seed;– D è il dominio (la funzione è stata richiamata

la x-esima volta, con x € D);– R è il codominio;

• Per semplicità ignoriamo D e indichiamo la funzione con FK

Una buona funzione casuale• Sia F una famiglia di PRF del tipo FK: D → R;

• Sia A un avversario che ha accesso a scatola chiusa alla funzione;

EspFprf-1(A)

k ←R K;

b ← A(Fk);

Return b

//funzione PC

EspFprf-0(A)

g ←R Func(D,R);

b ← A(g);

Return b

//funzione casuale

• Negli esperimenti l’avversario riceve una funzione senza sapere se questa sia PRF o casuale;

• Non si limita il comportamento dell’avversario;• Possiamo limitare il suo tempo di calcolo o il

numero di valutazioni;

• Adv(A) = |Pr(EspFprf-1(A)=1) – Pr(EspF

prf-0(A)=1)|;• La funzione è una buona funzione casuale se il

vantaggio di A è piccolo.

Una buona funzione casuale

Numeri pseudo-casuali

Nei test:

• Si usano seed diversi per avere stime diverse;

• Si usa lo stesso seed se vogliamo stimare l’accuratezza di una stima ottenuta con metodi diversi, in modo tale la stima non sia influenzata dai numeri casuali, i test hanno la stessa “fortuna”;

Numeri pseudo-casuali in Matlab

• La funzione utilizzata è rand(N,M);

Ritorna una matrice NxM riempita con valori estratti dalla distribuzione uniforme nell’intervallo (0,1)

• Per impostare il seed si usa rand(‘seed’,N) , dove N è il valore del seed;

Calcolo di un integrale

• Calcoliamo l’integrale analiticamente

;63662,0)0sin()sin(

)sin()cos(

222

2

1

0

1

022

2

xxI

Calcolo di un integrale• Approssimiamo l’integrale con il metodo Hit or Miss al

variare di N:

Calcolo di un integrale• Approssimiamo l’integrale con il metodo Sample Mean al

variare di N:

I due metodi a confronto

Calcolo con seed variabileSi esegue Hit or Miss t=1000 volte, con N=100000 ma con sequenze casuali diverse e si prende la media

Calcolo con seed variabileSi esegue Sample Mean t=1000 volte, con N=100000 ma con sequenze casuali diverse e si prende la media

Stima del valore di un titolo quotato in borsa

Il mercato finanziario

• Un mercato è il luogo di incontro tra la domanda e l’offerta;

• In un mercato finanziario, le merci scambiate sono prodotti finanziari;

• La molteplicità degli attori partecipanti in questi processi (Stati, banche, broker, imprese), la variabilità delle condizioni di contrattazione, l’influenza di infiniti fattori (naturali, economici, politici, sociali,…) nelle dinamiche dei mercati mondiali, fa si che questi processi siano altamente complessi e difficili da studiare, oltre che altamente imprevedibili.

Tipi di prodotti finanziari

• Abbiamo tre grandi categorie di prodotti finanziari:– Azioni: frazione del capitale sociale distribuito tra gli

azionisti. Un azionista è socio dell’impresa e partecipa agli utili;

– Obbligazioni: emissione di titoli da parte di un’impresa per far fronte ad una mancanza di liquidità. Il possessore sarà creditore nei confronti dell’azienda;

– Titoli di Stato: come delle obbligazioni, ma emesse dallo Stato per far fronte al debito pubblico;

Noi tratteremo le azioni.

Montecarlo in Economia e Finanza

Le scienze Economiche e Finanziare, che studiano questo tipo di processi, adoperano molti modelli per rendere più agevole lo studio di svariati problemi.

Il Metodo M.C. trova ampio utilizzo nel prezzamento di prodotti finanziari, nella previsione dei rendimenti di titoli e panieri azionari, la stima dei fattori di rischio e molto altro ancora.

Processi stocastici

• Un processo stocastico e una famiglia di variabili casuali Xt che dipendono dal tempo in modo continuo. Per semplicità tratteremo:– Processi Gaussiani: ogni “evento” ha pari probabilità

di verificarsi, quindi tutte le distribuzioni sono gaussiane ed Xt è distribuita normalmente per ogni t.

– Processi Markoviani: Il valore di Xt dipende unicamente da Xt-1

• Un processo che è sia gaussiano che markoviano si chiama di Wiener o browniano. Indicheremo questo genere di processo con W.

Processi di Wiener

I processi di Wiener godono delle proprietà:

1. W0=0 , con probabilità 1 (certezza);

2. Wt≈N(0,t) per ogni t>0. Quindi e distribuita come una normale avente media 0 e varianza t;

3. Tutti gli incrementi ΔW=Wt+Δt -Wt su intervalli di tempo che non si sovrappongono sono indipendenti;

4. Wt dipende in modo continuo da t.

Processi di Wiener

• Sia Δt>0 un incremento di tempo costante. Per valori di tempo ti=iΔt, i= 1, 2, … ogni corrispondente valore Wti può essere scritto come somma di incrementi ΔWk:

• Gli incrementi ΔWk sono indipendenti (processo markoviano) e distribuiti normalmente (processo gaussiano), con varianza V[ΔWk]=Δt, cioè ΔWk≈N(0, Δt);

• Operando un cambiamento di variabile

• Scriviamo quindi il processo di Wiener così:

;][1 1

)1(

i

k

i

ktktkkti WWWW

)1,0(NZt

WZ k

kk

tZW kk

Parametri di un titolo azionarioPer semplicità, trattiamo come modello un titolo azionario i cui

dividendi sono reinvestiti in azienda.

I parametri di mercato che influenzano il prezzo S(t) dell’azione, al tempo t sono:

• Il tasso di crescita dell’azione μ• La volatilità σ del prezzo S(t).

Il primo indica l’andamento generale del titolo nel corso di un dato periodo di tempo, il secondo da delle indicazioni sull’ampiezza delle fluttuazioni cui e soggetto il valore del titolo in un dato periodo di tempo.Entrambi si misurano, e si calcolano, su base annua.

Quindi μ=0.2 vuol dire che un’azione ha guadagnato il 20% nel corso di un anno, mentre σ=0.15 indica fluttuazioni del 15% (negative o positive che siano) rispetto il prezzo di riferimento.

Questi due parametri “governano” quindi il comportamento complessivo del titolo azionario, il tasso di crescita ci da informazioni generali sul comportamento del titolo, la volatilità indica quanto il titolo e soggetto a perturbazioni da parte del suo mercato di riferimento o in seguito ad un qualche avvenimento.

Ovviamente nel mercato reale μ e σ sono funzioni del tempo, e oggetto di processi stocastici.

Supporremo che questi due parametri rimangano costanti nel tempo.

Parametri di un titolo azionario

Funzione prezzo• Supponiamo che la volatilità del titolo sia nulla.

Vogliamo trovare una legge che descriva come cambia il valore di un’azione, a partire da un tempo iniziale t0=0 fino ad un tempo finale T.Scriviamo la variazione di prezzo in termini di tasso di crescita ed intervallo di tempo dS = μSdt Quindi la funzione prezzo sarà:

S(t) = S(t0)+dS;Notiamo che per un periodo T, S(T) = S(t0) + μS;

• Consideriamo la volatilità del titolo, che supponiamo essere del tipo di Wiener, da cui segue

dS = μSdt + σSdW con dW = r √(dt)dove r è un valore estratto dalla distribuzione normale standardizzata, cioè con valori in [-1,1].

Esempio utilizzatoConsideriamo la società Example S.p.A. che reinveste ogni eventuale utile senza elargire dividendi ai soci.

Il titolo presenta una volatilità elevata, σ=0.3, ma nel complesso ha dimostrato di avere un tasso di guadagno annuo affidabile del 15%, μ=0.15. Supponiamo di aver acquistato azioni al valore nominale di 100€.

Quanto sarà cambiato il valore del titolo tra una settimana?

Ricordando che assumiamo come unità temporale l’anno, otteniamo che dt=7/365 ≈ 0.0192.Quindi applicando l’equazione precedente troviamo che

dS=μSdt+σSdW ≈ 0.288 + 4.157 * r

L’incremento di prezzo si ottiene da una deviazione standard di media E(dS)= 0.288 e deviazione standard, o scarto tipo, 4.157 (la radice quadrata della Varianza Var(dS)).

Valutazioni• Valutiamo la funzione k=100 volte con sequenze

casuali diverse

Valutazione annuale

Se volessimo stimare il prezzo assunto dall’azione tra un anno? Potremmo porre dt=1, oppure ripetere iterativamente il calcolo precedente 52 volte.

Ovviamente nessun metodo (analitico, numerico o di altro tipo) potrà predire con certezza il verificarsi di un dato evento in un processo stocastico. Noi tuttavia abbiamo fatto forti assunzioni che avranno il loro peso.

Valutazione annuale

;1 trStSSS iiii

Conclusioni sull’esempio

• L’esempio è molto banale e non può essere utilizzato per la stima di un titolo reale, soprattutto in questa congiuntura economica;

• Dovremmo assumere come processi stocastici anche gli indici μ e σ, in modo continuo al variare del tempo.

• Inoltre dovremmo prendere in esame altri fattori di natura aleatoria come la variazione dei tassi di interesse, la variazione dei cambi tra valute estere, le oscillazioni dei prezzi del petrolio. Tutti fattori che giocano un ruolo non sempre trascurabile sui processi che regolano i mercati.

Conclusioni sull’esempio

• Troppe variabili sono complesse da gestire, alcune sono anche incontrollabili (uragani, terremoti);

• Avere un metodo di stima, anche se semplificato può comunque aiutare nella scelta dell’acquisto di un titolo;

Conclusioni• Il metodo MC non è conveniente per le stime su problemi di

dimensioni limitate;

• Quando le dimensioni del problema aumentano, una soluzione analitica o metodo di soluzione iterativo diventano progressivamente più complessi, se non addirittura intrattabili. In questi casi i metodi MC si rivelano un’utilissima “ultima spiaggia”;

• Possono essere utilizzati per confermare l’esistenza di un dato o prevedere l’esito di un esperimento, ma dopo la loro applicazione è utile trovare un modello matematico analitico con cui risolvere il problema

Grazie per l’attenzione