|
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.
|
|
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.
|
