A Simple Universal Generator for Continuous and Discrete Univariate T-concave Distributions

Josef Leydold


We use inequalities to design short universal algorithms that can be used to generate random variates from large classes of univariate continuous or discrete distributions (including all log-concave distributions). The expected time is uniformly bounded over all these distributions. The algorithms can be implemented in a few lines of high level language code. In opposition to other black-box algorithms hardly any setup step is required and thus it is superior in the changing parameter case.

CR Categories and Subject Descriptors: G.3 [Probability and Statistics]: Random number generation

Mathematics Subject Classification: 65C10 (Random Number Generation); 65U05 (Numerical methods in probability and statistics), 11K45 (Pseudo-random numbers, Monte Carlo methods)

General Terms: Algorithms

Key Words: non-uniform random variates, universal method, ratio-of-uniforms method, transformed density rejection, discrete distributions, continuous distributions, log-concave distributions, T-concave distributions

Download Preprint
© ACM, (2001). This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Trans. Math. Softw. 27(1), 66-83. http://doi.acm.org/10.1145/382043.382322