Box-Muller transform

Jump to: navigation, search
File:Box Muller.svg
Diagram of the Box Müller transform. The initial circles, uniformly spaced about the origin, are mapped to another set of circles about the origin that are closely spaced near the origin but quickly spread out. The largest circles in the domain map to the smallest circles in the range and vice versa.

A Box-Müller transform (by George Edward Pelham Box and Mervin Edgar Müller 1958)[1] is a method of generating pairs of independent standard normally distributed (zero expectation, unit variance) random numbers, given a source of uniformly distributed random numbers.

It is commonly expressed in two forms. The basic form as given by Box and Müller takes two samples from the uniform distribution on the interval (0, 1] and maps them to two normally distributed samples. The polar form takes two samples from a different interval, [−1, +1], and maps them to two normally distributed samples without the use of sine or cosine functions.

One could use the inverse transform sampling method to generate normally-distributed random numbers instead; the Box-Müller transform was developed to be more computationally efficient.[2] The more efficient Ziggurat algorithm can also be used.

Basic form

Suppose U1 and U2 are independent random variables that are uniformly distributed in the interval (0, 1]. Let

<math>Z_0 = R \cos(\Theta) =\sqrt{-2 \ln U_1} \cos(2 \pi U_2)\,</math>

and

<math>Z_1 = R \sin(\Theta) = \sqrt{-2 \ln U_1} \sin(2 \pi U_2).\,</math>

Then Z0 and Z1 are independent random variables with a normal distribution of standard deviation 1.

The derivation[3] is based on the fact that, in a two-dimensional cartesian system where X and Y coordinates are described by two independent and normally distributed random variables, the random variables for R2 and Θ (shown above) in the corresponding polar coordinates are also independent and can be expressed as

<math>R^2 = -2\cdot\ln U_1\,</math>

and

<math>\Theta = 2\pi U_2.\,</math>

Polar form

File:BoxMullerTransformUsingPolarCoordinates.png
Two uniformly distributed values, <math>u</math> and <math>v</math> are used to produce the value <math>s=R^2</math>, which is likewise uniformly distributed. The definitions of the sine and cosine are then applied to the basic form of the Box-Müller Transform in order to avoid using trigonometric functions.
The polar form is attributed by Devroye[4] to Marsaglia. It is also mentioned without attribution in Carter.[5]

Given u and v, independent and uniformly distributed in the closed interval [−1, +1], set s = R2 = u2 + v2. (Clearly <math>\scriptstyle R = \sqrt{s}</math>.) If s = 0 or s > 1, throw u and v away and try another pair (uv). Continue until a pair with s in the open interval (0, 1) is found. Because u and v are uniformly distributed and because only points within the unit circle have been admitted, the values of s will be uniformly distributed in the open interval (0, 1), too. The later can easily be seen by calculating the cumulative distribution function for s in the interval (0, 1). This is nothing more than the area of a circle with radius <math>\scriptstyle \sqrt{s}</math> divided by <math>\scriptstyle\pi</math>. From this we find the probability density function to have the constant value 1 on the interval (0, 1). Equally so, the angle θ divided by <math>\scriptstyle 2 \pi</math> is clearly uniformly distributed in the open interval (0, 1) and independent of s.

We now identify the value of s with that of U1 and <math>\scriptstyle \theta/(2 \pi)</math> with that of U2 in the basic form. As shown in the figure, the values of <math>\scriptstyle \cos \theta = \cos 2 \pi U_2</math> and <math>\scriptstyle \sin \theta = \sin 2 \pi U_2</math> in the basic form can be replaced with the ratios <math>\scriptstyle\cos \theta = u/R = u/\sqrt{s}</math> and <math>\scriptstyle\sin \theta = v/R = v/\sqrt{s}</math>, respectively. The advantage is that calculating the trigonometric functions directly can be avoided. This is helpful when they are comparatively more expensive than the single division that replaces each one.

Just as the basic form produces two standard normal deviates, so does this alternate calculation.

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

and

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

Contrasting the two forms

The polar method differs from the basic method in that it is a type of rejection sampling. It throws away some generated random numbers, but it is typically faster than the basic method because it is simpler to compute (provided that the random number generator is relatively fast) and is more numerically robust.[5] It avoids the use of trigonometric functions, which are comparatively expensive in many computing environments. It throws away 1 − π/4 ≈ 21.46% of the total input uniformly distributed random number pairs generated, i.e. throws away 4/π − 1 ≈ 27.32% uniformly distributed random number pairs per Gaussian random number pair generated, requiring 4/π ≈ 1.2732 input random numbers per output random number.

The basic form requires three multiplications, one logarithm, one square root, and one trigonometric function for each normal variate.[6]

The polar form requires two multiplications, one logarithm, one square root, and one division for each normal variate. The effect is to replace one multiplication and one trigonometric function with a single division.

See also

References

  1. G. E. P. Box and Mervin E. Müller, A Note on the Generation of Random Normal Deviates, The Annals of Mathematical Statistics (1958), Vol. 29, No. 2 pp. 610-611
  2. Kloeden and Platen, Numerical Solutions of Stochastic Differential Equations, p. 11-12
  3. Sheldon Ross, A First Course in Probability, (2002), p.279-81
  4. L. Devroye: 'Non-Uniform Random Variate Generation', Springer-Verlag, New York, 1986.
  5. 5.0 5.1 Everett F. Carter, Jr., The Generation and Application of Random Numbers, Forth Dimensions (1994), Vol. 16, No. 1 & 2.
  6. Note that the evaluation of <math>2 \pi U_1</math> is counted as a single multiplication because the value of <math>2\pi</math> can be computed in advance and used repeatedly.

External links


Navigation WikiDoc | WikiPatient | Up To Date Pages | Recently Edited Pages | Recently Added Pictures

Table of Contents In Alphabetical Order | By Individual Diseases | Signs and Symptoms | Physical Examination | Lab Tests | Drugs

Editor Tools Become an Editor | Editors Help Menu | Create a Page | Edit a Page | Upload a Picture or File | Printable version | Permanent link | Maintain Pages | What Pages Link Here
There is no pharmaceutical or device industry support for this site and we need your viewer supported Donations | Editorial Board | Governance | Licensing | Disclaimers | Avoid Plagiarism | Policies
Linked-in.jpg