Box-Muller transform

From Free net encyclopedia

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. There are two kinds:

Contents 1 Basic form 2 Polar form 3 Contrasting the two forms 4 External links

Basic form

Given r and φ independently uniformly distributed in (0,1], compute:

<math>z_0 = \cos(2 \pi \varphi) \cdot \sqrt{-2 \ln r}</math>

and

<math>z_1 = \sin(2 \pi \varphi) \cdot \sqrt{-2 \ln r}.</math>

Polar form

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

<math>z_0 = x \cdot \sqrt{\frac{-2 \ln R}{R}}</math>

and

<math>z_1 = y \cdot \sqrt{\frac{-2 \ln R}{R}}.</math>

Contrasting the two forms

The second method, which is a type of rejection sampling, is the polar equivalent of the first, but typically faster because it uses only one transcendental function instead of at least two, even though it throws away 1 − π/4 ≈ 21.46% of the total input uniformly distributed random number pairs generated, i.e. throws away 4/π − 1 ≈ 0.2732 uniformly distributed random number pairs per Gaussian random number pair generated, requiring 4/π ≈ 1.2732 input random numbers per output random number.

External links

• Generating Gaussian Random Numbers
• Box-Muller Transform on MathWorldde:Box-Muller-Methode

pl:Transformacja Boxa-Mullera ru:Преобразование Бокса — Мюллера uk:Перетворення Бокса-Мюллера