Trasformazione di Box-Muller

Da Wikipedia, l'enciclopedia libera.
Diagramma della trasformazione di Box Muller. I cerchi iniziali, a distanza uniforme dall'origine sono trasformati in un insieme di cerchi centrati nell'origine più concentrati vicino all'origine. I cerchi più grandi vengono mandati nei cerchi più piccoli e viceversa.

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 (0,1] e si ricavano due numeri distribuiti normalmente. La forma polare 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.

Forma base[modifica | modifica wikitesto]

Siano U_1 e U_2 due variabili aleatorie indipendenti ed uniformemente distribuite nell'intervallo (0,1]. Sia

Z_0 = R \cos(\Theta) =\sqrt{-2 \ln U_1} \cos(2 \pi U_2)

e

Z_1 = R \sin(\Theta) = \sqrt{-2 \ln U_1} \sin(2 \pi U_2).

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 \Theta nelle corrispondenti coordinate polari sono a loro volta indipendenti e possono essere espresse come

R^2 = -2\cdot\ln U_1

e

\Theta = 2\pi U_2.

Forma polare[modifica | modifica wikitesto]

Due valori distribuiti uniformemente, u e v vengono usati per ottenere il valore s=R^2, anch'esso uniformemente distribuito. Le definizioni di seno e coseno vengono quindi applicate alla forma base della trasformazione di Box-Muller per evitare l'uso di funzioni trigonometriche.

La forma polare viene attribuita da Devroye[3] a Marsaglia. Viene citata senza attribuzione in Carter.[4]

Assegnati u e v, indipendenti ed uniformemente distribuiti nell'intervallo chiuso [-1,+1], si pone s = R^2 = u^2 + v^2. (Ovviamente R = \sqrt{s}.) Se s=0 o s > 1, si trascurano u e v e si considera un'altra coppia (u,v). Si continua fino a trovare una coppia con s nell'intervallo aperto (0,1). Dal momento che u e v sono distribuiti uniformemente e poiché solamente i punti all'interno della circonferenza unitaria sono stati accettati, anche i valori di s saranno distribuiti uniformemente nell'intervallo aperto (0,1).

Il valore di s si identifica con quello della forma base, U_1. Come mostrato in figura, i valori di \cos \theta = \cos 2 \pi U_2 e \sin \theta = \sin 2 \pi U_2 nella forma base possono essere sostituiti con i rapporti \cos \theta = u/R = u/\sqrt{s} e \sin \theta = v/R = v/\sqrt{s} 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.

z_0 = \sqrt{-2 \ln U_1} \cos(2 \pi U_2) = \sqrt{-2 \ln s} \left(\frac{u}{\sqrt{s}}\right) = u \cdot \sqrt{\frac{-2 \ln s}{s}}

e

z_1 = \sqrt{-2 \ln U_1} \sin(2 \pi U_2) = \sqrt{-2 \ln U_1}\left( \frac{v}{\sqrt{s}}\right) = v \cdot \sqrt{\frac{-2 \ln s}{s}}.

Confronto fra le due forme[modifica | modifica wikitesto]

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 correlate[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

  1. ^ (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
  2. ^ (EN) Sheldon Ross, A First Course in Probability, (2002), p.279-81
  3. ^ (EN) L. Devroye: 'Non-Uniform Random Variate Generation', Springer-Verlag, New York, 1986.
  4. ^ a b Everett F. Carter, Jr., The Generation and Application of Random Numbers, Forth Dimensions (1994), Vol. 16, No. 1 & 2.
  5. ^ Il calcolo di 2 \pi U_1 è contato come singola multiplicazione perché il valore 2\pi può essere calcolato precedentemente ed utilizzato in seguito.

Collegamenti esterni[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica