Numeri pseudocasuali

Numeri pseudocasuali

“Numeri casuali non devono essere generati con un metodo scelto a caso” D.Knuth

• Il periodo deve essere il pi` u lungo possibile;

• la distribuzione deve essere uniforme in [0, 1]

p(x)=costante in [0, 1];

• le correlazioni devono essere trascurabili

D

x

· x

−

x

hx

i = 0;

• distribuzioni uniformi:

– metodi lineari congruenti;

– metodi Fibonacci lagged;

– metodi non lineari, etc

• distribuzioni non uniformi:

– distribuzione gaussiana e metodo di Box- M¨ uller

– distribuzione qualsiasi;

Metodi lineari congruenti (LCM)

• x

= (a · x

+ b) mod m;

• di solito b = 0;

• a ` e primo;

• m ` e primo, oppure m = 2

Problema

overflow per moltiplicazione per a.

Soluzione

m = a · q + r con r < q scrivo x

= z · q + w allora

a · x

= a · (z · q + w) = a · q · z + a · w = (a · q + r) · z − r · z + a · w

a · x

= m · z − r · z + a · w

con r · z < q · z < x

< m e a · w < a · q < m

Quindi a · w − r · z ` e minore di m ed il risulato ` e a · x

mod m = a · w − r · z(+m) =

a · (x

mod m) − r · (x

/q) (+m) Esempio:

a = 16807 m = 2

= 2147483648

Metodi Fibonacci lagged

x

=

XN q=0

a

x

• Simili alla successione di Fibonacci, ma con pi` u termini; di solito solo un paio di c

sono diversi da zero;

• occorre una certa attenzione alle condizioni iniziali; si pu` o provare a usare LCM come

”starter” per i primi termini;

• hanno periodo molto lungo e scarse corre- lazioni;

• pi` u successioni indipendenti con la stessa

regola;

Esempio: r250

• x

=

a

x

• periodo N ≈ 2

• a

= 0 escluso che per q = 103, 250 per cui a

= 1

• quindi x

= x

+ x

• in realt` a si usa xor: x

= x

xor x

• memorizzo gli ultimi 250 termini in uno

stack circolare per non dover spostare ad

ogni passo un intero vettore

Metodo di Box-M¨ uller

Voglio una distribuzione gaussiana: se x

e x

sono distribuite uniformemente in (0, 1) definisco

y₁ = p

−2 ln x₁sin(2πx₂) y₂ = p

−2 ln x₁ cos(2πx₂)

Quindi x

= e

e p(y

) p(y

) dy

dy

= p(x

) p(x

) dx

dx

= dx

dx

p(y

) p(y

) ∂(y

, y

)

∂(x

, x

) = 1

∂(y₁, y₂)

∂(x₁, x₂) =

¯¯

¯¯

¯

−1 x1

√−2 ln x1 sin(2πx₂) 2π√

−2 ln x₁cos(2πx₂)

−1 x1

√−2 ln x1 cos(2πx₂) −2π√

−2 ln x₁ sin(2πx₂)

¯¯

¯¯

¯

∂(y

, y

)

∂(x

, x

) = 2π x

Percio‘ p(y₁) p(y₂) = x₁ = 1

2πe^{−(y12+y22)/2} p(y₁) = 1

√2πe^−y12/2 p(y₂) = 1

√2πe^−y22/2

Distribuzioni qualsiasi

Se voglio ottenere una distribuzione con pro- babilit` a p(x) arbitraria limitata superiormente.

• suppongo che mi interessi 0 ≤ x ≤ a

• suppongo che p(x) ≤ b ∀x in [0, a]

• scelgo un numero a caso x con distribuzione uniforme nel range [0, a]

• scelgo un secondo numero a caso y con y²[0, b]

• se y < p(x) accetto il numero, altrimenti

procedo con altri due numeri

Applicazioni

Integrazione con numeri pseudocasuali Data f (x) voglio calcolare

Z _b

a

f (x) dx

dove so che f (x) ` e compresa tra zero e f

.

• genero coppie di numeri che corrispondono a un punto nel rettangolo che ha lati tra a e b e tra zero e f

.

• calcolo la percentuale P di punti che cadono sotto la curva y = f (x)

• l’integrale vale P · (b − a) · f

Test di uniformit` a e correlazioni

0 0.5 1

x 0.0496

0.0498 0.05 0.0502 0.0504

frazione

0 0.2 0.4 0.6 0.8 1

x n

Problemi Volume di una sfera unitaria

• x

+ y

+ z

≤ 1;

• considero solo un ottante con x > 0, y >

0, z > 0;

• genero una terna di numeri casuali x, y e z;

• guardo se x

+ y

+ z

≤ 1, nel qual caso accetto la terna;

• ripeto per un gran numero di terne;

• alla fine divido le terne accettate per quelle totali;

• moltiplico per 8;

• nota: l’errore ` e O(1/ √ N ) Moto Browniano

• prendo x = y = 0 inizialmente;

• noto x al tempo t, al tempo successivo x

` e dato da x

= x + ²ξ

e y

= y + ²ξ

con

−1 ≤ ξ

≤ 1;

• dopo N passi verifico che x

+ y

∼ N ²

;

Teorema del limite centrale

• considero le somme ξ

. . . ξ

;

• guardo come ` e distribuita la media al vari- are di N ;

• per N grande devo trovare una distribuzione

gaussiana;