Box–Muller transform

Diagram of the Box Muller 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-Muller transform (by George Edward Pelham Box and Mervin Edgar Muller 1958) 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 maps uniformly distributed Cartesian coordinates falling inside the unit circle to normally distributed Cartesian coordinates. The polar form maps uniformly distributed polar coordinates to normally distributed Cartesian coordinates.

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. The more efficient Ziggurat algorithm can also be used.

Cartesian form

Given x and y independently uniformly distributed in [−1,1], set s = x² + y². If s > 1, throw them away and try another pair (x, y), until a pair with s in (0,1] is found. Then, for these filtered points, compute:

$z_{0}=x\cdot {\sqrt {\frac {-2\ln s}{s}}}$

and

$z_{1}=y\cdot {\sqrt {\frac {-2\ln s}{s}}}.$

Polar form

Suppose $U_{1}$ and $U_{2}$ are independent random variables that are uniformly distributed in (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₀ and Z₁ are independent random variables with a normal distribution of standard deviation 1.

The derivation 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 R² and $\Theta$ (shown above) in the corresponding polar coordinates are also independent and can be expressed as

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

and

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

Contrasting the two forms

The Cartesian method as opposed to the polar method is a type of rejection sampling, and throws away some generated random numbers, but it is typically faster than the polar 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 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 (1-rejected)^-1 = (2 − 4/π)^-1 ≈ 1.376 input random numbers per output random number.

See also

• Ziggurat algorithm
• Normal distribution
• Inverse transform sampling

External links

• Box-Muller running in a Java Applet
• Generating Gaussian Random Numbers
• Box-Muller Transform on MathWorld