RANDOM NUMBER GENERATION (LUC DEVROYE)


PAPERS TO DOWNLOAD

L. Devroye, J. Fill and R. Neininger, Perfect Simulation from the Quicksort Limit Distribution, Electronic Communications in Probability, vol. 5, pp. 95-99, 2000. PDF file. Technical Report #603, Department of Mathematical Sciences, The Johns Hopkins University. We show how to generate a random variable from the quicksort limit distribution (for which only a distributional identity is known).
L. Devroye and R. Neininger, Density approximation and exact simulation of random variables that are solutions of fixed-point equations, Advances in Applied Probability, 2002, to appear. (PDF version). An algorithm is developed for the exact simulation from distributions that are defined as fixed-points of maps between spaces of probability measures. The fixed-points of the class of maps under consideration include examples of limit distributions of random variables studied in the probabilistic analysis of algorithms. The sampling algorithm relies on a modified rejection method.
L. Devroye, Simulating perpetuities Methodologies and Computing in Applied Probability, vol. 3, pp. 97-115, 2001. (PDF version). A perpetuity is a random variable that can be represented as $1+ W_1 + W_1 W_2 + W_1 W_2 W_3 + \cdots$, where the $W_i$'s are i.i.d.\ random variables. We study exact random variate generation for perpetuities and discuss the expected complexity. For the Vervaat family, in which $W_1 \inlaw U^{1/\beta}$, $\beta > 0$, $U$ uniform $[0,1]$, all the details of a novel rejection method are worked out. There exists an implementation of our algorithm that only uses uniform random numbers, additions, multiplications and comparisons.
L. Devroye, Random variate generation in one line of code, 1996 Winter Simulation Conference Proceedings, J.M. Charnes, D.J. Morrice, D.T. Brunner and J.J. Swain eds, ACM, pp. 265-272, 1996. (PDF version). For many distributions, it is possible to generate a random variate in one assignment statement using only simple mathematical functions and ordinary arithmetic operations.
L. Devroye, Simulating Bessel random variables, 2002. To appear in Statistics and Probability Letters. (PDF version). This paper develops a uniformly fast algorithm for generating random variates from the Bessel distribution. No Bessel function or Bessel ratio is needed.
L. Devroye, On random variate generation when only moments or Fourier coefficients are known, Mathematics and Computers in Simulation, vol. 31, pp. 71-89, 1989. We consider algorithms for generating random variates having a density, when only its Fourier coefficients or moments are known. We also study the expected time per random variate.
L. Devroye, Simulating theta random variates, Statistics and Probability Letters, vol. 31, pp. 275-2791, 1997. We develop an exact simple random variate generator for the theta distribution, which occurs as the limit distribution of the height of nearly all models of uniform random trees. Even though the density is only known as an infinite sum of functions, our algorithm does not require any summation.
L. Devroye, Random variate generation for the digamma and trigamma distributions, Journal of Statistical Computation and Simulation, vol. 43, pp. 197-216, 1992. We derive uniformly fast random variate generators for Sibuya's digamma and trigamma families. Some of these generators are based upon the close resemblance between these distributions and selected generalized hypergeometric distributions. The generators can also be used for the discrete stable distribution, the Yule distribution, Mizutani's distribution and the Waring distribution.
L. Devroye, On random variate generation for the generalized hyperbolic secant distributions, Statistics and Computing, vol. 3, pp. 125-134, 1993. We give random variate generators for the generalized hyperbolic secant distribution and related families such as Morris's skewed generalized hyperbolic secant family and a family introduced by Laha and Lukacs. The rejection method generators are uniformly fast over the parameter space and are based upon a complex function representation of the distributions due to Harkness and Harkness.
L. Devroye, A triptych of discrete distributions related to the stable law, Statistics and Probability Letters, vol. 18, pp. 349-351, 1993. We derive useful distributional representations for the discrete stable distribution of Steutel and Van Harn, the discrete Linnik distribution introduced by Pakes, and a discrete distribution of Sibuya. These representations may be used to obtain simple uniformly fast random variate generators.
L. Devroye, Algorithms for generating discrete random variables with a given generating function or a given moment sequence, SIAM Journal on Scientific and Statistical Computing, vol. 12, pp. 107-126, 1991. We present and analyze various algorithms for generating positive integer-valued random variables when the distribution is described either through the generating function or via the sequence of moments.
L. Devroye, Random variate generation for multivariate unimodal densities, ACM Transactions on Modeling and Computer Simulation, vol. 7, pp. 447-477, 1997. A probability density on a finite-dimensional Euclidean space is ortho-unimodal with a given mode if within each orthant (quadrant) defined by the mode, the density is a monotone function of each of its arguments individually. Up to a linear transformation, most of the commonly used random vectors possess ortho-unimodal densities. To generate a random vector from a given ortho-unimodal density, several general-purpose algorithms are presented; and an experimental performance evaluation illustrates the potential efficiency increases that can be achieved by these algorithms versus naive rejection.
L. Devroye, The branching process method in random variate generation, Communications in Statistics---Simulation, vol. 21, pp. 1-14, 1992. The generalized Lagrange probability distributions include the Borel-Tanner distribution, Haight's distribution, the Poisson-Poisson distribution and Consul's distribution, to name a few. We introduce two universally applicable random variate generators for this family of distributions. In the branching process method, we produce the generation sizes in a Galton-Watson branching process. In the uniform bounding method, we employ the rejection method based upon a simple probability inequality that is valid for all members in a given subfamily.

RANDOM NUMBER GENERATION JOURNALS

ACM Transactions on Mathematical Software
ACM Transactions on Modeling and Computer Simulation
INFORMS College on Simulation: go here for the free full version of the Winter Simulation Conference (WSC) Proceedings.

NON-UNIFORM RANDOM NUMBER GENERATION LINKS

winrand 1.0/95 (CRAND) CRAND is the highest quality package (in my opinion) for non-uniform random variate generation, developed and implemented by Ernst Stadlober. In C++.
RANLIB Random number generation package by Brown, Movato and Russell. Here are the files. Download the C or FORTRAN implementations.
Regress+ Mac-based freeware package for fitting models to data. It includes as an essential component a battery of non-uniform random variate generators (currently for 29 distributions, soon for 50). Developed by Michael P. McLaughlin.
Compendium of probability distributions An on-line list of distributions compiled by Mike McLaughlin.
Non-Uniform Random Variate Generation Boris Shukhman has programmed most algorithms from my book in C, but the code is not suitable for general consumption yet. Also, the algorithms are not as fast as those developed by Ernst Stadlober, Wolfgang Hörmann, Jo Ahrens and Ulrich Dieter.
Alan Miller's programs Alan Miller from the CSIRO Mathematical & Information Sciences programmed most algorithms from Non-Uniform Random Variate Generation.
Newran02A A C++ library for generating sequences of random numbers from a wide variety of distributions.
Gaussian random number generator A fast time-correlated gaussian generator. FORTRAN.

(UNIFORM) RANDOM NUMBER GENERATION LINKS

CRM Workshop The "Workshop on random number generators and highly uniform point sets", to be hel June 17-28, 2002, at the CRM in Montreal. Organized by Pierre L'Ecuyer.
Pierre Lecuyer For good uniform random number generators, check out the work by Pierre at the University of Montreal. Pierre L'Ecuyer's papers can be downloaded by ftp or HTML.
Uniform random number generator I get frequently asked for a good reliable uniform random number generator. There is no such universal beast, but the link above lets you download a high quality generator.
RANDPOLY RANDPOLY is a REDUCE-package based on a port of the Maple random polynomial . Has some random number generators.
Quasi-Monte Carlo Methods, Number Theory and Combinatorics Links to combinatorics and quasi Monte Carlo compiled by Wolfgang Schmid at the University of Salzburg.
Numerical analysis FAQ by FTP
University of Salzburg PLAB: random number generation laboratory. Maintained by Karl.Entacher@sbg.ac.at. Has links, lists of researchers, and generic implementations of the linear congruential, inversive congruential, and explicit inversive congruential random number generators in ANSI C. pLab is an object oriented system for generating and testing random numbers written in C++. Get the software from Hannes Leeb.
University of Salzburg Main web page for the Math Department at the University of Salzburg.
Marsaglia's test suite Includes also information on Marsaglia's CDROM full of random bits.
Source for Marsaglia's generators
Mok-Kong Shen Compound pseudo random number generator developed by Shen.
Sabri Pllana's page The history of the Monte Carlo method.
QR Streams This commercial Mathematica-oriented package allows the generation of all major types of quasi-random sequences.
Random Numbers and Monte Carlo Methods The WWW Virtual Library maintained by Karl Entacher.
INFORMS College of Simulation Newsletter
David Wagner's page Page of links maintained by David Wagner at CS in Berkeley. Related to all sorts of ways of generating randomness. Has also some cryptography links.
Skip Carter's random number page Links maintained by Skip Carter at Taygeta Inc.
Bob Jenkins
Links
SG100 140USD hardware random number generator from Bo Domstedt.
Other hardware generators. Hotbits hardware, RBG 1210, ORION's Random Number Generator, ComScire QNG, ComScire QNGADINT.
Random Numbers on the Web: NCSA Lots of great links to random number generation.
The NHSE Guide to Random Number Generators Page maintained by Paul Coddington, Northeast Parallel Architectures Center, Syracuse University.
Michael Hennecke Page on random number generation.
Computer Generated Random Numbers An electronic book by David W. Deley.
Comscire's Bibliography Short list of references.
NHSE Review On random numbers in parallel computers.
Random Master A physical device by Yiu Ly (Rymex Corporation) for generating random numbers through thermal noise inside a semiconductor element.
Research Institute for Theoretical Physics Publications from the Research Institute for Theoretical Physics from the University of Helsinki, Finland. Check also here.
Java applet Java applet for viewing the lattice structure of linear congruential generators.
SPRNG Scalable Parallel Random Number Generators.
Numerical Recipes in C Has the complete Numerical Recipes books in C and Fortran 77 on-line, in both PostScript and Adobe Acrobat formats. Reviews of the Numerical Recipes book.
Mersenne Twister Matsumoto and Nishimura's new generator features a period of 2^19937 - 1, optimal equidistribution properties in dimensions up to 623, and a very fast algorithm.
Blum-Blum-Shub generator An experimental implementation of the cryptographically strong BBS generator using UNIX bc.
TT800 A twisted GFSR generator proposed by Matsumoto and Kurita in the ACM Transactions on Modelling and Computer Simulation, Vol. 4, No. 3, 1994, pp. 254-266. This has a period of 2^800 - 1 and excellent equidistribution properties up to dimension 25. A TGFSR with a period of more than 2^11000, is currently under construction by M. Matsumoto and T. Nishimura.
Los Alamos National Laboratory IMSL routines for random numbers.
Cern Program Library Go to section V for random number generators.
NETLIB Random number generators in FORTRAN and C. Mirror).
National HPCC Software Exchange (NHSE) Random number library.
RANPACK
PMMMLCG A modified version of the random number generator proposed by S.K. Park & K.W. Miller in "Random Number Generators: Good Ones Are Hard to Find", Comm. ACM, 31:1192-1201, 1988.
R250 A generator (in C) from S. Kirkpatrick and E. Stoll, J. Comp. Physics, 40:517, 1981.
rand() A generator from the BSD C library.
random() Another generator from the BSD C library.
Mathlink program
CRAY T3E A very fast long period random number generator for the CRAY T3E. FORTRAN.

CONTACT

Luc Devroye
School of Computer Science
McGill University
Montreal, Canada H3A 2K6
luc@cs.mcgill.ca
http://luc.devroye.org/index.html