Universal nonuniform random vector generator based on acceptance-rejection

ABSTRACT

The acceptance/rejection approach is widely used in universal nonuniform random number generators. Its key part is an accurate approximation of a given probability density from above by a hat function. This article uses a piecewise constant hat function, whose values are overestimates of the density on the elements of the partition of the domain. It uses a sawtooth overestimate of Lipschitz continuous densities, and then examines all local maximizers of such an overestimate. The method is applicable to multivariate multimodal distributions. It exhibits relatively short preprocessing time and fast generation of random variates from a very large class of distributions.

REFERENCES

• 1: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 2: L. M. Batten , G. Beliakov, Fast Algorithm for the Cutting Angle Method of Global Optimization, Journal of Global Optimization, v.24 n.2, p.149-161, October 2002 [doi>10.1023/A:1020256900863]
• 3: Beliakov, G. 2003. Geometry and combinatorics of the cutting angle method. Optim. 52, 4-5, 379--394.
• 4: Beliakov, G. 2005. Extended cutting angle method of constrained global optimization. In Optimization in Industry, L. Caccetta, Ed. Springer, Heidelberg, in press.
• 5: Bern, M. and Eppstein, D. 1992. Mesh generation and optimal triangulation. In Computing in Euclidean Geometry, D.-Z. Du and F. Hwang, Eds. World Scientific, Singapore, 23--90.
• 6: Boissonnat, J.-D., Sharir, M., Tagansky, B., and Yvinec, M. 1998. Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete Comput. Geom. 19, 485--519.
• 7: Büeler, B., Enge, A., and Fukuda, K. 2000. Exact volume computation for convex polytopes: A practical study. In Polytopes---Combinatorics and Computation, G. Kalai and G. M. Ziegler, Eds. Birkhäuser, Basel, 131--154.
• 8: Dagpunar, J. 1988. Principles of Random Variate Generation. Clarendon Press, Oxford.
• 9: Demyanov, V. and Rubinov, A. 1995. Constructive Nonsmooth Analysis. Peter Lang, Frankfurt am Main.
• 10: Devroye, L. 1986. Nonuniform Random Variate Generation. Springer Verlag, New York.
• 11: Evans, M. and Swartz, T. 1998. Random variable generation using concavity properties of the transformed densities. J. Computat. Graph. Stat. 7, 4, 514--528.
• 12: Hansen, P. and Jaumard, B. 1995. Lipschitz optimization. In Handbook of Global Optimization, R. Horst and P. Pardalos, Eds. Kluwer, Dordrecht, 407--493.
• 13: 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]
• 14: Hörmann, W., Leydold, J., and Derflinger, G. 2004. Automatic Nonuniform Random Variate Generation. Springer, Berlin.
• 15: Horst, R., Pardalos, P., and Thoai, N. 2000. Introduction to Global Optimization, 2nd ed. Kluwer Academic Publishers, Dordrecht.
• 16: Lay, S. 1972. Convex Sets and their Applications. Wiley, New York.
• 17: Josef Leydold , Wolfgang Hörmann, A sweep-plane algorithm for generating random tuples in simple polytopes, Mathematics of Computation, v.67 n.224, p.1617-1635, Oct. 1998 [doi>10.1090/S0025-5718-98-01004-7]
• 18: Leydold, J. and Hörmann, W. 2001. Universal algorithms as an alternative for generating nonuniform continuous random variates. In Monte Carlo Simulation, G. Schuëler and P. Spanos, Eds. A. A. Balkema, Rotterdam, 177--183.
• 19: Luescher, M. 1994. A portable high-quality random number generator for lattice field theory calculations. Comput. Phys. Comm. 79, 100--110.
• 20: F H Mladineo, An algorithm for finding the global maximum of a multimodal, multivariate function, Mathematical Programming: Series A and B, v.34 n.2, p.188-200, March 1986 [doi>10.1007/BF01580583]
• 21: Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
• 22: Rockafellar, R. 1970. Convex Analysis. Princeton University Press, Princeton.
• 23: Rubinov, A. 2000. Abstract Convexity and Global Optimization. Kluwer Academic Publishers, Dordrecht; Boston.
• 24: Sergeyev, Y. D. 2004. Finding the minimal root of an equation: applications and algorithms based on Lipschitz condition. In Global Optimization---Selected Case Studies, J. Pintér, Ed. Kluwer Academic Publishers, in press.
• 25: K. C. Sio , C. K. Lee, Estimation of the Lipschitz Norm with Neural Networks, Neural Processing Letters, v.6 n.3, p.99-108, Dec. 1997 [doi>10.1023/A:1009667824060]
• 26: Strongin, R. G. and Sergeyev, Y. D. 2000. Global Optimization with Non-convex Constraints: Sequential and Parallel Algorithms. Kluwer Academic Publishers, Dordrecht; London.
• 27: Walker, A. 1974. New fast method for generating discrete random numbers with arbitrary frequency distributions. Electron. Lett. 10, 127--128.
• 28: Wolfe, P. 1976. Finding the nearest point in a polytope. Math. Progr. 11, 128--149.
• 29: Wood, G. R. and Zhang, B. 1996. Estimation of the Lipschitz constant of a function. J. Global Optim. 8, 91--103.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

General Terms:
Algorithms

Keywords:
Acceptance/rejection, Lipschitz approximation, nonuniform random variates, random number generator