Devroye L. Non-Uniform Random Variate Generation

New York: Springer, 1986. - 857p.General outline
About our notation
Definitions
A few important univariate densities
Assessment of random variate generators
Distributions with no variable parameters
Parametric families
Operations on random variables
Transformations
Mixtures
Order statistics
Convolutions Sums of independent random variables
Sums of independent uniform random variables
ExercisesGeneral Principle of Random Numbers GenerationThe inversion method
The inversion principle
Inversion by numerical solution of $F(X)=U$
Explicit approximations
Exercises
The rejection method
Definition
Development of good rejection algorithms
Generalizations of the rejection method
Wald's equation
Letac's lower bound
The squeeze principle
Recycling random variates
Exercises
Decomposition as discrete mixtures
Definition
Decomposition into simple components
Partitions into intervals
The waiting time method for asymmetric mixtures
Polynomial densities on $[,]$
Mixtures with negative coefficients
The acceptance-complement method
Definition
Simple acceptance-complement methods
Acceleration by avoiding the ratio computation
An example : nearly flat densities on $[,]$
ExercisesDiscrete Random VariatesThe inversion methodInversion by truncation of a continuous random variate
Comparison-based inversions
The method of guide tables
Inversion by correction
Exercises
Table look-up methods
The table look-up principle
Multiple table look-ups
The alias method
Definition
The alias-urn method
Geometrical puzzles
Exercises
Other general principles
The rejection method
The composition and acceptance-complement methods
ExercisesSpecialized AlgorithmsMotivation for the chapter
Exercises
The Forsythe-von Neumann method
Description of the method
Von Neumann's exponential random variate generator
Monahan's generalization
An example : Vaduva's gamma generator
Exercises
Almost-exact inversion
Definition
Monotone densities on $[, inf )$
Polya's approximation for the normal distribution
Approximations by simple functions of normal random variates
Exercises
Many-to-one transformations
The principle
The absolute value transformation
The inverse gaussian distribution
Exercises
The series methodDescriptionAnalysis of the alternating series algorithm
Analysis of the convergent series algorithm
The exponential distribution
The Raab-Green distribution
The Kolmogorov-Smirnov distribution
Exercises
Representations of densities as integralsKhinchine's and related theorems
The inverse-of-$f$ method for monotone densities
Convex densities
Recursive methods based upon representations
A representation for the stable distribution
Densities with Polya type characteristic functions
Exercises
The ratio-of-uniforms methodSeveral examples
ExercisesUniform and Exponential SpacingMotivation
Uniform and exponential spacings
Uniform spacings
Exponential spacings
Exercises
Generating ordered samples
Generating uniform $[,]$ order statistics
Bucket sorting Bucket searching
Generating exponential order statistics
Generating order statistics with distribution function F
Generating exponential random variates in batches
Exercises
The polar method
Radially symmetric distributions
Generating random vectors uniformly distributed on $C sub d$
Generating points uniformly in and on $C sub $
Generating normal random variates in batches
Generating radially symmetric random vectors
The deconvolution method
ExercisesThe Poisson ProcessThe Poisson processSimulation of homogeneous Poisson processes
Nonhomogeneous Poisson processes
Global methods for nonhomogeneous Poisson
process simulation
Exercises
Generation of random variates with a given hazard rate
Hazard rate Connection with Poisson processes
The inversion method
The composition method
The thinning method
DHR distributions Dynamic thinning
Analysis of the dynamic thinning algorithm
Exercises
Generating random variates with a given
discrete hazard rateThe sequential test method
Hazard rates bounded away from
Discrete dynamic thinning
ExercisesUniversal MethodsBlack box philosophy
Log-concave densities
Definition
Inequalities for log-concave densities
A black box algorithm
The optimal rejection algorithm
The mirror principle
Non-universal rejection methods
Exercises
Inequalities for families of densities
Motivation
Bounds for unimodal densities
Densities satisfying a Lipschitz condition
Normal scale mixtures
Exercises
The inversion-rejection method
The principle
Bounded densities
Unimodal and monotone densities
Monotone densities on $[,]$
Bounded monotone densities : inversion-rejection
based on Newton-Raphson iterations
Bounded monotone densities : geometrically
increasing interval sizes
Lipschitz densities on $[, inf )$
ExercisesTable Methods for Continous Random VariatesComposition versus rejection
Strip methods
Definition
Example : monotone densities on $[,]$
Other examples
Exercises
Grid methodsGenerating a point uniformly in a compact set $A$
Avoidance problems
Fast random variate generatorsContinuous Univariate DensitiesThe normal density
Definition
The tail of the normal density
Composition/rejection methods
Exercises
The exponential density
Overview
Marsaglia's exponential generator
The rectangle-wedge-tail method
Exercises
The gamma density
The gamma family
Gamma variate generators
Uniformly fast rejection algorithms for $a >= $
The Weibull density
Johnk's theorem and its implications
Gamma variate generators when $a <= $
The tail of the gamma density
Stacy's generalized gamma distribution
Exercises
The beta density
Properties of the beta density
Overview of beta generators
The symmetric beta density
Uniformly fast rejection algorithms
Generators when $min (a,b) <= $
Exercises
The t distribution
Overview
Ordinary rejection methods
The Cauchy density
Exercises
The stable distribution
Definition and properties
Overview of generators
The Bergstrom-Feller series
The series method for stable random variates
Exercises
Nonstandard distributions
Bessel function distributions
The logistic and hyperbolic secant distributions
The von Mises distribution
The Burr distribution
The generalized inverse gaussian distribution
ExercisesDiscrete Univaruate DistributionsGoals of this chapter
Generating functions
Factorials
A universal rejection method
Exercises
The geometric distribution
Definition and genesis
Generators
Exercises
The Poisson distribution
Basic properties
Overview of generators
Simple generators
Rejection methods
Exercises
The binomial distribution
Properties
Overview of generators
Simple generators
The rejection method
Recursive methods
Symmetric binomial random variates
The negative binomial distribution
Exercises
The logarithmic series distributionGenerators
Exercises
The Zipf distribution
A simple generator
The Planck distribution
The Yule distribution
ExercisesMultivariate DistriutionsGeneral principlesThe conditional distribution method
The rejection method
The composition method
Discrete distributions
Exercises
Linear transformations The multinormal distribution
Linear transformations
Generators of random vectors with a
given covariance matrix
The multinormal distribution
Points uniformly distributed in a hyperellipsoid
Uniform polygonal random vectors
Time series
Singular distributions
Exercises
Dependence Bivariate distributions
Creating and measuring dependence
Bivariate uniform distributions
Bivariate exponential distributions
A case study: bivariate gamma distributions
Exercises
The Dirichlet distribution
Definitions and properties
Liouville distributions
Exercises
Some useful multivariate families
The Cook-Johnson family
Multivariate Khinchine mixtures
Exercises
Random matrices
Random correlation matrices
Random orthogonal matrices
Random $R times C$ tables
ExercisesRandom SamplingClassical sampling
The swapping method
Classical sampling with membership checking
Exercises
Sequential sampling
Standard sequential sampling
The spacings method for sequential sampling
The inversion method for sequential sampling
Inversion-with-correction
The ghost point method
The rejection method
Exercises
Oversampling
Definition
Exercises
Reservoir sampling
Definition
The reservoir method with geometric jumps
ExercisesRandom Combinatorial ObjectsGeneral principlesThe decoding method
Generation based upon recurrences
Random permutations
Simple generators
Random binary search trees
Exercises
Random binary trees
Representations of binary trees
Generation by rejection
Generation by sequential sampling
The decoding method
Exercises
Random partitions
Recurrences and codewords
Generation of random partitions
Exercises
Random free trees
Prufer's construction
Klingsberg's algorithm
Free trees with a given number of leaves
Exercises
Random graphs
Random graphs with simple properties
Connected graphs
Tinhofer's graph generators
Bipartite graphs
ExcercisesProbabilistics Shortcuts and Additional TopicsThe maximum of iid random variables
Overview of methods
The quick elimination principle
The record time method
Exercises
Random variates with given moments
The moment problem
Discrete distributions
Unimodal densities and scale mixtures
Convex combinations
Exercises
Characteristic functions
Problem statement
The rejection method for characteristic functions
A black box method
Exercises
The simulation of sums
Problem statement
A detour via characteristic functions
Rejection based upon a local central limit theorem
A local limit theorem
The mixture method for simulating sums
Sums of independent uniform random variables
Exercises
Discrete event simulation
Future event set algorithms
Reeves's model
Linear lists
Tree structures
Exercises
Regenerative phenomena
The principle
Random walks
Birth and death processes
Phase type distributions
Exercises
The generalization of a sample
Problem statement
Sample independence
Consistency of density estimates
Sample indistinguishability
Moment matching
Generators for $f sub n$
ExercisesThe random Bit ModelThe random bit modelSome examples
The Knuth-Yao lower bound
DDG trees
The lower bound
Exercises
Optimal and suboptimal DDG-tree algorithms
Suboptimal DDG-tree algorithms
Optimal DDG-tree algorithms
Distribution-free inequalities for the performance
of optimal DDG-tree algorithms
Exercises