Trasformazione di Box-Muller: differenze tra le versioni
m Nuova pagina: [[Image:Box_Muller.svg|thumb|160px|Diagramma della trasformazione di Box Muller. I cerchi inziali, a distanza uniforme dall'origine sono trasformati in un insieme di cerchi centrati ne... |
(Nessuna differenza)
|
Versione delle 14:17, 13 lug 2007
La trasformazione di Box-Muller (George Edward Pelham Box e Mervin Edgar Muller, 1958)[1] è 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. La forma principale è quella del lavoro originale: si campionano due numeri dalla distribuzione uniforme sull'intervallo e si ricavano de numeri distribuiti normalmente. La forma polare campiona due numeri su un intervallo differente () e permette di ricavare due numeri distribuiti normalmente senza l'uso delle funzioni seno e coseno.
Basic form
Siano e due variabili aleatorie indipendenti ed uniformemente distribuite nell'intervallo . Sia
e
Allora Z0 e Z1 sono variabili aleatorie indipendenti con distribuzione normale di deviazione standard unitaria.
La dimostrazione[2] è basata sul fatto che, in un sistema cartesiano bidimensionale nel quale le coordinate X e Y sono descritte da due variabili casuali indipendenti normalmente distribuite, le variabili casuali R2 e nelle corrispondenti coordinate polari sono a loro volta indipendenti e possono essere espresse come
e
Polar form
La forma polare viene attribuita da Devroye[3] a Marsaglia. Viene citata senza attribuzione in Carter.[4]
Assegnati e , indipendenti ed uniformemente distribuiti nell'intervallo chiuso , si pone . (Ovviamente .) Se o , si trascurano e e si considera un'altra coppia . Si continua fino a trovare una coppia con nell'intervallo aperto . Dal moment che e sono distribuiti uniformemente e poiché solamente i punti all'interno cella criconferenza unitaria sono stati accettati, anche i valori di saranno distribuiti uniformemente nell'intervallo aperto .
Il valore di si identifica con quello della forma base, . Come mostrato in figura, i valori di e nella forma base possono essere sostituiti con i rapporti e rispettivamente. Il vantaggio è dato dalla mancata valutazione delle funzioni trigonometriche (che è un'operazione più onerosa di un rapporto). Così come per la forma base, si sono ottenute due variabili gaussiane a varianza unitaria.
e
Confronto fra le due forme
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 (purché il generatore di numeri casuali sia relativamente efficiente) e tipicamente più robusto.[4]
Si evita il l'utilizzo delle funzioni trigonometriche che sono tipicamente più costose delle divisioni; vengono scartate 1 − π/4 ≈ 21.46% del totale di coppie generate, ovvero si scartano 4/π − 1 ≈ 27.32% coppie di numeri casuali uniformemente distribuiti per ciascuna coppia di numeri casuali normalmente distribuiti, richiedendo 4/π ≈ 1.2732 numeri di input per numero generato.
La forma base richiede tre moltiplicazioni, un logaritmo, una radice quadrata ed una funzione trigonometrica per ciascun numero casuale normalmente distribuito[5]
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.
Voci collegate
La trasformata di Box-Muller viene utilizzata in simulazioni numeriche (di dinamica molecolare o tramite il metodo Monte Carlo) ad esempio per campionare la distribuzione di Maxwell-Boltzmann.
Bibliografia
- ^ (EN) G. E. P. Box and Mervin E. Muller, A Note on the Generation of Random Normal Deviates, The Annals of Mathematical Statistics (1958), Vol. 29, No. 2 pp. 610-611
- ^ (EN) Sheldon Ross, A First Course in Probability, (2002), p.279-81
- ^ (EN) L. Devroye: 'Non-Uniform Random Variate Generation', Springer-Verlag, New York, 1986.
- ^ a b [ ftp://ftp.taygeta.com/pub/publications/randnum.tar.Z Everett F. Carter, Jr., The Generation and Application of Random Numbers, Forth Dimensions (1994), Vol. 16, No. 1 & 2.]
- ^ Il calcolo di è contato come singola multiplicazione perchè il valore può essere calcolato precedentemente ed utilizzato in seguito.