Abstract
The fields of probability and statistics are built over the abstract concepts of probability space and random variable. This has given rise to elegant and powerful mathematical theory, but exact implementation of these concepts on conventional computers seems impossible. In practice, random variables and other random objects are simulated by deterministic algorithms. The purpose of these algorithms is to produce sequences of numbers or objects whose behavior is very hard to distinguish from that of their “truly random” counterparts, at least for the application of interest. Key requirements may differ depending on the context.For Monte Carlo methods, the main goal is to reproduce the statistical properties on which these methods are based, so that the Monte Carlo estimators behave as expected, whereas for gambling machines and cryptology, observing the sequence of output values for some time should provide no practical advantage for predicting the forthcoming numbers better than by just guessing at random.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aiello, W., Rajagopalan, S., Venkatesan, R.: Design of practical and provably good random number generators. J. Algorithm. 29(2), 358–389 (1998)
Asmussen, S., Glynn, P.W. Stochastic simulation, Springer, New York (2007)
Blum, L., Blum, M., Schub, M.: A simple unpredictable pseudo-random number generator. SIAM J. Comput. 15(2), 364–383 (1986)
Bratley, P., Fox, B.L., Schrage, L.E.: A Guide to Simulation. (2nd edn.), Springer, New York, NY (1987)
Brown, M., Solomon, H.: On combining pseudorandom number generators. Ann. Stat. 1, 691–695 (1979)
Chen, H.C., Asau, Y.: On generating random variates from an empirical distribution. AIEE Trans. 6, 163–166 (1974)
Cheng, R.C.H.: Random variate generation. In: Banks, J. (eds.) Handbook of Simulation, pp. 139–172. Wiley (1998); chapter 5.
Collings, B.J.: Compound random number generators. J. Am. Stat. Assoc. 82(398), 525–527 (1987)
Conway, J.H., Sloane, N.J.A.: Sphere packings, lattices and groups. (3rd edn.) Grundlehren der Mathematischen Wissenschaften 290. Springer, New York (1999)
Couture, R., L’Ecuyer, P.: On the lattice structure of certain linear congruential sequences related to AWC/SWB generators. Math. Comput. 62(206), 798–808 (1994)
Couture, R., L’Ecuyer, P.: Orbits and lattices for linear random number generators with composite moduli. Math. Comput. 65(213), 189–201 (1996)
Couture, R., L’Ecuyer, P.: Distribution properties of multiply-with-carry random number generators. Math. Comput. 66(218), 591–607 (1997)
Couture, R., L’Ecuyer, P.: Lattice computations for random numbers. Math. Comput. 69(230), 757–765 (2000)
Deng, L.-Y.: Efficient and portable multiple recursive generators of large order. ACM Trans. Model. Comput. Simulat. 15(1), 1–13 (2005)
Deng, L.-Y., George, E.O.: Generation of uniform variates from several nearly uniformly distributed variables. Comm. Stat. B19(1), 145–154 (1990)
Deng, L.-Y., Lin, D.K.J.: Random number generation for the new century. Am. Stat. 54(2), 145–150 (2000)
Deng, L.-Y., Xu, H.: A system of high-dimensional, efficient, long-cycle and portable uniform random number generators. ACM Trans. Model. Comput. Simulat. 13(4), 299–309 (2003)
Devroye, L.: Non-uniform Random Variate Generation, Springer, New York, NY (1986)
Devroye, L.: Nonuniform random variate generation. In: Simulation, Henderson, S.G., Nelson, B.L. (eds.) Handbooks in Operations Research and Management Science, pp. 83–121. Elsevier, Amsterdam, Netherlands (2006); Chapter 4.
Eichenauer-Herrmann, J.: Pseudorandom number generation by nonlinear methods. Int. Stat. Rev. 63, 247–255 (1995)
Eichenauer-Herrmann, J., Herrmann, E., Wegenkittl, S.: A survey of quadratic and inversive congruential pseudorandom numbers. In: Hellekalek, P., Larcher, G., Niederreiter, H., Zinterhof, P. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 1996, Lecture Notes in Statistics, vol. 127, pp. 66–97. Springer, New York, NY (1998)
Evans, M., Swartz, T.: Approximating Integrals via Monte Carlo and Deterministic Methods, Oxford University Press, Oxford, UK (2000)
Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comput. 44, 463–471 (1985)
Fishman, G.S.: Monte Carlo: Concepts, Algorithms, and applications. Springer Series in Operations Research. Springer, New York, NY (1996)
Gentle, J.E.: Random Number Generation and Monte Carlo methods. (2nd edn.), Springer, New York, NY (2003)
Goresky, M., Klapper, A.: Efficient multiply-with-carry random number generators with maximal period. ACM Trans. Model. Comput. Simulat. 13(4), 310–321 (2003)
Hellekalek, P., Wegenkittl, S.: Empirical evidence concerning AES. ACM Trans. Model. Comput. Simulat. 13(4), 322–333 (2003)
Hörmann, W., Leydold, J.: Dec. Automatic random variate generation for simulation input. In: Joines, J.A., Barton, R.R., Kang, K., Fishwick, P.A. (eds.) In: Proceedings of the 2000 Winter Simulation Conference, pp. 675–682. IEEE Press, Pistacaway, NJ (2000)
Hörmann, W., Leydold, J.: Continuous random variate generation by fast numerical inversion. ACM Trans. Model. Comput. Simulat. 13(4), 347–362 (2003)
Hörmann, W., Leydold, J., Derflinger, G.: Automatic Nonuniform Random Variate Generation. Springer, Berlin (2004)
Kinderman, A.J., Monahan, J.F.: Computer generation of random variables using the ratio of uniform deviates. ACM Trans. Math. Software 3, 257–260 (1977)
Knuth, D.E.: The art of Computer Programming, Seminumerical Algorithms, vol. 2, (3rd edn.) Addison-Wesley, Reading, MA (1998)
Kronmal, R.A., Peterson, A.V.: An Acceptance-complement Analogue of the Mixture-plus-acceptance-rejection Method for Generating Random Variables. ACM Trans. Math. Software 10, 271–281 (1984)
Lagarias, J.C.: Pseudorandom numbers. Stat. Sci. 8(1), 31–39 (1993)
Law, A.M., Kelton, W.D.: Simulation Modeling and Analysis. (3rd edn.), McGraw-Hill, New York, NY (2000)
L’Ecuyer, P.: Random numbers for simulation. Comm. ACM 33(10), 85–97 (1990)
L’Ecuyer, P.: Uniform random number generation. Ann. Oper. Res. 53, 77–120 (1994)
L’Ecuyer, P.: Combined multiple recursive random number generators. Oper. Res. 44(5), 816–822 (1996a)
L’Ecuyer, P.: Maximally equidistributed combined Tausworthe generators. Math. Comput. 65(213), 203–213 (1996b)
L’Ecuyer, P.: Bad lattice structures for vectors of non-successive values produced by some linear recurrences. INFORMS J. Comput. 9(1), 57–60 (1997)
L’Ecuyer, P.: Random number generation. In: Banks, J. (eds.) Handbook of Simulation, pp. 93–137. Wiley (1998); chapter 4.
L’Ecuyer, P.: Good parameters and implementations for combined multiple recursive random number generators. Oper. Res. 47(1), 159–164 (1999a)
L’Ecuyer, P.: Tables of linear congruential generators of different sizes and good lattice structure. Math. Comput. 68(225), 249–260 (1999b)
L’Ecuyer, P.: Tables of maximally equidistributed combined LFSR generators. Math. Comput. 68(225), 261–269 (1999c)
L’Ecuyer, P.: Software for uniform random number generation: Distinguishing the good and the bad. In: Proceedings of the 2001 Winter Simulation Conference, pp. 95–105. IEEE Press, Pistacaway, NJ (2001)
L’Ecuyer, P.: Polynomial integration lattices. In: Niederreiter, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2002, pp. 73–98. Springer, Berlin (2004)
L’Ecuyer, P.: SSJ: A Java library for stochastic simulation. Software user’s guide, available at http://www.iro.umontreal.ca/~lecuyer (2008)
L’Ecuyer, P.: Quasi-Monte Carlo methods with applications in finance. Finance Stochast. 13(3), 307–349 (2009)
L’Ecuyer, P., Andres, T.H.: A random number generator based on the combination of four LCGs. Math. Comput. Simul. 44, 99–107 (1997)
L’Ecuyer, P., Blouin, F., Couture, R.: A search for good multiple recursive random number generators. ACM Trans. Model. Comput. Simulat. 3(2), 87–98 (1993)
L’Ecuyer, P., Côté, S.: Implementing a random number package with splitting facilities. ACM Trans. Math. Software 17(1), 98–111 (1991)
L’Ecuyer, P., Couture, R.: An implementation of the lattice and spectral tests for multiple recursive linear random number generators. INFORMS J. Comput. 9(2), 206–217 (1997)
L’Ecuyer, P., Granger-Piché, J.: Combined generators with components from different families. Math. Comput. Simul. 62, 395–404 (2003)
L’Ecuyer, P., Hellekalek, P.: Random number generators: Selection criteria and testing. In: Hellekalek, P., Larcher, G. (eds.) Random and Quasi-Random Point Sets, Lecture Notes in Statistics, vol. 138, pp. 223–265. Springer New York, NY (1998)
L’Ecuyer, P., Lemieux, C.: Variance reduction via lattice rules. Manag. Sci. 46(9), 1214–1235 (2000)
L’Ecuyer, P., Lemieux, C.: Recent advances in randomized quasi-Monte Carlo methods. In: Dror, M., L’Ecuyer, P., Szidarovszky, F. (eds.) Modeling Uncertainty: An Examination of Stochastic Theory, Methods, and Applications, pp. 419–474. Kluwer Academic, Boston (2002)
L’Ecuyer, P., Mandjes, M., Tuffin, B.: Importance sampling and rare event simulation. In: Rubino, G., Tuffin, B. (eds.) Rare Event Simulation Using Monte Carlo Methods, 17–38. Wiley (2009); Chapter 2.
L’Ecuyer, P., Panneton, F.: Construction of equidistributed generators based on linear recurrences modulo 2. In: Fang, K.-T., Hickernell, F.J., Niederreiter, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2000, pp. 318–330. Springer, Berlin (2002)
L’Ecuyer, P., Panneton, F.: F 2-linear random number generators. In: Alexopoulos, C., Goldsman, D.J.R. (eds.) Advancing the Frontiers of Simulation: A Festschrift in Honor of George Samuel Fishman, Wilson, pp. 169–193. Springer, New York (2009)
L’Ecuyer, P., Proulx, R.: Dec. About polynomial-time “unpredictable” generators. In: Proceedings of the 1989 Winter Simulation Conference, pp. 467–476: IEEE Press, New York (1989)
L’Ecuyer, P., Simard, R.: Beware of linear congruential generators with multipliers of the form a = ± 2q ± 2r. ACM Trans. Math. Software 25(3), 367–374 (1999)
L’Ecuyer, P., Simard, R.: On the performance of birthday spacings tests for certain families of random number generators. Math. Comput. Simul. 55(1–3), 131–137 (2001)
L’Ecuyer, P., Simard, R.: TestU01: A C library for empirical testing of random number generators. ACM Trans. Math. Software 33(4), Article 22 (2007)
L’Ecuyer, P., Simard, R., Chen, E.J., Kelton, W.D.: An object-oriented random-number package with many long streams and substreams. Oper. Res. 50(6), 1073–1075 (2002)
L’Ecuyer, P., Simard, R., Wegenkittl, S.: Sparse serial tests of uniformity for random number generators. SIAM J. Sci. Comput. 24(2), 652–668 (2002)
L’Ecuyer, P., Tezuka, S.: Structural properties for two classes of combined random number generators. Math. Comput. 57(196), 735–746 (1991)
L’Ecuyer, P., Touzin, R.: Fast combined multiple recursive generators with multipliers of the form a = ± 2q ± 2r. In: Joines, J.A., Barton, R.R., Kang, K., Fishwick, P.A. (eds.) Proceedings of the 2000 Winter Simulation Conference, pp. 683–689. IEEE Press, Pistacaway, NJ (2000)
L’Ecuyer, P., Touzin, R.: On the Deng-Lin random number generators and related methods. Stat. Comput. 14, 5–9 (2004)
Leeb, H.: Random numbers for computer simulation. Master’s thesis, University of Salzburg (1995)
Lemieux, C., L’Ecuyer, P.: Randomized polynomial lattice rules for multivariate integration and simulation. SIAM J. Sci. Comput. 24(5), 1768–1789 (2003)
Leydold, J.: Automatic sampling with the ratio-of-uniform method. ACM Trans. Math. Software 26(1), 78–98 (2000)
Leydold, J.: UNU.RAN—universal non-uniform random number generators. Available at http://statmath.wu.ac.at/unuran/ (2009)
Luby, M.: Pseudorandomness and cryptographic applications. Princeton: Princeton University Press (1996)
Lüscher, M.: A portable high-quality random number generator for lattice field theory simulations. Comput. Phys. Comm. 79, 100–110 (1994)
Marsaglia, G.: A current view of random number generators. In Computer Science and Statistics, Sixteenth Symposium on the Interface, pp. 3–10. Elsevier Science Publishers, North-Holland, Amsterdam (1985)
Marsaglia, G.: The Marsaglia random number CDROM including the DIEHARD battery of tests of randomness. See http://stat.fsu.edu/pub/diehard (1996)
Marsaglia, G., Zaman, A.: A new class of random number generators. Ann. Appl. Probab. 1, 462–480 (1991)
Marsaglia, G., Zaman, A., Marsaglia, J.C.W.: Rapid evaluation of the inverse normal distribution function. Stat. Probab. Lett. 19, 259–266 (1994)
Matsumoto, M., Kurita, Y.: Twisted GFSR generators. ACM Trans. Model. Comput. Simul. 2(3), 179–194 (1992)
Matsumoto, M., Kurita, Y.: Twisted GFSR generators II. ACM Trans. Model. Comput. Simul. 4(3), 254–266 (1994)
Matsumoto, M., Kurita, Y.: Strong deviations from randomness in m-sequences based on trinomials. ACM Trans. Model. Comput. Simul. 6(2), 99–106 (1996)
Matsumoto, M., Nishimura, T.: Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8(1), 3–30 (1998)
Nelsen, R.B.: An introduction to copulas, Lecture Notes in Statistics. vol. 139, Springer, New York, NY (1999)
Nelson, B.L., Yamnitsky, M.: Input modeling tools for complex problems. In: Proceedings of the 1998 Winter Simulation Conference, pp. 105–112. IEEE Press, Piscataway, NJ (1998)
Niederreiter, H.: Random number generation and quasi-Monte Carlo methods, SIAM CBMS-NSF Regional Conference Series in Applied Mathematics. vol. 63 SIAM, Philadelphia, PA (1992)
Niederreiter, H.: The multiple-recursive matrix method for pseudorandom number generation. Finite Fields Appl. 1, 3–30 (1995)
Niederreiter, H., Shparlinski, I.E.: Recent advances in the theory of nonlinear pseudorandom number generators. In: Fang, K.-T., Hickernell, F.J., Niederreiter, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2000, pp. 86–102. Springer, Berlin (2002)
Nishimura, T.: Tables of 64-bit Mersenne twisters. ACM Trans. Model. Comput. Simul. 10(4), 348–357 (2000)
Panneton, F., L’Ecuyer, P.: Random number generators based on linear recurrences in \({F}_{{2}^{w}}\). In: Niederreiter, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2002, pp. 367–378. Springer, Berlin (2004)
Panneton, F., L’Ecuyer, P.: On the xorshift random number generators. ACM Trans. Model. Comput. Simul. 15(4), 346–361 (2005)
Panneton, F., L’Ecuyer, P., Matsumoto, M.: Improved long-period generators based on linear recurrences modulo 2. ACM Trans. Math. Software 32(1), 1–16 (2006)
Read, T.R.C., Cressie, N.A.C.: Goodness-of-fit statistics for discrete multivariate data. Springer Series in Statistics. Springer, New York, NY (1988)
Rukhin, A., Soto, J., Nechvatal, J., Smid, M., Barker, E., Leigh, S., Levenson, M., Vangel, M., Banks, D., Heckert, A., Dray, J., Vo, S.: A statistical test suite for random and pseudorandom number generators for cryptographic applications. NIST special publication 800-22, National Institute of Standards and Technology (NIST), Gaithersburg, MD, USA (2001); See http://csrc.nist.gov/rng/.
Tausworthe, R.C.: Random numbers generated by linear recurrence modulo two. Math. Comput. 19, 201–209 (1965)
Tezuka, S.: Uniform random numbers: Theory and practice. Kluwer Academic Publishers, Norwell, MA (1995)
Tezuka, S., L’Ecuyer, P.: Efficient and portable combined Tausworthe random number generators. ACM Trans. Model. Comput. Simul. 1(2), 99–112 (1991)
Tezuka, S., L’Ecuyer, P., Couture, R.: On the add-with-carry and subtract-with-borrow random number generators. ACM Trans. Model. Comput. Simul. 3(4), 315–331 (1994)
Tootill, J.P.R., Robinson, W.D., Eagle, D.J.: An asymptotically random Tausworthe sequence. J. ACM 20, 469–481 (1973)
Vattulainen, I., Ala-Nissila, T., Kankaala, K.: Physical models as tests of randomness. Phys. Rev. E 52(3), 3205–3213 (1995)
von Neumann, J.: Various techniques used in connection with random digits. In: A.S.H. et al. (eds.) The Monte Carlo Method, vol. 12, pp. 36–38. National Bureau of Standards, Applied Mathematics Series (1951)
Walker, A.J.: An efficient method for generating discrete random variables with general distributions. ACM Trans. Math. Software 3, 253–256 (1977)
Wang, D., Compagner, A.: On the use of reducible polynomials as random number generators. Math. Comput. 60, 363–374 (1993)
Wegenkittl, S., Matsumoto, M.: Getting rid of correlations among pseudorandom numbers: Discarding versus tempering. ACM Trans. Model. Comput. Simul. 9(3), 282–294 (1999)
Wu, P.-C.: Multiplicative, congruential random number generators with multiplier \(\pm {2}^{{k}_{1}} \pm{2}^{{k}_{2}}\) and modulus 2p − 1. ACM Trans. Math. Software 23(2), 255–265 (1997)
Acknowledgements
This work has been supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) and a Canada Research Chair to the author. Wolfgang Hörmann, Josef Leydold, François Panneton, and Richard Simard made helpful comments and corrections on an earlier draft. The author has been asked to write chapters on Random Number Generation for several handbooks and encyclopedia over the years. Inevitably, there is a large amount of duplication between these chapters.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
L’Ecuyer, P. (2012). Random Number Generation. In: Gentle, J., Härdle, W., Mori, Y. (eds) Handbook of Computational Statistics. Springer Handbooks of Computational Statistics. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21551-3_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-21551-3_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21550-6
Online ISBN: 978-3-642-21551-3
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)