The automatic generation of one- and multi-dimensional distributions with transformed density rejection

Josef Leydold and Wolfgang Hörmann


A rejection algorithm, called ``transformed density rejection'', is presented. It uses a new method for constructing simple hat functions for a unimodal density $f$. It is based on the idea of transforming $f$ with a suitable transformation $T$ such that $T(f(x))$ is concave. The hat function is then constructed by taking the pointwise minimum of tangents which are transformed back to the original scale. The resulting algorithm works very well for a large class of distributions and is fast. The method is also extended to the two- and multidimensional case.

Mathematics Subject Classification: 65C10 (Random Number Generation)

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

General Terms: Algorithms

Key Words: random number generation, rejection method, log-concave density

Download Preprint