Simulazione di esperimenti aleatori

Note

Dato un evento e un esperimento aleatorio è possibile ripetere l’esperimento aleatorio tante volte (in maniera indipendente), e per ogni prova registrare una variabile aleatoria :

Con indipendenti e identicamente distribuite. Costruendo la loro media campionaria :

Per la legge debole dei grandi numeri, la media campionaria è una buona stima di :

Controllo dell'errore di stima

In modo analogo al problema del sondaggista, abbiamo un livello fiduciario dove vogliamo cadere con grande probabilità:

Inoltre vogliamo avere un errore quadratico medio di stima piccolo:

Calcoliamo quindi l’errore relativo di stima:

E quindi:

Per , un piccolo è sufficiente, tuttavia per deve essere molto grande, quindi stimare la probabilità di eventi rari è dispendioso.

Generatore di numeri casuali

Note

Per simulare è necessario generare numeri casuali. Per farlo utilizziamo dei sistemi caotici, cioè sistemi che data una condizione iniziale (detta seed), ci fornisce in uscita una sequenza di bit pseudo-casuali.

Generazione di variabili aleatorie uniformi

Avendo a disposizione una sequenza pseudo-casuale di bit e , è possibile generare numeri casuali .

È possibile generare realizzazioni da con data. Per farlo processiamo l’output del generatore di variabili aleatorie uniformi con una funzione .

Sia la funzione monotona crescente, allora la funzione:

Siccome è non decrescente, possiamo anche dire che:

Metodo di acceptance-rejection

Note

Supponiamo di voler generare campioni , scegliamo un valore tale che:

Scegliamo casualmente dei punti nella regione rettangolare , tenendo solo i punti che cadono sotto (acceptance).

Algoritmo di acceptance-rejection

1. Genero
2. Genero , con
3. Accetto e pongo se , altrimenti torno ad .

Si trova un valore tale che:

1. Si genera un e con
2. Accettiamo e poniamo se , altrimenti torno ad .

È provabile che mediamente si genera campione valido di ogni cicli, di conseguenza l’efficienza dell’algoritmo di acceptance-rejection è .

Algoritmo di Box-Muller

Note

L’algoritmo di Box-Muller è un algoritmo di generazione casuale con efficienza . Consideriamo di generare campioni da un vettore di variabili aleatorie Gaussiane standard indipendenti:

Definiamo:

Introduciamo una matrice di covarianza :

Per le variabili aleatorie Gaussiane standard perché le sono indipendenti e identicamente distribuite.

Per generare un campione:

1. Genero le per in maniera indipendente.
2. Pongo , e si determinano e in modo che e , da cui ricaviamo e .

La fattorizzazione è detta fattorizzazione di Cholesky:

Campionare da distribuzioni discrete

Note

Per campionare da distribuzioni discrete si può riadattare il metodo della cumulata inversa:

Quindi come algoritmo possiamo seguire:

1. Genero
2. Assegno come indicato sopra