Rejection-inversion to generate variates from monotone discrete distributions

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.

REFERENCES

• 1: BARINGHAUS, L. 1989. A note on a rejection method for generating random variates from the discrete pareto distribution. Utilitas Math. 35, 65-66.
• 2: DAGPUNAR, J. 1988. Principles of Random Variate Generation. Clarendon Press, Oxford, U.K.
• 3: DEVROYE, L. 1986. Non-Uniform Random Variate Generation. Springer-Verlag, New York.
• 4: Wolfgang Hörmann, A rejection technique for sampling from T-concave distributions, ACM Transactions on Mathematical Software (TOMS), v.21 n.2, p.182-193, June 1995 [doi>10.1145/203082.203089]
• 5: HORMANN, W. 1994. A universal generator for discrete log-concave distributions. Computing 52, 89-96.
• 6: JOHNSON, N. L., KOTZ, S., AND KEMP, A. W. 1992. Univariate Discrete Distributions. 2nd edition, Wiley, New York.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Algorithms

Keywords:
T-concave, Zipf distribution, rejection method, tail of Poisson distribution, universal algorithm