The patchwork rejection technique for sampling from unimodal distributions

ABSTRACT

We report on both theoretical developments and comutational experience with the patchwork rejection technique in Zechner and Stadlober [1993] and Zechner [1997]. The basic approach is due to Minh [1988], who suggested a special sampling method for the gamma distribution. The method's general objective is to rearrange the area below the density of histogram f (x) in the body of the distribution by certain point reflections such that variates may be generated efficiently within a large center interval. This is carried out via uniform hat functions, combined with minorizing rectangles for immediate acceptance of one transformed uniform deviate. The remaining tails of f(x) are covered by exponential functions. Experiments show that patchwork rejection algorithms are in general faster than their competitors at the cost of higher set-up times.

REFERENCES

• 1: J. H. Ahrens , U. Dieter, Generating gamma variates by a modified rejection technique, Communications of the ACM, v.25 n.1, p.47-54, Jan. 1982 [doi>10.1145/358315.358390]
• 2: J. H. Ahrens , U. Dieter, Computer Generation of Poisson Deviates from Modified Normal Distributions, ACM Transactions on Mathematical Software (TOMS), v.8 n.2, p.163-179, June 1982 [doi>10.1145/355993.355997]
• 3: L. Devroye, A simple generator for discrete log-concave distributions, Computing, v.39 n.1, p.87-91, 1987 [doi>10.1007/BF02307716]
• 4: H RMANN, W. 1992. The transformed rejection method for generating Poisson random variables. Insurance: Math. Econ. 11, 1-7.
• 5: H RMANN, W. 1993. The generation of binomial variates. J. Stat. Comput. Simul. 46, 1/2, 101-110.
• 6: H RMANN, W. 1994. A universal generator for discrete log-concave distributions. Computing 52, 1, 89-96.
• 7: 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]
• 8: W. Hörmann , G. Derflinger, Rejection-inversion to generate variates from monotone discrete distributions, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.6 n.3, p.169-184, July 1996 [doi>10.1145/235025.235029]
• 9: H RMANN, W. AND DERFLINGER, G. 1997. An automatic generator for a large class of unimodal discrete distributions. In ESM97, Gaining Competitive Advantage Through Simulation Technologies, A. R. Kaylan and A. Lehmann, Eds. 139-144.
• 10: KACHITVICHYANUKUL, V. AND SCHMEISER, B.W. 1985. Computer generation of hypergeometric random variates. J. Stat. Comput. Simul. 22, 1, 127-145.
• 11: Voratas Kachitvichyanukul , Bruce W. Schmeiser, Binomial random variate generation, Communications of the ACM, v.31 n.2, p.216-222, Feb. 1988 [doi>10.1145/42372.42381]
• 12: A. W. Kemp, Patchwork rejection algorithms, Journal of Computational and Applied Mathematics, v.31 n.1, p.127-131, July 1990 [doi>10.1016/0377-0427(90)90343-X]
• 13: Do Le Minh, Generating gamma variates, ACM Transactions on Mathematical Software (TOMS), v.14 n.3, p.261-266, Sept. 1988 [doi>10.1145/44128.214382]
• 14: SAKASEGAWA, H. 1983. Stratified rejection and squeeze method for generating beta random numbers. Annual Institute Statistical Math. 35, B, 291-302.
• 15: SCHMEISER, B. W. AND BABU, A. J. G. 1980. Beta variate generation via exponential majorizing functions. Oper. Res. 28, 4, 917-926. (Errata: Oper. Research 31, 1983, 802).
• 16: SCHMEISER, B. W. AND LAL, R. 1980. Squeeze methods for generating gamma variates. J. Am. Stat. Assoc. 75, 371, 675-682.
• 17: STADLOBER, E. 1989. Sampling from Poisson, binomial, and hypergeometric distributions: ratio of uniforms as a simple and fast alternative. Math. Statist. Sektion 303. Forschungsgesellschaft Joanneum, Graz, Austria.
• 18: E. Stadlober, The ratio of uniforms approach for generating discrete random variates, Journal of Computational and Applied Mathematics, v.31 n.1, p.181-189, July 1990 [doi>10.1016/0377-0427(90)90349-5]
• 19: STADLOBER, E. AND PIOK, M. 1995. WinRand 1.0/95.: Accessible by anonymous ftp from statistik.tu-graz, ac. at \ winrand.
• 20: ZECHNER, H. AND STADLOBER, E. 1993. Generating beta variates via patchwork rejection. Computing 50, 1, 1-18.
• 21: ZECHNER, H. 1997. Efficient sampling from continuous and discrete unimodal distributions. Ph.D. Dissertation. Technical University Graz, Graz, Austria.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation; Statistical software

General Terms:
Algorithms, Performance, Reliability

Keywords:
patchwork rejection, random variate generation, random variate transformations, sampling techniques, stochastic simulation, unimodal distributions