Box-Muller transform
|
|
A Box-Muller transform 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:
(1) 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>
(2) Given x and y independently uniformly distributed in [−1,1], set R = x2 + y2. 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>
The second method, which is a type of rejection sampling, is 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 (http://www.taygeta.com/random/gaussian.html)de:Box-Muller-Methode