The Monty Python method for generating random variables

ABSTRACT

We suggest an interesting and fast method for generating normal, exponential, t, von Mises, and certain other important random variables used in Monte Carlo studies. The right half of a symmetric density is cut into pieces, then, using simple area-preserving transformations, reassembled into a rectangle from which the x-coordinate—or a linear function of the x-coordinate—of a random point provides the required variate. To illustrate the speed and simplicity of the Monty Python method, we provide a small C program, self-contained, for rapid generation of normal (Gaussian) variables. It is self-contained in the sense that required uniform variates are generated in-line, as pairs of 16-bit integers by means of the remarkable new multiply-with-carry method.

REFERENCES

• 1: DEVROYE, L. 1986. Non-Uniform Random Variate Generation, Springer-Verlag, New York.
• 2: MARSAGLIA, G. 1984. The exact-approximation method for generating random variables. J. Am. Stat. Assoc. 79, 218-221.
• 3: MARSAGLIA, G. 1996. The Marsaglia Random Number CDROM, with the DIEHARD Battery of Tests of Randomness. Department of Statistics, Florida State University. Available by ftp through the Department of Computer Science, Univ. of Hong Kong: http://www.cs.hku.hk/ ftp.html
• 4: MARSAGLIA, G. AND TSANG, W.W. 1984. A fast, easily implemented method for sampling from decreasing or symmetric unimodal density functions. SIAM J. Sci. Stat. Comput. 5, 349-359.
• 5: Do Le Minh, Generating gamma variates, ACM Transactions on Mathematical Software (TOMS), v.14 n.3, p.261-266, Sept. 1988 [doi>10.1145/44128.214382]
• 6: ZECHNER, g. AND STADLOBER, E. 1993. Generating beta variates via patchwork rejection. Computing 50, 1-18.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Theory

Keywords:
Monty Python method, normal variates, t variates, von Mises variates, von mises variates