Box-Muller method

Graphical illustration of the Box-Muller method

The Box-Muller method (after George Edward Pelham Box and Mervin Edgar Muller 1958) is a method for generating normally distributed random numbers .

Generation of standard normally distributed random numbers

This method first requires two independent standard random numbers and . These can be generated , for example, with a random number generator . Standard random numbers are subject to a rectangular distribution with the parameters and . ${\displaystyle u_{1}}$ ${\displaystyle u_{2}}$ ${\displaystyle 0}$ ${\displaystyle 1}$

It can be shown that one according to the following transformation step from two normally distributed (stochastic) independent random numbers and receives: ${\displaystyle z_{1}}$ ${\displaystyle z_{2}}$

${\displaystyle z_{1}={\sqrt {-2\ln u_{1}}}\cos(2\pi u_{2})}$

and

${\displaystyle z_{2}={\sqrt {-2\ln u_{1}}}\sin(2\pi u_{2})}$.

If you write the pair with polar coordinates , so ${\displaystyle (z_{1},z_{2})}$

${\displaystyle z_{1}=r\cos \varphi }$and , ${\displaystyle z_{2}=r\sin \varphi }$

then applies:

${\displaystyle r={\sqrt {-2\ln u_{1}}}\ }$and . ${\displaystyle \varphi =2\pi u_{2}}$

Application of the inversion method for the transformation of and into the polar coordinates and shows that a rectangular distribution with the parameters and is subject and an exponential distribution with the parameter . The common distribution of and can be derived from this result . It is based on the relationship: ${\displaystyle u_{1}}$ ${\displaystyle u_{2}}$ ${\displaystyle r}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle 0}$ ${\displaystyle 2\pi }$ ${\displaystyle r^{2}}$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle z_{1}}$ ${\displaystyle z_{2}}$

${\displaystyle {\tfrac {1}{2}}e^{-{\frac {1}{2}}r^{2}}\mathrm {d} (r^{2}){\tfrac {1}{2\pi }}\mathrm {d} \varphi ={\tfrac {1}{2\pi }}e^{-{\frac {1}{2}}r^{2}}r\mathrm {d} r\mathrm {d} \varphi ={\tfrac {1}{2\pi }}e^{-{\frac {1}{2}}(z_{1}^{2}+z_{2}^{2})}\mathrm {d} z_{1}\mathrm {d} z_{2}}$

The previous transformation steps generate two standard normally distributed random numbers. A standard normal distribution is a special case of the normal distribution , namely with the expected value and the variance . ${\displaystyle \mu =0}$ ${\displaystyle \sigma ^{2}=1}$

In order to generate normal distributions with any parameters using the Box-Muller method, the obtained can be mapped according to the pattern ${\displaystyle z_{i}}$

${\displaystyle x_{i}=\mu +\sigma \cdot z_{i}}$

transform. As usual, in the above notation stands for the circle number , for the sine , for the cosine and for the natural logarithm . ${\displaystyle \pi }$ ${\displaystyle \sin }$ ${\displaystyle \cos }$ ${\displaystyle \ln }$

Problems

If a linear congruence generator is used to generate the one , the pairs lie on a curve described by a spiral. This behavior is closely related to the hyperplane behavior of linear congruence generators described in Marsaglia's theorem . ${\displaystyle u_{i}}$ ${\displaystyle (z_{1};z_{2})}$

This problem can be avoided if an inverse congruence generator or the polar method is used instead of the linear congruence generator .

Conclusion

The Box-Muller method first generates two stochastically independent and standard normally distributed random numbers, which can then be transformed into a normal distribution with any parameters. The Box-Muller method requires the evaluation of logarithms and trigonometric functions, which can be very time-consuming on some computers.

Alternatives

Further possibilities for generating normally distributed random numbers are described in the article Normal Distribution. An alternative is e.g. B. the polar method .

Sources and footnotes

1. ↑ See Albert J. Kinderman and John G. Ramage: Computer Generation of Normal Random Numbers . In: Journal of the American Statistical Association , Vol. 71 (1976), Issue 356, pp. 893-896.

literature

• George Edward Pelham Box, Mervin Edgar Muller: A note on the generation of random normal deviates. In: Annals of Mathematical Statistics , Vol. 29 (1958), Issue 2, ISSN  0003-4851 , pp. 610-611.
• Donald Ervin Knuth : The Art of Computer Programming , Sec. 3.4.1, p. 117.
• Otto Moeschlin, Eugen Grycko, Claudia Pohl, Frank Steinert: Chapter 1.4 Generating Sample Values . In: Diess .: Experimental Stochastics. Springer, Berlin et al. 1998, ISBN 3-540-14619-9 .