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 .
It can be shown that one according to the following transformation step from two normally distributed (stochastic) independent random numbers and receives:
and
- .
If you write the pair with polar coordinates , so
- and ,
then applies:
- and .
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:
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 .
In order to generate normal distributions with any parameters using the Box-Muller method, the obtained can be mapped according to the pattern
transform. As usual, in the above notation stands for the circle number , for the sine , for the cosine and for the natural logarithm .
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 .
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
- ↑ 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 .