skip to main content
article

Universal nonuniform random vector generator based on acceptance-rejection

Published: 01 July 2005 Publication History

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]
Aurenhammer, F. 1991. Voronoi diagrams---a survey of a fundamental data structure. ACM Comput. Surve. 23, 345--405.]]
[2]
Batten, L. and Beliakov, G. 2002. Fast algorithm for the cutting angle method of global optimization. J. Global Optim. 24, 149--161.]]
[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]
Hörmann, W. 1995. A rejection technique for sampling from t-concave distributions. ACM Trans. Math. Soft. 21, 182--193.]]
[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]
Leydold, J. and Hörmann, W. 1998. A sweep-plane algorithm for generating random tuples in simple polytopes. Math. Computation 67, 1617--1635.]]
[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]
Mladineo, R. 1986. An algorithm for finding the global maximum of a multimodal, multivariate function. Math. Progr. 34, 188--200.]]
[21]
Okabe, A., Boots, B., Sugihara, K., and Chiu, S. N. 2000. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd ed. John Wiley, Chichester.]]
[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]
Sio, K. and Lee, C. 1997. Estimation of the Lipschitz norm with neural networks. Neural Processing Letters 6, 99--108.]]
[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.]]

Cited By

View all
  • (2024)Global Optimization: Cutting Angle MethodEncyclopedia of Optimization10.1007/978-3-030-54621-2_229-1(1-9)Online publication date: 8-May-2024
  • (2022)Robust aggregation of compositional and interval-valued data: The mode on the unit simplexFuzzy Sets and Systems10.1016/j.fss.2021.01.007446(124-143)Online publication date: Oct-2022
  • (2020)Density estimates on the unit simplex and calculation of the mode of a sampleInternational Journal of Intelligent Systems10.1002/int.2222735:5(850-868)Online publication date: 20-Feb-2020
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Computer Simulation
ACM Transactions on Modeling and Computer Simulation  Volume 15, Issue 3
July 2005
105 pages
ISSN:1049-3301
EISSN:1558-1195
DOI:10.1145/1103323
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2005
Published in TOMACS Volume 15, Issue 3

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Acceptance/rejection
  2. Lipschitz approximation
  3. nonuniform random variates
  4. random number generator

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Global Optimization: Cutting Angle MethodEncyclopedia of Optimization10.1007/978-3-030-54621-2_229-1(1-9)Online publication date: 8-May-2024
  • (2022)Robust aggregation of compositional and interval-valued data: The mode on the unit simplexFuzzy Sets and Systems10.1016/j.fss.2021.01.007446(124-143)Online publication date: Oct-2022
  • (2020)Density estimates on the unit simplex and calculation of the mode of a sampleInternational Journal of Intelligent Systems10.1002/int.2222735:5(850-868)Online publication date: 20-Feb-2020
  • (2015)SKIRT: The design of a suite of input models for Monte Carlo radiative transfer simulationsAstronomy and Computing10.1016/j.ascom.2015.05.00612(33-44)Online publication date: Sep-2015
  • (2008)Optimal Expected-Distance Separating HalfspaceMathematics of Operations Research10.1287/moor.1070.030933:3(662-677)Online publication date: Aug-2008
  • (2008)Handling Uncertainty in Agile Requirement Prioritization and Scheduling Using Statistical SimulationProceedings of the Agile 200810.1109/Agile.2008.79(73-82)Online publication date: 4-Aug-2008
  • (2008)Global Optimization: Cutting Angle MethodEncyclopedia of Optimization10.1007/978-0-387-74759-0_229(1304-1311)Online publication date: 2008

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media