A rejection technique for sampling from T-concave distributions

ABSTRACT

A rejection algorithm that uses a new method for constructing simple hat functions for a unimodal, bounded density f is introduced called “transformed density rejection.” It is based on the idea of transforming f with a suitable transformation T such that T(f(x)) is concave. f is then called T-concave, and tangents of T(f(x)) in the mode and in a point on the left and right side are used to construct a hat function with a table-mountain shape. It is possible to give conditions for the optimal choice of these points of contact. With T= -1/xxx, the method can be used to construct a universal algorithm that is applicable to a large class of unimodal distributions, including the normal, beta, gamma, and t-distribution.

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: AHRENS, J. H. ANn KOHRT, K.D. 1981. Computer methods for sampling from largely arbitrary statistical distributions. Computing 26, 19-31.
• 3: ATKINSON, A.C. 1982. The simulation of generalized inverse gaussian and hyperbolic random variables. SIAM J. Sci. Star. Comput. 3, 502-515.
• 4: CHENG, R. C.H. 1977. The generation of gamma variables with non-integral shape parameter. Appl. Stat. 26, 71-75.
• 5: R. C. H. Cheng, Generating beta variates with nonintegral shape parameters, Communications of the ACM, v.21 n.4, p.317-322, April 1978 [doi>10.1145/359460.359482]
• 6: L. Devroye, A simple generator for discrete log-concave distributions, Computing, v.39 n.1, p.87-91, 1987 [doi>10.1007/BF02307716]
• 7: DEVROYE, L. 1986. Non-Uniform Random Variate Generation. Springer-Verlag, New York.
• 8: U. Dieter, Mathematical aspects of various methods for sampling from classical distributions, Proceedings of the 21st conference on Winter simulation, p.477-483, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76800]
• 9: GILKS, W. R. AND WILD, P. 1992. Adaptive rejection sampling for gibbs sampling. Appl. Stat. 41,337-348.
• 10: HSRMANN, W. 1994. A universal generator for discrete log-concave distributions. Computing 52, 89-96.
• 11: H~RMANN, W. AND DERFLINGER, G. 1990. The ACR method for generating normal random variables. OR Spektrum 12, 181-185.
• 12: JOHNSON, N. L. AND KOTZ, S. 1970. Continuous Univariate Distributwns. Vol. 1. John Wiley, New York.
• 13: JORGENSEN, B. 1982. Statistical Properties of the Generalized Inverse Gaussian Distribution. Lecture Notes in Statistics, vol. 9. Springer, Berlin.
• 14: KACHITVlCHYANUKUL, V. AND SCHMEISER, B.W. 1985. Computer generation of hypergeometric random variates. J. Stat. Comput. Simul. 22, 127-145.
• 15: A. J. Kinderman , J. F. Monahan, Computer Generation of Random Variables Using the Ratio of Uniform Deviates, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.257-260, Sept. 1977 [doi>10.1145/355744.355750]
• 16: KINDERMAN, A. J. AND MONAHAN, F. J. 1980. New methods for generating student's t and gamma variables. Computing 25, 369-377.
• 17: MARSAGLIA, G. AND TSANG, W.W. 1984. A fast, easily implemented method for sampling from decreasing or symmetric unimodal density functions. SIAM J. Sci. Star. Comput. 5, 349-359.
• 18: SCHMEISER, B. W. AND BABU, A. J.G. 1980. Beta variate generation via exponential majorizing functions. Oper. Res. 28, 917-926.
• 19: SCHMEISER, B. W. AND LAL, R. 1980. Squeeze methods for generating gamma variates. J. Am. Stat. Assoc. 75, 679-682.
• 20: S. Stefănescu , I. Văduva, On computer generation of random vectors by transformation of uniformly distributed vectors, Computing, v.39 n.2, p.141-153, April 1, 1987 [doi>10.1007/BF02310103]
• 21: WAKEFIELD, J. C., GELFAND, A. E., AND SMITH, A. F.M. 1991. Efficient generation of random variates via the ratio-of-uniforms method. Stat. Comput. 1, 129-133.
• 22: ZECHNER, H. AND STADLOBER, E. 1993. Generating beta variates via patchwork rejection. Computing 50, 1-18.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
log-concave distributions, rejection method, universal method