Trasformazione di Box-Muller: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
m Bot: fix citazione web (v. discussione) |
||
Riga 1:
[[Immagine:Box_Muller.svg|thumb|upright=0.7|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)<ref>
La trasformazione viene comunemente espressa in due forme. La forma principale è quella del lavoro originale: si campionano due numeri dalla distribuzione uniforme sull'intervallo <math>(0,1]</math> e si ricavano due numeri distribuiti normalmente. La forma polare campiona due numeri su un intervallo differente (<math>[-1,+1]</math>) e permette di ricavare due numeri distribuiti normalmente senza l'uso delle funzioni [[seno (trigonometria)|seno]] e [[coseno]].
Riga 20:
:<math>R^2 = -2\cdot\ln U_1</math>
e
:<math>\Theta = 2\pi U_2.</math>
Riga 27:
[[Immagine:BoxMullerTransformUsingPolarCoordinates.png|thumb|upright=1.8|Due valori distribuiti uniformemente, <math>u</math> e <math>v</math> vengono usati per ottenere il valore <math>s=R^2</math>, 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<ref>{{en}} [http://cg.scs.carleton.ca/~luc/rnbookindex.html L. Devroye: 'Non-Uniform Random Variate Generation', Springer-Verlag, New York, 1986.]</ref> a Marsaglia. Viene citata senza attribuzione in Carter.<ref name="Carter">[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.]</ref>
Assegnati <math>u</math> e <math>v</math>, indipendenti ed uniformemente distribuiti nell'intervallo chiuso <math>[-1,+1]</math>, si pone <math>s = R^2 = u^2 + v^2</math>. (Ovviamente <math>R = \sqrt{s}</math>.) Se <math>s=0</math> o <math>s > 1</math>, si trascurano <math>u</math> e <math>v</math> e si considera un'altra coppia <math>(u,v)</math>. Si continua fino a trovare una coppia con <math>s</math> nell'intervallo aperto <math>(0,1)</math>. Dal momento che <math>u</math> e <math>v</math> sono distribuiti uniformemente e poiché solamente i punti all'interno della circonferenza unitaria sono stati accettati, anche i valori di <math>s</math> saranno distribuiti uniformemente nell'intervallo aperto <math>(0,1)</math>.
Il valore di <math>s</math> si identifica con quello della forma base, <math>U_1</math>. Come mostrato in figura, i valori di <math>\cos \theta = \cos 2 \pi U_2</math> e <math>\sin \theta = \sin 2 \pi U_2</math> nella forma base possono essere sostituiti con i rapporti <math>\cos \theta = u/R = u/\sqrt{s}</math> e <math>\sin \theta = v/R = v/\sqrt{s}</math> 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.
:<math>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}}</math>
e
:<math>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}}.</math>
Riga 43:
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 [[Numeri pseudo-casuali|generatore di numeri casuali]] sia relativamente efficiente) e tipicamente più robusto.<ref name="Carter"/>
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<ref>Il calcolo di <math>2 \pi U_1</math> è contato come singola multiplicazione perché il valore <math>2\pi</math> può essere calcolato precedentemente ed utilizzato in seguito.</ref>
Riga 61:
== Collegamenti esterni ==
* {{
* {{
* {{
{{Portale|matematica}}
| |||