Numeri pseudo-casuali

Sono detti numeri pseudo-casuali (in inglese pseudo-random numbers) i numeri generati da un algoritmo deterministico che produce una sequenza con, approssimativamente, le stesse proprietà statistiche di una sequenza di numeri generata da un processo casuale. Tale algoritmo è detto generatore di numeri pseudo-casuali (PRNG, dall'inglese pseudo-random number generator).

Le sequenze di numeri pseudo-casuali vengono solitamente generate da un computer e utilizzate per algoritmi basati su processi casuali, come i metodi di tipo Monte Carlo o le applicazioni di crittografia. Quando invece occorrono sequenze di numeri realmente casuali, si utilizza un generatore hardware di numeri casuali.

Proprietà

Una sequenza di numeri pseudo-casuali deve soddisfare, al minimo, le seguenti proprietà statistiche:

• distribuzione degli elementi della sequenza secondo una funzione di densità di probabilità predefinita $f(x)$: di solito si richiede una distribuzione uniforme su un intervallo specificato (equidistribuzione), cioè $f(x)=1/(x_{max}-x_{min})$ nell'intervallo $[x_{min},x_{max}]$ e $f(x)=0$ fuori da tale intervallo.
• indipendenza tra elementi successivi della sequenza: se la funzione di distribuzione per un singolo elemento è f(x), la funzione di distribuzione per le coppie di elementi successivi deve essere $f(x,y)=f(x)\cdot f(y)$.

Ad esempio, la sequenza 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 non si può definire pseudo-casuale, in quanto soddisfa il requisito dell'equidistribuzione (sull'intervallo $[1,10]$), ma non quello dell'indipendenza: le coppie di elementi successivi non sono uniformemente distribuite sull'insieme di tutte le possibili coppie di numeri da 1 a 10, ma sono tutte della forma $(n,n+1)$ (quindi disegnandole su un grafico cartesiano si dispongono tutte sulla stessa retta). Una sequenza pseudo-casuale potrebbe invece essere ad esempio 3, 2, 10, 9, 6, 8, 1, 5, 4, 7: in questo caso le coppie di elementi successivi appaiono distribuirsi in modo abbastanza uniforme sull'insieme delle coppie di numeri da 1 a 10, anche se la lunghezza della sequenza è troppo breve per poterlo verificare accuratamente.

Alcune applicazioni necessitano di altre proprietà statistiche in aggiunta a queste. In particolare, per le applicazioni di crittografia è essenziale che l'algoritmo non permetta di ricostruire l'intera sequenza avendone osservata una parte: altrimenti un malintenzionato potrebbe riprodurre la chiave crittografica generata a partire dalla sequenza e decifrare le informazioni protette da essa. I generatori che soddisfano questo requisito sono detti crittograficamente sicuri (CSPRNG, cryptographically secure PRNG).

Un'altra proprietà significativa di un generatore di numeri casuali è il suo periodo, ovvero il numero di elementi dopo i quali la sequenza si ripete. In generale più è lungo il periodo e migliore è la qualità del generatore, anche se per la maggior parte delle applicazioni un periodo di $2^{32}-1$ (circa 4 miliardi), quale si ottiene per molti generatori di uso comune, è più che adeguato.

Algoritmi di generazione

Esistono diverse classi di generatori di numeri pseudo-casuali, che si differenziano per il tipo di algoritmo usato. Nella quasi totalità essi producono una sequenza di numeri interi uniformemente distribuiti tra 0 e un certo valore massimo, oppure di numeri reali tra 0 e 1 (questi ultimi si possono sempre ottenere dai primi semplicemente dividendo per il valore massimo).

Prima di essere usato, un generatore deve essere inizializzato assegnando un opportuno valore a un parametro numerico, o gruppo di parametri, che viene chiamato seme (in inglese seed). Ogni volta che si usa lo stesso seme, si otterrà sempre la stessa identica sequenza. Il periodo di un generatore non può quindi superare il numero dei possibili valori del seme: per esempio un generatore il cui seme è immagazzinato in un'unica variabile a 32 bit potrà avere al massimo un periodo di $2^{32}$ (solitamente il valore zero non è consentito e quindi i valori possibili sono in effetti $2^{32}-1$).

Un'attenta analisi matematica è richiesta per assicurare che i numeri generati abbiano le necessarie proprietà statistiche. Robert R. Coveyou dell'Oak Ridge National Laboratory ha intitolato un articolo: "La generazione dei numeri casuali è troppo importante per essere lasciata al caso".

Le principali classi di generatori di uso corrente:

• generatori lineari congruenziali (LCG, linear congruential generators): questa è la prima classe in ordine di tempo ad essere stata utilizzata, e tuttora la più diffusa.
• generatori di Fibonacci ritardati (lagged Fibonacci): sono in grado di generare sequenze molto lunghe. Tra questi va segnalato l'algoritmo Mersenne Twister, che ha un periodo di $2^{19937}-1$.
• registri di traslazione a retroazione lineare
• registri di traslazione a retroazione generalizzata

I seguenti sono generatori crittograficamente sicuri:

• Fortuna
• Blum Blum Shub

Distribuzioni non uniformi

È possibile generare anche sequenze di numeri pseudo-casuali aventi distribuzione non uniforme: se la forma della distribuzione desiderata è data dalla funzione $f(x)$ (di integrale pari a 1) e se $\{x_{n}\}$ è una sequenza di numeri uniformemente distribuiti nell'intervallo $[0,1]$, una sequenza avente la distribuzione desiderata si ottiene calcolando $y_{n}=F^{-1}(x_{n})$, dove $F$ è la funzione integrale o funzione cumulativa relativa alla funzione $f$:

$F(x)=\int _{-\infty }^{x}f(y)dy$

e $F^{-1}(x)$ è la sua funzione inversa.

Questo metodo va con il nome di metodo di inversione.

Esempio

si vogliono generare numeri pseudo-casuali distribuiti secondo la distribuzione $f(x)=e^{-x}$. Allora avremo che:

$F(x)=\int _{0}^{x}e^{-y}dy=1-e^{-x}$.

e

$F^{-1}(x)=-\ln(1-x)$.

Sia ora $r$ la nostra variabile casuale generata uniformemente tra 0 ed 1, poniamo $r=F(x)$, allora

$x=-\ln(1-r)$

è una variabile pseudo-casuale generata secondo la distribuzione $f(x)$.

Per la distribuzione normale, che non è integrabile in forma chiusa, si usa la trasformazione di Box-Muller.

Numeri pseudo-casuali in C

Lo standard del linguaggio C (ISO C89) prevede due funzioni dedicate alla generazione di numeri pseudo-casuali:

void srand(unsigned seed);

int rand(void);

La prima funzione inizializza il seme della sequenza, la seconda estrae un numero intero equidistribuito tra 0 e RAND_MAX. Il valore di RAND_MAX dipende dall'implementazione; solitamente è 32767 ($2^{15}-1$) oppure 2147483647 ($2^{31}-1$). I prototipi di queste funzioni sono nell'header stdlib.h.

Lo standard non prescrive l'uso di un particolare algoritmo; generalmente viene usato il metodo lineare congruenziale.

Esempio

La seguente funzione genera una sequenza pseudo-casuale a 16 bit.

uint random;  // Variabile globale in cui è memorizzato il numero casuale (16bit)
void randomNext(void) {
  // Aggiorna sequenza random
  // Algoritmo Polinomiale:
  // +> b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15
  // |     |  |     |                                     |
  // ------+--+-----+-------------------------------------+
  // carry = b1^b2^b4^b15
  // Pn+1=(Pn<<1)|carry
  uchar randomtmp;  // Accumulo le operazioni ex-OR
  if (random==0) random++;  // N.B. : il seed dovrebbe essere != 0
  randomtmp=0;
  if ((uchar)random&0x02) randomtmp=1;
  if ((uchar)random&0x04) randomtmp^=1;
  if ((uchar)random&0x10) randomtmp^=1;
  if (random&0x8000) randomtmp^=1;
  random<<=1;
  (uchar)random|=randomtmp;
}

Bibliografia

• R. R. Coveyou, Random Number Generation is Too Important to be Left to Chance, Studies in Appl. Math., 3, 70-111, 1970.
• Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Chapter 3, pp. 1–193.
• John von Neumann, "Various techniques used in connection with random digits," in A. S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C.: U. S. Government Printing Office, 1951): 36-38.
• NIST Recommendation for Random Number Generation Using Deterministic Random Bit Generators
• Luc Devroye Non-Uniform Random Variate Generation, Springer-Verlag, New York, 1986.