Box-Muller transform

A Box-Muller transform (by George Edward Pelham Box and Mervin Edgar Muller 1958) [ [http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.aoms/1177706645 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] ] 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 Muller 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-Muller transform was developed to be more computationally efficient. [Kloeden and Platen, "Numerical Solutions of Stochastic Differential Equations", p. 11-12] The more efficient Ziggurat algorithm can also be used.

Basic form

Suppose "U"1 and "U"2 are independent random variables that are uniformly distributed in the interval (0, 1] . Let

:Z_0 = R cos(Theta) =sqrt{-2 ln U_1} cos(2 pi U_2),

and

:Z_1 = R sin(Theta) = sqrt{-2 ln U_1} sin(2 pi U_2).,

Then "Z"0 and "Z"1 are independent random variables with a normal distribution of standard deviation 1.

The derivation [Sheldon Ross, "A First Course in Probability", (2002), p.279-81] 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

:R^2 = -2cdotln U_1,

and

:Theta = 2pi U_2.,

Polar form

The polar form is attributed by Devroye [ [http://cg.scs.carleton.ca/~luc/rnbookindex.html L. Devroye: 'Non-Uniform Random Variate Generation', Springer-Verlag, New York, 1986.] ] to Marsaglia. It is also mentioned without attribution in 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.] ]

Given "u" and "v", independent and uniformly distributed in the closed interval [−1, +1] , set "s" = "R"2 = "u"2 + "v"2. (Clearly scriptstyle R = sqrt{s}.) If "s" = 0 or "s" > 1, throw "u" and "v" away and try another pair ("u", "v"). 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 latter can be seen by calculating the cumulative distribution function for "s" in the interval (0, 1). This is the area of a circle with radius scriptstyle sqrt{s} divided by scriptstylepi. 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 scriptstyle 2 pi is uniformly distributed in the open interval (0, 1) and independent of "s".

We now identify the value of "s" with that of "U"1 and scriptstyle heta/(2 pi) with that of "U"2 in the basic form. As shown in the figure, the values of scriptstyle cos heta = cos 2 pi U_2 and scriptstyle sin heta = sin 2 pi U_2 in the basic form can be replaced with the ratios scriptstylecos heta = u/R = u/sqrt{s} and scriptstylesin heta = v/R = v/sqrt{s}, 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.

:z_0 = sqrt{-2 ln U_1} cos(2 pi U_2) = sqrt{-2 ln s} left(frac{u}{sqrt{s ight) = u cdot sqrt{frac{-2 ln s}{s

and

:z_1 = sqrt{-2 ln U_1} sin(2 pi U_2) = sqrt{-2 ln s}left( frac{v}{sqrt{s ight) = v cdot sqrt{frac{-2 ln s}{s.

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. 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. [Note that the evaluation of 2 pi U_1 is counted as a single multiplication because the value of 2pi can be computed in advance and used repeatedly.]

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.

ee also

* Normal distribution
* Inverse transform sampling
* Marsaglia polar method, an optimization of the Box-Muller transform
* Ziggurat algorithm, a very different way to generate normal random numbers

References

External links

* [http://www.kdcalc.com/demos/NormalDistribution/NormalDistribution.html Box-Muller running in a Java Applet]
* [http://www.taygeta.com/random/gaussian.html Generating Gaussian Random Numbers]
* [http://mathworld.wolfram.com/Box-MullerTransformation.html Box-Muller Transform on MathWorld]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Método de Box-Muller — Diagrama de la transformada de Box Müller. Los círculos iniciales, se encuentran uniformemente espaciados respecto al origen, están graficados junto con otro conjunto de círculos centrados en el origen donde la separación entre ellos aumenta a… …   Wikipedia Español

  • Muller — may refer to: Contents 1 People 2 Characters 3 Other 4 …   Wikipedia

  • Inverse transform sampling — Inverse transform sampling, also known as the probability integral transform, is a method of generating sample numbers at random from any probability distribution given its cumulative distribution function (cdf). This method is generally… …   Wikipedia

  • Normal distribution — This article is about the univariate normal distribution. For normally distributed vectors, see Multivariate normal distribution. Probability density function The red line is the standard normal distribution Cumulative distribution function …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • Uniform distribution (continuous) — Uniform Probability density function Using maximum convention Cumulative distribution function …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Ziggurat algorithm — The ziggurat algorithm is an algorithm to generate random numbers from a non uniform distribution. It belongs to the class of rejection sampling algorithms and can be used for choosing values from a monotone decreasing probability distribution.… …   Wikipedia

  • List of transforms — This is a list of transforms in mathematics.Integral transforms*Abel transform *Fourier transform **Short time Fourier transform *Hankel transform *Hartley transform *Hilbert transform **Hilbert Schmidt integral operator *Laplace transform… …   Wikipedia

  • Marsaglia polar method — The polar method (attributed to George Marsaglia, 1964[1]) is a pseudo random number sampling method for generating a pair of independent standard normal random variables. While it is superior to the Box–Muller transform[citation needed], the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.