Appunti di Statistica computazionale

|Z|

continua non negativa ha funzione di densità

X = r 2

2 x

exp .

f (x) = 2f (x) = −

X Z π 2

Si sceglie exp{−x} e si applica l’algoritmo AR. Si determina quindi tale

g(x) = b

che f (x)

X

sup .

b = g(x)

x∈R

Si dimostra che ha un’espressione algebrica semplice:

b r 2e .

b = π ∼

L’algoritmo ad hoc che permette di generare una determinazione di Y

N(µ, è il seguente:

σ)

si genera indipendentemente , e da uniformi in

u u u (0, 1);

1. 1 2 3

si genera da con l’algoritmo ITM sfruttando ;

x Exp(1) u

2. 1

si determina e si controlla se ⩽

b u bg(x) f (x).

3. 2 X |Z|,

se soddisfa la condizione, si accetta come determinazione da

x x X =

4. altrimenti si ripetono i passi;

se si cambia il segno di ottenendo una determinazione di

u < 0.5, x Z;

5. 3

si ottiene determinazione di calcolando

y, Y, y = σz + µ.

6.

3.3. METODI AD HOC PER LA GENERAZIONE DI CAMPIONI DALLA NORMALE GENERALE2

3.3.2 Teorema centrale del limite

Sia una variabile aleatoria con e

(centrale del limite). E(X)

3.1

Teorema X = µ

2 Dato un campione casuale estratto da vale che

var(X) = σ < +∞. X , X , . . . , X X

n

1 2

P n X − nµ d

i N(0,

i=1 √ −

→ 1)

σ n

→

con n +∞.

∼

Se e è un campione casuale estratto da si ha

X UC(0, 1) X , X , . . . , X X,

n

1 2 P

che n n

X −

i d

i=1 N(0,

2 −

→ 1)

n

p 12

P P

n n

n n

→

con in quanto E e var .

)

( )

(

X =

n +∞, X =

i i

i=1 i=1

2 12

L’algoritmo per generare un campione casuale dalla normale standard,

fissato “grande”, è il seguente:

n ∼

generazione di determinazioni indipendenti da

n x , x , . . . , x X

1. n

1 2

UC(0, 1);

la determinazione dalla normale standard è

2. P n n

x −

i

i=1 2 .

y = n

p 12

Quest’algoritmo ha diversi limiti:

• sfrutta un’approssimazione asintotica;

• ha un costo computazionale elevato; √ √ i

h .

• le osservazione del campione generato sono limitate all’intervallo 3n, 3n

−

3.3.3 Metodo di Box e Muller

R.

∈

Si considera il punto Sfruttando le coordinate polari vale che

(x, y) 

 cos

x = r θ

 sin

y = r θ

∈

con e Si considera il vettore aleatorio con distribuzione

r > 0 θ [0, 2π). (X, Y) ∼ N

normale bivariata con componenti indipendenti, ovvero Si

(X, Y) (0, I ).

2 2

3. GENERAZIONE DI NUMERI PSEUDO-CASUALI DA QUALSIASI DISTRIBUZIO

22CAPITOLO

considera ora la trasformazione in coordinate polari:



 cos

X = R Θ

 sin

Y = R Θ

∈

con e Il determinante della matrice jacobiana associata alla

R > 0 Θ [0, 2π).

trasfromazione in coordinate polari è

" #

cos sin

θ −r θ 2 2

det det cos sin

J = = r θ − r θ = r > 0.

sin cos

θ r θ

Allora la funzione di densità congiunta di è

(R, Θ)

cos sin

f (r, θ) = f (r θ, r θ)r =

(R,Θ) (X,Y) 2

r

1 exp .

−

r

= 2π 2

|{z} | {z }

=f =f

Θ R

La funzione di densità congiunta di è il prodotto delle marginali. Per cui,

(R, Θ) ∼

le variabile aleatorie e sono indipendenti. Si nota che Si nota

R Θ Θ UC(0, 2π).

∼ 12 12

2 2 2 22

≡ ≡

inoltre che in quanto somma

T = R = X + Y χ Gamma 1, Exp

di normali standard indipendenti. L’algoritmo di Box e Muller è il seguente:

generazione indipendente di e dalla distribuzione uniforme in

u u (0, 1);

1. 1 2

p p

si pone log cos(2πu e log sin(2πu

x = −2 u ) y = −2 u ).

2. 1 2 1 2

∼ 1 p

Si nota che log è una generazione da e quindi log è

−2 u T Exp −2 u

1 1

2 ∼

generazione da mentre, invece, è una generazione da

R, 2πu Θ UC(0, 2π).

2

Questo algoritmo risulta avere un elevato costo computazionale a causa del

calcolo delle funzioni e

cos sin.

3.3.4 Marsaglia (Polar Rejection Method)

L’algoritmo di Marsaglia migliora il metodo di Box e Muller evitando il calcolo

delle funzioni e adottando un vincolo di accettazione.

cos sin

L’algoritmo di Marsaglia è il seguente:

generazione indipendente di e dalla distribuzione uniforme in

u u (0, 1);

1. 1 2

3.3. METODI AD HOC PER LA GENERAZIONE DI CAMPIONI DALLA NORMALE GENERALE2

generazione di determinazioni dall’uniforme in (0, 2π):

2. e

v = 2πu − 1 v = 2πu − 1;

1 1 2 2

21 22

se si accetta il punto altrimenti si ripetono i passi;

⩽

s = v + v 1, (v , v ),

3. 1 2

calcolo di

4. v v

1 2

p p

√ √

log e log .

z = −2 s z = −2 s

1 2

s s

Si considerano i punti cos sin Dopo aver considerato il

(v , v ) = (r θ, r θ).

1 2

22

21 il vettore aleatorio è distribuito uniformemente nel

vincolo ⩽ 1, (V , V )

+ v

v 1 2

cerchio unitario, quindi 1 .

f (v , v ) =

1 2

(V ,V )

1 2 π

Applicando il teorema del diffeomorfismo per trovare la densità di (R, Θ) =

v

2 2 2

arctan si trova

(V + V , ),

1 2 v 1 1

1 .

cos sin r = 2r

f (r, θ) = f (r θ, r θ)r = |{z}

(R,Θ) (V ,V )

1 2 π 2π

|{z} =f R

=f

Θ

La funzione di densità congiunta di è il prodotto delle marginali. Per cui,

(R, Θ) ∼

le variabile aleatorie e sono indipendenti. Si nota che Invece,

R Θ Θ UC(0, 2π).

∼

2 2 2 infatti

S = R = V + V UC(0, 1),

1 2 Z √ √

s

√ s

h i

2 2

⩽ ⩽ ⩽ s) = 2rdr = r = s.

P(S s) = P(R s) = P(R 0

0

v v v

v

1 1 2

2

Ricordando quindi che cos e sin , dal metodo di Box e

√ √

θ = = θ = =

r r

s s

Muller, si trova che v v

1 2

p p p p

√ √

log cos log e log sin log .

−2 s θ = −2 s z = −2 s θ = −2 s

z =

1 2

s s

La probabilità di accettazione di un punto è

(v , v )

1 2

Area del cerchio unitario π .

=

Area del quadrato di lato 4

2

Ci si aspetta quindi che circa il dei punti venga respinto. Nonostante questo

21%

si osserva che il metodo di Marsaglia risulta essere più efficiente del metodo di

Box e Muller. 3. GENERAZIONE DI NUMERI PSEUDO-CASUALI DA QUALSIASI DISTRIBUZIO

24CAPITOLO

3.3.5 Generazione dalla normale multivariata con componenti

correlate

Per generare da una normale multivariata di ordine si generano campioni

p, p

casuali da normali standard indipendenti. Si suppone di voler generare un

∼ N

campione casuale da con vettore delle medie e matrice di

Y µ

(µ, Σ) Σ

p

varianze/covarianze. Sfruttando la decomposizione di Cholesky di ovvero

Σ,

′

Σ = AA ,

ha che ∼ N

µ

Y = + AZ (µ, Σ)

p

∼ N

dove Z (0, I ).

p p √ |det

Si dimostra che det Σ = A|.

L’algoritmo per generare dalla normale multivariata con componenti corre-

late è il seguente:

generazione di determinazioni da normali standard indipendenti;

z

p

1. calcolo della trasformazione di Cholesky;

2. calcolo della trasformazione y µ

= + Az.

3.

3.4 Rapporto di uniformi

Si studia la relazione tra due uniformi e e il loro rapporto. Sia un

U V (U, V)

vettore aleatorio uniformemente distribuito in r v

⩽ ⩽

C = (u, v) : 0 u h

h u

con funzione non negativa, integrabile e con integrale finito. Allora la variabile

h V

aleatoria ha funzione di densità proporzionale a Il vettore ha

X = h. (U, V)

U

funzione di densità 1 .

f (u, v) =

(U,V) Area di C h

3.4. RAPPORTO DI UNIFORMI 25

Siccome ZZ

Area di dudv =

C =

h C h

Z Z q v

( )

h u

= dudv =

R 0

√

Z Z h(x)

= w dxdw =

R 0 √

Z Z

h(x)

2

w 1

= dx = h(x)dx,

2 2

R R

0

v

ponendo , si ha che

(w, x) = u, u 2w

R .

f (w, x) = f (w, wx)w =

(W,X) (U,V) h(x)dx

R

Marginalizzando rispetto a si ottiene la funzione di densità di

W X:

√

Z h(x)

f (x) = f (w, x)dw =

X (W,X)

0

√

Z h(x) 2w

R

= dw =

h(y)dy

R

0 √

Z h(x)

2

R

= w dw =

h(y)dy

R 0 √

h(x)

2

2 h(x)

w

R R .

= dw =

2

h(y)dy h(y)dy

R R

0 v

Se si riesce a generare uniformemente dentro , allora è una determi-

C x =

h u

h(x)

R

nazione da con funzione di densità . Ciò è quasi sempre difficile. Si

X h(y)dy

R

genera quindi da uno spazio più semplice che contiene . Generato un punto,

C h

q v

si verifica che appartenga a , ovvero che .

⩽ ⩽

C 0 u h

h u

2

Siano e due funzioni limitate in , allora la regione maggiorante

h(x) x h(x) C h

è {(u, } ×

⩽ ⩽ ⩽ ⩽

v) : 0 u a, b v b = [0, a] [b , b ]

− + − +

dove p p p

sup e

a = h(x), b = inf x h(x) b = sup x h(x).

− +

x⩽0 x⩾0

x∈R

3. GENERAZIONE DI NUMERI PSEUDO-CASUALI DA QUALSIASI DISTRIBUZIO

26CAPITOLO

L’algoritmo del rapporto di uniformi è il seguente:

generazione di e da uniformi in indipendenti;

u u (0, 1)

1. 1 2

calcolo di

2. e ;

v = au v = b + (b − b )u

− + −

1 1 2 2

v 21

2

si considera altrimenti si

come generazione da se ⩽

x = h(x),

X v

3. v 1

ripetono i passi.

4

Capitolo

L’integrazione Monte Carlo

Rientrano nel metodo Monte Carlo (MC) tutte quelle tecniche che risolvono

problemi matematici deterministici attraverso la generazione di determinazioni

da variabili aleatorie artificiali. Scegliendo di utilizzare queste tecniche si accetta

l’introduzione di un er