Il metodo middle square ha come obbiettivo quello di generare numeri casuali. Questo metodo per generare un numero casuale di N cifre richiede che si scelga un numero ad arbitrio di N cifre che esso venga elevato al quadrato e infine che si prendano le N cifre centrali del numero elevato al quadrato.
Quindi l’algoritmo si struttura in tre steps:
Questo metodo genera effettivamente un numero casuale però presenta alcuni difetti o opportune precisazioni sulla scelta del numero iniziale: la scelta del seme risulta decisiva e questo metodo presenta alcuni problemi quando si scelgono numeri con uguali cifre come ad esempio 33 o 66 inoltre quando si presenta uno 0 o uno 00 e via dicendo non ci riesce più a generare valori quindi nella scelta del seme bisogna porre attenzione a non scegliere un numero il cui quadrato presenti un zero nei valori centrali
I metodi congruenziali lineari e misti sono metodi per generare numeri casuali che si basano sull’idea che il resto di una divisione si possa considerare come casuale.
\[ y = x \mod m \] Lo scopo di questi metodi è quello di creare una sequenza di numeri casuali attraverso un algoritmo che sommi, sottragga, moltiplichi o divida da un numero valori per poi calcolare il resto della divisione: \[ x_1 = (a * x_0 + b) \mod m \\ x_2 = (a * x_1 + b) \mod m \\ ... \\ x_n = (a * x_{n-1} + b) \mod m \] Occcorre però fare delle opportune considerazioni sulla scelta dei coefficenti: - occorre che m sia un numero primo molto grande - occorre che c e m siano coprimi - a dovrebbe essere nella forma \(2^r + 1 \space \space \space t.c. \space \space \space r \geq 2\)
La generazione di numeri casuali non è altro che la generazione di valori da una uniforme in quanto in questa distribuzione tutti i valori sono indipendenti e hanno la stessa probabilità; quindi per testare un algoritmo di generazione di numeri casuali si può fare un test empirico per verificare l’uniformità e un test del chi-quadro per verificare l’indipendenza
Per generare una realizzazione da una v.c. \(Y\) con funzione di ripartizione \(F_y(y)\) è necessario individuare una trasformazione di una o più v.c. \(U(0,1)\) indipendenti t.c. valga la relazione \(y=f(U)\), per trovare questa trasformazione calcoliamo la funzione di ripartizione inversa di \(Y\) per \(U\):
\[F_y(y) = u \rightarrow Y = F_y^{-1}(u)\]
Alcune v.c. possono essere costruite, a partire dalla loro definizione, come funzione di v.c. di distribuzione più “semplici”, si pensi ad esempio alla chi-quadro che è il quadrato di una normale.
L’algoritmo di accettazione-rifiuto fu realizzato nel 1951 da Von Neuman e afferma che, quando si vuole generare valori da una v.c. \(Y\) con funzione di densità “complicata” e si supponga di poter generare solo da una v.c. \(X\) “semplice” con densità \(g_x(x)\) e da una v.c. \(U(0,1)\) e t.c. il supporto di \(Y\) sia contenuto in quello di \(g_x( . )\) allora si possono generare da \(g_x(x)\) valori casuali di \(Y\) se e solo se, per \(n\gg0\), gli \(n\) valori generati da una \(U(0,1)\) moltiplicati per un coefficiente \(b\) e per gli \(n\) valori generati dalla v.c. \(X\) attraverso \(g_x(x)\) sono minori o uguali degli \(n\) valori generati dalla v.c. \(X\) inseriti all’interno della funzione di densità di \(Y\), ossia:
\(n \gg 0\)
\(i = 1, ..., n\)
\(u_i \sim U(0,1)\)
\(x_i \sim g_x(x)\)
\[u_i \space \space b \space \space x_i \leq f_y(x_i)\]
dove \(b\) corrisponde al massimo \(y\) del rapporto tra \(f_y(y)\) e \(g_x(y)\) ossia:
\[ b= \max_{y}{\frac{f_y(y)}{g_x(y)}} \]
Questo metodo sfrutta il teorema centrale del limite per generare da una uniforme \(U(0,1)\) valori di una normale:
\(u_i \sim U(0,1)\) con \(i = 1, ..., n\)
\[ \frac{\frac{\sum u_i}{n}- E[U]}{\frac{Var(U)}{\sqrt n}} \sim N(0,1)\]
In particolare ipotizzando: \(n=12\) generazioni da una \(U(0,1)\) risulta:
\[ E[U]=\frac{1}{2} \\ Var(U)=\frac{1}{12} \\ quindi: \\ \rightarrow \sum u_i - 6 \sim N(0,1) \]
Metodo per generare da una normale bivariata a componenti indipendenti, questo algoritmo si struttura in 4 fasi:
Dove \(Z_1, Z_2\) sono due \(N(0,1)\) indipendenti.
Metodo per generare da una normale bivariata a componenti indipendenti, questo algoritmo si struttura in 4 fasi:
Dove \(Z_1, Z_2\) sono due \(N(0,1)\) indipendenti.