A note on the quality of random variates generated by the ratio of uniforms method

ABSTRACT

The one-dimensional distribution of pseudorandom numbers generated by the ratio of uniforms method using linear congruential generators (LCGs) as the source of uniform random number is investigated in this note. Due to the two-dimensional lattice structure of LCGs there is always a comparable large gap without a point in the one-dimensional distribution of any ratio of uniforms method. Lower bounds for these probabilities only depending on the modulus and the Beyer quotient of the LCG are proved for the case that Cauchy normal or exponential random numbers are generated. These bounds justify the recommendation not to use the ratio of uniform method combined with LCGs.

REFERENCES

• 1: L. Afflerbach, Criteria for the assessment of random number generators, Journal of Computational and Applied Mathematics, v.31 n.1, p.3-10, July 1990 [doi>10.1016/0377-0427(90)90330-3]
• 2: AFFLERBACH, L. 1990b. Die gfitebewertung von pseudo-zufallszahlen-generatoren aufgrund theoretischer analysen und algorithmischer berechnungen. Grazer Mathematische ~Berichte Nr. 309, Graz. In German.
• 3: AFFLERBACH, L. AND H6RMANN, W. 1992. Nonuniform random numbers: A sensitivity analysis for transformation methods. In the Internatwnal Workshop on Computatwnally Intensive Methods in Simulatwn and Optimtzation. Lecture Notes in Economics Mathematics Systems, vol. 374. Springer-Verlag, New York.
• 4: AFFLERBACH, L. AND WENZEL, K. 1988. Normal random numbers lying on spirals and clubs. Stat. Papers 29, 237-244.
• 5: DENG, L.Y. 1988. Robustness study of some random variate generators. In Computer Science and Stattstics: 20th Symposium on the Interface, eds. E. J. Wegman et al., 624 626.
• 6: DEVROYE, L. 1986. Non-Uniform Random Variate Generation, Springer-Verlag, New York.
• 7: U. Dieter, Mathematical aspects of various methods for sampling from classical distributions, Proceedings of the 21st conference on Winter simulation, p.477-483, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76800]
• 8: George A Fishman , Louis R Moore, III, An exhaustive analysis of multiplicative congruential random number generators with modulus 2³¹-1, SIAM Journal on Scientific and Statistical Computing, v.7 n.1, p.24-45, Jan. 1986 [doi>10.1137/0907002]
• 9: H(~RMANN, W. AND DERFLINGER, G. 1991. The transformed rejection method for generating random variables, an alternative to the ratio of uniforms method. Manuskript, Institut f. Statistik, Wirtschaftsuniversit~t Wien, Vienna, Austria.
• 10: A. J. Kinderman , J. F. Monahan, Computer Generation of Random Variables Using the Ratio of Uniform Deviates, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.257-260, Sept. 1977 [doi>10.1145/355744.355750]
• 11: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 12: KUIPERS, L. AND NIEDERREITER, H. 1974. Uniform Dlstrtbutton of Sequences Wiley, New York.
• 13: P. L'Ecuyer, Efficient and portable combined random number generators, Communications of the ACM, v.31 n.6, p.742-751, June 1988 [doi>10.1145/62959.62969]
• 14: LEWIS, P. A., GOODMAN, A. S., AND MILLER, J.M. 1969. A pseudo-random number generator for the system/360. IBM Syst. J. 8, 2, 136-146.
• 15: MARSAGLIA, G. 1972. The structure of linear congruential sequences In Apphcations of Number Theory to Numerical Analysts. Academic Press, New York, 249 286.
• 16: NEAVE, R. 1973. On using the Box-Muller transformatmn with multiplicative congruential pseudo-random number generators. Appl. Stattst. 22, 1, 92 97.
• 17: NIEDERREITER, H. 1978. Quasi-Monte Carlo methods and pseudo-random numbers. Bull. Am. Math. Soc. 84, 6, 957 1041.
• 18: S. K. Park , K. W. Miller, Random number generators: good ones are hard to find, Communications of the ACM, v.31 n.10, p.1192-1201, Oct. 1988 [doi>10.1145/63039.63042]
• 19: B. D. Ripley, Uses and abuses of statistical simulation, Mathematical Programming: Series A and B, v.42 n.1, p.53-68, April 1988 [doi>10.1007/BF01589392]
• 20: STADLOBER, E. 1989 Sampling from Poisson, binomial and hypergeometnc distributions: Ratio of uniforms as a simple and fast alternative. Berichte der Math.-Stat. Sektion in der Forschungsgesellschaft Joanneum, Nr. 303, Graz.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Algorithms

Keywords:
discrepancy, linear congruential generator, ratio of uniforms method