Trasformazione di Box-Muller

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 ] {\displaystyle (0,1]} e si ricavano due numeri distribuiti normalmente. La forma polare campiona due numeri su un intervallo differente ( [ − 1 , + 1 ] {\displaystyle [-1,+1]} ) e permette di ricavare due numeri distribuiti normalmente senza l'uso delle funzioni seno e coseno.

Forma base

Siano U 1 {\displaystyle U_{1}} e U 2 {\displaystyle U_{2}} due variabili aleatorie indipendenti ed uniformemente distribuite nell'intervallo ( 0 , 1 ] {\displaystyle (0,1]} . Sia

Z 0 = R cos ⁡ ( Θ ) = − 2 ln ⁡ U 1 cos ⁡ ( 2 π U 2 ) {\displaystyle Z_{0}=R\cos(\Theta )={\sqrt {-2\ln U_{1}}}\cos(2\pi U_{2})}

e

Z 1 = R sin ⁡ ( Θ ) = − 2 ln ⁡ U 1 sin ⁡ ( 2 π U 2 ) . {\displaystyle 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 Θ {\displaystyle \Theta } nelle corrispondenti coordinate polari sono a loro volta indipendenti e possono essere espresse come

R 2 = − 2 ⋅ ln ⁡ U 1 {\displaystyle R^{2}=-2\cdot \ln U_{1}}

e

Θ = 2 π U 2 . {\displaystyle \Theta =2\pi U_{2}.}

Forma polare

Due valori distribuiti uniformemente, u {\displaystyle u} e v {\displaystyle v} vengono usati per ottenere il valore s = R 2 {\displaystyle 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 {\displaystyle u} e v {\displaystyle v} , indipendenti ed uniformemente distribuiti nell'intervallo chiuso [ − 1 , + 1 ] {\displaystyle [-1,+1]} , si pone s = R 2 = u 2 + v 2 {\displaystyle s=R^{2}=u^{2}+v^{2}} . Se s = 0 {\displaystyle s=0} o s ≥ 1 {\displaystyle s\geq 1} , si trascurano u {\displaystyle u} e v {\displaystyle v} e si considera un'altra coppia ( u , v ) {\displaystyle (u,v)} . Si continua fino a trovare una coppia con s {\displaystyle s} nell'intervallo aperto ( 0 , 1 ) {\displaystyle (0,1)} . Dal momento che u {\displaystyle u} e v {\displaystyle v} sono distribuiti uniformemente e poiché solamente i punti all'interno della circonferenza unitaria sono stati accettati, anche i valori di s {\displaystyle s} saranno distribuiti uniformemente nell'intervallo aperto ( 0 , 1 ] {\displaystyle (0,1]} .

Il valore di s {\displaystyle s} si identifica con quello della forma base, U 1 {\displaystyle U_{1}} . Come mostrato in figura, i valori di cos ⁡ θ = cos ⁡ 2 π U 2 {\displaystyle \cos \theta =\cos 2\pi U_{2}} e sin ⁡ θ = sin ⁡ 2 π U 2 {\displaystyle \sin \theta =\sin 2\pi U_{2}} nella forma base possono essere sostituiti con i rapporti cos ⁡ θ = u / R = u / s {\displaystyle \cos \theta =u/R=u/{\sqrt {s}}} e sin ⁡ θ = v / R = v / s {\displaystyle \sin \theta =v/R=v/{\sqrt {s}}} rispettivamente. Il vantaggio è dato dalla mancata valutazione delle funzioni trigonometriche che è un'operazione computazionalmente più onerosa di un rapporto. Così come per la forma base, si sono ottenute due variabili gaussiane a varianza unitaria.

z 0 = − 2 ln ⁡ U 1 cos ⁡ ( 2 π U 2 ) = − 2 ln ⁡ s ( u s ) = u ⋅ − 2 ln ⁡ s s {\displaystyle 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 = − 2 ln ⁡ U 1 sin ⁡ ( 2 π U 2 ) = − 2 ln ⁡ U 1 ( v s ) = v ⋅ − 2 ln ⁡ s s . {\displaystyle 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

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 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.

La trasformata di Box-Muller viene utilizzata in simulazioni numeriche di dinamica molecolare tramite il metodo Monte Carlo o per esempio per campionare la distribuzione di Maxwell-Boltzmann.

Bibliografia

  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. Archiviato il 5 maggio 2009 in Internet Archive.
  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 π U 1 {\displaystyle 2\pi U_{1}} è contato come singola moltiplicazione perché il valore 2 π {\displaystyle 2\pi } può essere calcolato precedentemente ed utilizzato in seguito.

Voci correlate

  • Distribuzione normale
  • Metodo Montecarlo
  • Dinamica molecolare

Collegamenti esterni

  • (EN) Applet Java relativo a Box-Muller, su kdcalc.com.
  • (EN) Generare numeri casuali, su taygeta.com.
  • (EN) La trasformazione di Box-Muller su MathWorld, su mathworld.wolfram.com.
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica