Eginardo

Wikipedia:Babelfish

Questo utente apprezza Wikipedia e i Wikipediani.

Questo utente usa Iceweasel.

Questo utente è un sostenitore di GNU/Linux e del Free Software.

Questo utente ha appena provato Debian, e non cambierà più distro.

Questo utente usa spesso LATEX.

Wikipedia:Babel

it-N	Quest'utente può contribuire con un livello madrelingua in italiano.

en-3	This user has advanced knowledge of English.

la-1	Hic usor/Haec ustrix simplici lingua Latina conferre potest.

Dati personali

Sono nato nello scorso millennio... Ma per essere breve non dirò quando. Sono laureato in fisica, ma ancora non ho smesso di studiare!

Credo fortemente nella libera circolazione del sapere, e quindi utilizzo comunemente Linux - ed in particolare Debian (ed ovviamente collaboro saltuariamente con Wikipedia). Una massima che mi ha sempre colpito è

«Faber est suae quisque fortunae»

(Appio Claudio Cieco)

Non sono assolutamente convinto che sia così, ma si deve lavorare perché lo sia!

Così ho iniziato a collaborare con Wikipedia:

14:26, 30 ott 2006 (cron) (diff) Prodotto tensoriale.

Ma già prima la consultavo (anche se solo nella versione inglese!).

Ringraziamenti

Voglio ringraziare tutti coloro dai quali ho copiato per personalizzare la mia pagina personale (l'unico che conosco, e che quindi ricordo, è Blazar).

Box Muller

 

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

Basic form

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

${\displaystyle Z_{0}=R\cos(\Theta )={\sqrt {-2\ln U_{1}}}\cos(2\pi U_{2})\,}$ 

e

${\displaystyle 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^[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 R² e ${\displaystyle \Theta }$  nelle corrispondenti coordinate polari sono a loro volta indipendenti e possono essere espresse come

${\displaystyle R^{2}=-2\cdot \ln U_{1}\,}$ 

e

${\displaystyle \Theta =2\pi U_{2}.\,}$ 

Polar form

 

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

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

${\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

${\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 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

• Distribuzione normale
• Inverse transform sampling
• Marsaglia polar method, an optimization of the Box-Muller transform
• Algoritmo Ziggurat, a very different way to generate normal random numbers

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.
4. [ 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.]
5. ^ Il calcolo di ${\displaystyle 2\pi U_{1}}$  è contato come singola multiplicazione perchè il valore ${\displaystyle 2\pi }$  può essere calcolato precedentemente ed utilizzato in seguito.

Collegamenti esterni

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