Statistica computazionale - cash-cow.it · entropia esterna utile per certe applicazioni dove è...
Transcript of Statistica computazionale - cash-cow.it · entropia esterna utile per certe applicazioni dove è...
Generatori di numeri casuali
Alberto Lusoliwww.cash-cow.it
Distribuito sotto licenza Creative Common Share Alike Attribution
Statistica computazionale
“La generazione dei numeri casuali ètroppo importante per essere lasciata alcaso”
Robert R. Coveyou
Concetti fondamentali
I campi di studio della probabilità e dellastatistica si fondano sul concetto dispazio delle probabilità e variabilecasuale.Quando questi concetti vengonoimplementati in elaboratori nasce ilproblema di simulare variabili casualimediante algoritmi deterministici.
Definizione intuitiva
Un algoritmo RNG (Random NumberGenerator) è un software il cui output èdifficilmente distinguibile dalcomportamento di una variabile"veramente casuale".
Definizione intuitiva
Ovvero, osservando una serie di outputforniti dall'algoritmo non si dovrebberoavere informazioni circa il successivovalore generato.
Quando si utilizzano numerirandom?
Nei linguaggi di programmazione sonopresenti funzioni per la generazione di numericasuali. Tra quelli che abbiamo affrontato inaltri corsi citiamo:
Matlabrand
ANSI Crand()
Processi fisici
Variabili casuali possono scaturireanche dall’osservazione di processifisici come il tempo di decadimentoatomico o l'analisi del thermal noise(disturbo termico) nei semiconduttori.
Processi fisici
I RNG basati su processi fisici hannomolti svantaggi rispetto alla lorocontroparte software: sono difficili darealizzare, sono costosi, lenti e nonsono in grado di riprodurre la stessasequenza di output a partire dalmedesimo stato iniziale.
Processi fisici
Questi metodi sono spesso utilizzatiinsieme a algoritmi RNG per laselezione del seme iniziale (vedi dopo).Rappresentano infatti una fonte dientropia esterna utile per certeapplicazioni dove è frequente ilreseeding, ovvero la reinizializzazionedella sequenza di output (criptologia emacchine da gioco).
Algoritmi RNG e numeripseudo casuali
Centro della nostra analisi sono i software per lagenerazione di numeri casuali (abbreviati in RNG)Si tratta di algoritmi deterministici in grado digenerare un output avente le stesse proprietàstatistiche di una sequenza di numeri generata daun processo casuale.
Numeri Pseudo casuali
L’output fornito, come accennato inprecedenza, imita ma non èpropriamente una variabile casuale. Perquesto motivo è più corretto parlare dinumeri pseudo-casuali (PRNG,dall'inglese pseudo-random numbersgenerator).
Caratteristiche dei numeripseudo-casuali
Una sequenza di numeri pseudo-casuali deve soddisfare, al minimo, leseguenti proprietà statistiche:
• Distribuzione• Indipendenza
Distribuzione
Distribuzione degli output secondo unafunzione di distribuzione predefinita f(x):di solito si richiede una distribuzioneuniforme su un intervallo specificato(equidistribuzione)
Indipendenza
Indipendenza tra elementi successividella sequenza, ovvero tra 2 outputsuccessivi
Esempio
La sequenza1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Non si può definire pseudo-casualeE’ certamente equidistribuita sull'intervallo[1,10], ma le coppie di elementi successivinon sono uniformemente distribuitesull'insieme di tutte le possibili coppie dinumeri da 1 a 10, ma sono tutte della forma(n,n+1). Non è quindi soddisfatto il criterio diindipendenza
Provare la casualità
Il problema principale dei RNG è chel'output fornito non è propriamente unavariabile casuale ma unaapprossimazione di una variabilecasuale con distribuzione uniforme edindipendente
Provare la casualità
Se l’output è, come avviene spesso,una sequenza di bit con valori 0 o 1,ogni bit deve assumere con ugualeprobabilità 0 o 1 e tutti i bit devonoessere tra di loro indipendenti.
Provare la casualità
Questo comportamento desiderato nonpuò essere provato a ex-ante ma deveessere testato ex-post mediante teststatistici che provino che la variabile inosservazione abbia realmente ilcomportamento casuale desiderato.
RNG in formula
Indipendentemente dal funzionamentoparticolare di ciascun algoritmo, tutti gliRNG possono essere descritti comecomposti da:
!
(",µ, f ,U,g)
RNG in formula
!
" :
!
U :
!
g :
!
µ :
!
f :
Insieme finito di stati (spazio degli stati)
Distribuzione di probabilità utilizzata per selezionaredall’insieme lo stato iniziale (detto Seme)
Funzione di transizione che, partendo da determina . In formula:
Spazio degli output, solitamente comprende i valoritra 0 e 1Funzione di output. Dato uno stato
Gli output sono i Numeri casuali prodotti dal RNG
!
"
!
s0
!
si
!
si+1
!
si+1 = f (si)
!
si
!
ui = g(si)"U
!
u0,u1,u2...
Periodo massimo di un RNG
Dato che l’insieme degli stati è finito,per qualsiasi seme (stato iniziale)esisterà un valore tale per cui
!
"
!
s1
!
l
!
si+ l = s
i
Periodo massimo di un RNG
Dato che le funzioni di transizione e dioutput e sono deterministiche,allora anche per l’output vale la formula:
!
ui+ l = u
i!
f
!
g
…a parole
Significa che, partendo da un qualsiasi statoiniziale, dopo un certo numero di iterazioni, ilsistema torna allo stato iniziale, ovvero alseme.Quindi, tutti gli algoritmi RNG generanosequenze finite di numeri casuali e dopo unnumero di iterazioni tornano allo statoiniziale.
!
l
!
l
Proprietà del periodo
Il valore di l più piccolo per cui èavviene il ritorno allo stato iniziale èchiamato periodo del RNG ed èindicato con . è minore o uguale a , ovveroall'insieme finito di stati (spazio deglistati).!
"
!
"
!
"
Proprietà del periodo
Se gli stati sono rappresentati in un computerda una stringa di k bit, allora:
Buoni RNG hanno valore di tendente a . dipende anche dal seme.RNG efficienti hanno uguale per tutti ipossibili stati iniziali.!
" # 2k
!
"
!
"
!
"
!
"
Altre caratteristiche dei RNG
Criteri di qualità utilizzati per valutare laqualità di un RNG sono:
• Lunghezza del periodo: periodi lunghi, prossimi a , assicurano che il sistema non entri in cicli prevedibili.
!
"
Altre caratteristiche dei RNG
• Efficienza: buoni RNG devono utilizzare unaquantità ridotta di risorse (memoria)
• Ripetibilità: partendo dallo stesso seme,devono essere in grado di riprodurre la stessasequenza di numeri casuali
• Portabilità: devono essere indipendenti dalcontesto hardware software
Alcuni esempi di RNG
Analizziamo ora 2 famiglie di RNG, trale più utilizzate.
• Generatori lineari congruenziali• Mersenne Twister
Generatori lineari congruenziali
I generatori di numeri casuali di tipolineare congruenziale sono tra i piùsemplici e più diffusi.La formula base per questa famiglia diRNG è del tipo:
!
si+1 = a " s
i+ c(modm)
…nel dettaglio
!
si+1
!
m
!
a
!
c
: stato al tempo
!
i+1
!
si
: stato al tempo
!
i
: parametro Moltiplicatore
: parametro Incremento. Se , allora l’RNG è detto Moltiplicativo
!
c = 0
: numero di stati possibili
!
si+1 = a " s
i+ c(modm)
Esempio
Poniamo i valori dei parametri pari a:
!
a = 3
!
c = 6
!
m = 5
!
s0
=1
!
"
!
!
si+1 = 3 " s
i+ 6(mod5)
Esempio
!
s0
=1
Esempio
!
s1 = 3 "1+ 6(mod5) = 4
!
s0
=1
Esempio
!
s1 = 3 "1+ 6(mod5) = 4
!
s0
=1
!
s2 = 3 " 4 + 6(mod5) = 3
Esempio
!
s1 = 3 "1+ 6(mod5) = 4
!
s0
=1
!
s2 = 3 " 4 + 6(mod5) = 3
!
s3 = 3 " 3+ 6(mod5) = 0
Esempio
!
s1 = 3 "1+ 6(mod5) = 4
!
s0
=1
!
s2 = 3 " 4 + 6(mod5) = 3
!
s3 = 3 " 3+ 6(mod5) = 0
!
s4 = 3 " 0 + 6(mod5) =1
Esempio
!
s1 = 3 "1+ 6(mod5) = 4
!
s0
=1
!
s2 = 3 " 4 + 6(mod5) = 3
!
s3 = 3 " 3+ 6(mod5) = 0
!
s4 = 3 " 0 + 6(mod5) =1
!
s5 = 3 "1+ 6(mod5) = 4
Esempio
!
s1 = 3 "1+ 6(mod5) = 4
!
s0
=1
!
s2 = 3 " 4 + 6(mod5) = 3
!
s3 = 3 " 3+ 6(mod5) = 0
!
s4 = 3 " 0 + 6(mod5) =1
!
s5 = 3 "1+ 6(mod5) = 4
Periodo di lunghezza 4
!
4 < 5
" < m
" < #
in simboli:
riprendendo la formula generale:
Pro e contro dei RNG linearicongruenziali
Pro• Semplici da implementare• Velocità di esecuzione
Contro• Sequenza periodica di periodo al più pari a m• Ogni valore di è completamente
determinato dai 4 parametri• Correlazione tra chiamate successive del
generatore!
"
!
a,c,m,s0
Cosa si intende per correlazione?
Se k numeri consecutivi della sequenzavengono utilizzati come coordinate di punti inuno spazio k-dimensionale, se i numerifossero assolutamente non-correlati, i puntitenderebbero a coprire tutto lo spazio.In realtà i punti vanno a cadere in “piani” (k-1)dimensionali, il cui numero è al massimo:
!
m
1
k
Correlazione
Consideriamo ad esempio k=2. Utilizziamoogni coppia di numeri pseudo-casualigenerati da un RNG come coordinate di puntiall’interno di un piano cartesiano.Un buon RNG dovrebbe dar luogo ad ungrafico dove i punti sono dispostiuniformemente nello spazio (figura di sinistra)
Correlazione
Mersenne Twister
RNG in grado di generare numeri casuali diqualità elevata ed in tempi ridotti.
Sviluppato nel 1997 da Makoto Matsumoto eTakuji Nishimura.
Mersenne Twister
Tra i vantaggi di questo RNG vi sono:
• Periodo lungo: pari a• Correlazione: Correlazione trascurabile tra
valori successivi della sequenza• Velocità: La velocità di generazione è
paragonabile a quella della funzione Rand()dell’ ANSI C
• Efficienza: Utilizzo delle risorse ridotto
!
219937
Valutare la qualità di un RNG
Come accennato in precedenza, pervalutare la qualità di un RNG ènecessario studiare le proprietàstatistiche delle sequenze generate.
Test di uniformità o del
Test in grado di valutare l’uniformitàdella distribuzione di una sequenza divariabile discrete.
!
" 2
Test di uniformità o del
!
" 2
!
k : numero di eventi possibili
!
E1,E
2,...,E
k : evento 1, evento 2, …, evento k
!
p1, p
2,..., pk : probabilità evento 1, probabilità evento 2, …,
probabilità evento k
!
n : numero di esperimenti
!
y1,y
2,...,yk : numero di volte che si realizza l’evento 1,
numero di volte che si realizza l’evento 2, , …, numero di volte che si realizza l’evento k
Test di uniformità o del
!
" 2
Quindi, la sommatoria di tutti gli eventi che si realizzano sarà pari al numero di esperimenti:
!
yi = ni=1
k
"
Introduciamo la variabile V, definita come:
!
V =i=1
k
"(yi # npi)
2
npi
Per verificare l’uniformità di un generatore nelfornire numeri random distribuitiuniformemente in [0,1]:
• Tra 0 e 1, si creano k-sottointervalli diampiezza
• Si genera un gran numero di istanze dellav.a. uniforme e si conta per ogni intervallo ilnumero di istanze che sono caduteall’interno dell’intervallo
Test di uniformità o del
!
" 2
!
yi!
1k
Poichè il generatore è uniforme si ha
!
pi = 1k
Si calcola qundi il valore di V utilizzando laformula descritta in precedenza:
Se il generatore è efficace, la variabile V risulta avere distribuzione con
gradi di libertà.
!
" 2
!
k "1
Test di uniformità o del
!
" 2
!
V =i=1
k
"(yi # npi)
2
npi
Test di uniformità o del
!
" 2
Il test è superato se, fissato un certo valore critico
V non risulta maggiore a tale valoreSolitamente si pone
!
"1#$
2
!
" = 0.05
Riferimenti web e bibliografia
• Computational statistic• Marsenne Twister Home page
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
• http://www.cs.unibo.it/~donat/random1.pdf