Automatic generation of non-uniform random variates for arbitrary pointwise computable probability densities by tiling
For practitioners needing automatic random variate generation from arbitrary densities, this method offers a fast, unattended solution with minimal setup.
The paper introduces a rejection method for generating non-uniform random variates from arbitrary pointwise computable probability densities, using recursive tiling to achieve fast generation with short setup time. Benchmarks show it outperforms similar rejection and transformation methods.
We present a rejection method based on recursive covering of the probability density function with equal tiles. The concept works for any probability density function that is pointwise computable or representable by tabular data. By the implicit construction of piecewise constant majorizing and minorizing functions that are arbitrarily close to the density function the production of random variates is arbitrarily independent of the computation of the density function and extremely fast. The method works unattended for probability densities with discontinuities (jumps and poles). The setup time is short, marginally independent of the shape of the probability density and linear in table size. Recently formulated requirements to a general and automatic non-uniform random number generator are topped. We give benchmarks together with a similar rejection method and with a transformation method.