Lezione del 15 -11- 2011

Generatori di numeri casuali

I Numeri casuali sono utilizzati per costruire simulazioni di natura probabilistica di fenomeni fisici , di problemi decisionali, finanziari e  informatici.

Brevi cenni storici

L’idea di utilizzare in modo sistematico simulazioni di tipo probabilistico per risolvere un problema di natura fisica viene generalmente attribuita al matematico polacco Stanislaw Ulam (1909-1984). Ulam fu uno dei personaggi chiave nel progetto americano per la costruzione della bomba atomica  durante la seconda guerra mondiale. Il progetto richiedeva la risoluzione di un enorme numero di problemi incredibilmente complessi. 

Generatori di numeri pseudo- casuali

Nessun calcolatore è in grado di generare numeri puramente casuali, ma solo numeri pseudo-casuali o quasi-casuali ossia numeri generati da algoritmi numerici deterministici in grado di superare una serie di test statistici che conferiscono a tali numeri una apparente casualità.

 Nei primi anni dell’era dei computer (1946) John von Neumann suggerì il famoso metodo middle-square per generare numeri pseudo casuali distribuiti in modo uniforme. In tale distribuzione uniforme ogni possibile numero in un determinato intervallo è ugualmente probabile. Il metodo middle-square richiede come tutti i generatori di numeri casuali un valore iniziale, detto seme dal quale vengono generati i successivi valori. La successione generata quindi non potrà essere casuale ma avrà solo il carattere di apparente casualità. Oggi il metodo middle-square ha un’importanza solamente storica.

Nel 1948 venne proposto un generatore di numeri casuali distribuiti uniformemente detto generatore lineare congruenziale o più brevemente LCG che a tutt’oggi è ancora utilizzato. Tale generatore venne presentato per la prima volta dal matematico D.H. Lemer esperto di teoria dei numeri. Il metodo LCG, analogamente al metodo  middle-square, ha bisogno di un seme per inizializzare la sequenza di numeri secondo la seguente regola: xn+1 = (axn + c)modm, n  0, dove a, c ed m sono opportuni numeri interi costanti. La notazione “mod m”, ossia modulo m, significa che axn + c viene diviso per m e xn+1 posto uguale al resto intero della divisione. Quindi xn+1 assume valori interi tra 0, 1, 2, . . . ,m − 1.

” Una proprietà importante nel valutare la bontà di un generatore uniforme di numeri pseudo-casuali è l’assenza di correlazione tra i numeri generati dall’algoritmo”.

 Trasformazione di Box-Muller

La trasformazione di Box-Muller è un metodo per generare coppie di numeri casuali indipendenti e distribuiti gaussianamente con media nulla e varianza uno.

La trasformazione viene comunemente espressa in due forme:

–         Forma base nella quale  si campionano due numeri dalla distribuzione uniforme sull’intervallo (0,1] e si ricavano due numeri distribuiti normalmente.

 –         Forma  polare che campiona due numeri su un intervallo differente ([ − 1, + 1]) e permette di ricavare due numeri distribuiti normalmente senza l’uso delle funzioni seno e coseno.

 La forma polare differisce da quella base in quanto è un esempio di tecnica di rigetto. Vengono scartati alcuni numeri casuali, ma l’algoritmo è più veloce della forma base perché meno oneroso da valutare numericamente  e tipicamente più robusto.

La forma base richiede tre moltiplicazioni, un logaritmo, una radice quadrata ed una funzione trigonometrica per ciascun numero casuale normalmente distribuito.

La forma polare richiede due moltiplicazioni, un logaritmo, una radice quadrata ed una divisione per ciascun numero gaussiano. L’effetto è quello di sostituire una moltiplicazione ed una funzione trigonometrica con una sola divisione.

Numeri casuali in VB.Net

Per generare un numero casuale (o random) in Visual Basic.Net è necessario creare un oggetto di tipo Random :

 Dim MyRnd As New Random

 Dopo aver fatto cioè si può utilizzare una delle seguenti istruzioni:

1.  MyRnd.Next

Restituisce un numero casuale intero non negativo a 32 bit;

2.  MyRnd.Next(N)

Restituisce un numero casuale compreso tra 0 e N-1;

3.   MyRnd.Next(m, M)

Restituisce un numero random intero compreso tra m e M-1;

4.   MyRnd.NextDouble

Restituisce un numero random con la virgola compreso tra 0,0 e 1,0.