Sequenze stocastiche e deterministiche

Gli algoritmi proposti in letteratura sono innumerevoli ed una loro trattazione anche superficiale va ben oltre gli obiettivi di questo intervento. Ci limitiamo a proporne due al fine di evidenziare i concetti fondamentali [13]. La classe di generatori detta congruenze lineari si definisce nel modo seguente:

Dove a è detto moltiplicatore, b traslazione e M modulo tali che a,c,x, ε {0,1,2,...,M-1}. Dato un valore iniziale, detto anche “seme”, è possibile ottenere una sequenza di numeri pseudo-casuali:

Se un elemento si ripete dopo k iterazioni, si dice che il generatore ha periodo k. I parametri vengono scelti in modo da rendere massimo tale valore. Si può dimostrare, tuttavia, che le k-ple di numeri generati con il metodo delle congruenze lineari giacciono su al più (k!m)1/k iperpiani e quindi non sono distribuiti uniformemente nell’ipercubo [0,1]k. Questo costituisce una forte limitazione all’uso di tale generatore per il caso multivariato.

Tra i metodi deterministici troviamo anche le successioni a bassa discrepanza, spesso presentate tra i metodi di riduzione della varianza poiché consentono di aumentare l’accuratezza dei risultati della simulazione. Si tratta infatti di algoritmi deterministici che generano sequenze di numeri pseudo-casuali in grado di coprire in modo uniforme lo spazio in cui si sta simulando.

Gli algoritmi generano i numeri pseudo-casuali in modo da riempire gli “spazi vuoti” lasciati dalle precedenti generazioni casuali. Per comprendere il tipo di algoritmi che consentono di generare successioni a bassa discrepanza, trattiamo ora a titolo esemplificativo la sequenza di Halton. Si consideri un numero intero i, esso può essere rappresentato in base b nel modo seguente: La sequenza di Halton è data da:

e permette di generare un numero in base 10 tra 0 e 1. Per generare una sequenza su più dimensioni (n) si considerano più basi:

Le successioni a bassa discrepanza (che individuano i metodi detti Quasi-Monte Carlo) sono caratterizzate da un ordine di convergenza dell’errore diverso rispetto ai metodi Monte Carlo classici, pari a (log M)d/M , dove d è la dimensionalità del problema [1] (figura 1). Si può dimostrare tuttavia che l’efficienza nel coprire in modo uniforme l’iperpiano unitario si deteriora all’aumentare della dimensionalità. I valori generati, in particolare presentano caratteristiche di collinearità [8].

Di R. Casarin & M. Gobbo