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) è 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

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 Z₀ e Z₁ sono variabili aleatorie indipendenti con distribuzione normale di deviazione standard unitaria.

La dimostrazione è 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 R² 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

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 a Marsaglia. Viene citata senza attribuzione in Carter.

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

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.

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

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

• Distribuzione normale.
• Metodo Montecarlo.
• Dinamica molecolare.

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.

Collegamenti esterni

• (EN) Applet Java relativo a Box-Muller
• (EN) Generare numeri casuali
• (EN) La trasformazione di Box-Muller su MathWorld