Rejection-inversion to generate variates from monotone discrete distributions
Authors:
Open Access
- 1 July 1996
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Modeling and Computer Simulation
- Vol. 6 (3) , 169-184
Abstract
For discrete distributions a variant of reject from a continuous hat function is presented. The main advantage of the new method, called rejection-inversion , is that no extra uniform random number to decide between acceptance and rejection is required, which means that the expected number of uniform variates required is halved. Using rejection-inversion and a squeeze, a simple universal method for a large class of monotone discrete distributions is developed. It can be used to generate variates from the tails of most standard discrete distributions. Rejection-inversion applied to the Zipf (or zeta) distribution results in algorithms that are short and simple and at least twice as fast as the fastest methods suggested in the literature.Keywords
This publication has 3 references indexed in Scilit:
- A rejection technique for sampling from T -concave distributionsACM Transactions on Mathematical Software, 1995
- A universal generator for discrete log-concave distributionsComputing, 1994
- Non-Uniform Random Variate Generation1986