Automatic random variate generation


Type Research Project

Funding Bodies
  • Austrian Science Fund

Duration Oct. 1, 1999 - Sept. 30, 2003

http://statistik.wu-wien.ac.at/arvag/
  • Mathematical Methods in Statistics AE (Former organization)

Tags

Press 'enter' for creating the tag
  • Derflinger, Gerhard (Former researcher) Project Head
  • Hörmann, Wolfgang (Former researcher)
  • Janka, Erich (Former researcher)
  • Leydold, Josef (Details)
  • Tirler, Günter (Former researcher)
 

Abstract (German)

Stochastische Simulationen sind fuer viele Forschungsbereiche und Anwendungen von grosser Bedeutung. Zu ihrer Durchfuehrung ist die Erzeugung von Zufallsvariablen verschiedener Verteilungen eine notwendige Voraussetzung. Daher wurden bereits in den 1950er Jahren erste Ueberlegungen angestellt, wie gleichverteilte und nichtgleichverteilte Zufallszahlen erzeugt werden koennen. Seither sind viele Verfahren fuer Standardverteilungen vorgeschlagen worden, z.B. fuer Normal-, Beta-, Gamma-, Poisson- oder Binomialverteilungen. Fuer diskrete Verteilungen sind zwei automatische (oder universelle) Algorithmen bekannt, die in den meisten Faellen eingesetzt werden koennen: <BR>
Die Alias-Methode und Sequentielle Suche. Automatische Methoden zur Erzeugung von stetigen Zufallsvariablen sind jedoch viel schwieriger zu verwirklichen.
Die Entwicklung in diesem Bereich begann mit Devroye (1986). Ein weiterer interessanter Beitrag stammt vom W.R. Gilks und P. Wild (1992). W. Hoermann (1995) hat die Konzepte von Devroye und Gilks & Wild "Transformed Density Rejection" (TDR), genannt und so erweitert, dass sie fuer eine grosse Klasse von Dichten, die sogenannten T-konkaven Dichten, anwendbar sind.<P>
Die Ziele dieses Projekts sind <UL>
<LI>Optimale Punkte zur Konstruktion von Hutfunktionen der TDR</LI>
<LI>Herleiten von Eigenschaften von T-konkaven Verteilungen</LI>
<LI>Automatische Erzeugung von Ranggroessen</LI>
<LI>Untersuchung der Qualitaet der erzeugten nicht-gleichverteilten (Pseudo-) Zufallszahlen</LI>
<LI>Universelle Generatoren fuer multivariate Verteilungen</LI>
<LI>Programmieren einer Bibliothek mit wichtigen universellen Algorithmen</LI>
<LI>Monographie mit einer Zusammenfassung von universellen Methoden</LI>
<LI>Anwendungen</LI></UL>


Abstract (English)

It is readliy accepted in the scientific comunity that simulation is a tool of great and still increasing importance in many fields of research and application. For stochastic simulations, the generation of random variates from different distributions is a necessary prerequisite. Thus the first considerations how to generate uniform random numbers and non-uniform random variates started already in the fifties. Since that time, hundreds of papers were published proposing algorithms for many important standard distributions, e.g.for the normal, gamma, beta, Poisson, and binomial distributions. For discrete distributions two different automatic (or universal) algorithms, which can be applied to almost all discrete distributions, are well known:<BR>
the alias method and the method of sequential search. For automatic algorithms for generating continuous distributions, the situation is slightly more difficult. The development in this field was started by Devroye in 1986. A very interesting contribution is due to W.R. Gilks and P. Wild (1992). W. Hörmann (1995) has generalized the concept of Devroye, the corresponding procedure, called transformed density rejection, being applicable to a much larger class of densities, called T-concave densities.<P>
The aims of our project are:<UL>
<LI>Optimize the construction of hat functions for the transformed density method and derive usable properties of the class of T-concave distributions</LI>
<LI>Automatic generation of order statistics</LI>
<LI>Investigate the quality of the resulting non-uniform pseudo-random variates</LI>
<LI>Design universal generators for multivariate distributions</LI>
<LI>Generating multidimensional variates from data</LI>
<LI>Building of a portable C library for all important automatic generators</LI>
<LI>A monography that sumerizes automatic generation techniques</LI>
<LI>Applications</LI></UL>

Publications

Journal article

2004 Tirler, G., Dalgaard, P., Hörmann, W., Leydold, J.. 2004. An Error in the Kinderman-Ramage Method and How to Fix It. Computational Statistics and Data Analysis 47(3): 433-440 open access (Details)
  Leydold, J., Hörmann W.. 2004. Smoothed Transformed Density Rejection. Monte Carlo Methods and Applications 10 (3-4): 393-402 open access (Details)
2003 Leydold, J., Derflinger, G., Tirler, G., Hörmann, W.. 2003. An Automatic Code Generator for Nonuniform Random Variate Generation. Mathematics and Computers in Simulation 62 (3-6): 405-412 open access (Details)
  Hörmann, W., Leydold, J.. 2003. Continuous Random Variate Generation by Fast Numerical Inversion. ACM Trans. Model. Comput. Simul. 13 (4): 347-362 (Details)
  Leydold, J.. 2003. Short universal generators via generalized ratio-of-uniforms method. Mathematics of Computation 72 (243): 1453-1471 (Details)
2002 Hörmann, W.. 2002. A Note on the Performance of the 'Ahrens Algorithm'. Computing 69 (1): 83-89 (Details)
  Hörmann, W., Derflinger, G.. 2002. Fast Generation of Order Statistics. ACM Transactions on Modeling and Computer Simulation 12 (2): 83-93 (Details)
2000 Leydold, J.. 2000. A Note on Transformed Density Rejection. Computing 65 (2): 187-192 (Details)
  Hörmann, W.. 2000. Algorithm 802: An Automatic Generator for Bivariate Log-Concave Distributions. ACM Transactions on Mathematical Software 26 (1): 201-219 (Details)
  Leydold, J.. 2000. Automatic Sampling with the Ratio-of-Uniforms Method. ACM Transactions on Mathematical Software 26 (1): 78-98 (Details)
1998 Leydold, J., Hörmann, W.. 1998. A Sweep-Plane Algorithm for Generating random tuples in simple polytopes. Mathematics of Computation 67: 1617-1635 (Details)

Chapter in edited volume

2003 Hauser, M., Hörmann, W.. 2003. Time Series. In: Automatic Nonuniform Random Variate Generation, Hrsg. Hörmann, W., Leydold, J., Derflinger, G., 345-362. Berlin/Heidelberg: Springer-Verlag (Details)

Contribution to conference proceedings

2003 Tirler, G., Leydold, J.. 2003. Automatic Nonuniform Random Variate Generation in R. In: Proceedings of the 3rd International Workshop on Distributed Statistical Computing (DSC2003), Hrsg. Hornik, K., Leisch, F., Wien (Details)
2000 Hörmann, W., Leydold, J.. 2000. Automatic Random Variate Generation for Simulation Input. In: Proceedings of the 2000 Winter Simulation Conference, Hrsg. Joines, J. A., Barton, R., Fishwick, P., Kang, K., 675-682. Pistacaway: NJ. IEEE Press (Details)
  Leydold, J., Hörmann, W.. 2000. Black Box Algorithms for Generating Non-Uniform Continuous Random Variates. In: Compstat 2000, Short Communications and Posters, Hrsg. Jansen, J., Bethlehem, J. G., 53-54. Heidelberg: Physica-Verlag (Details)
  Hörmann, W., Bayar, O.. 2000. Modelling Probability Distributions from Data and its Influence on Simulation. In: Proceedings IMACS Symposium on Mathematical Modeling, Argesim Report No. 15, Hrsg. Troch, I., Breitenecker, F., 429-435 (Details)

Paper presented at an academic conference or symposium

2003 Leydold, J.. 2003. Automatic Non-Uniform Random Variate Generation in R. DSC 2003, Technische Universität Wien, Vienna, Austria, 20.03-22.03.2003 (Details)
  Leydold, J.. 2003. Transformed Density Rejection and Smoothed Rejection. MCM 2003, Berlin, Deutschland, 15.09.-19.09.2003 (Details)
2002 Leydold, J.. 2002. A new automatic generator for multivariate distributions. Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing 2002, Singapore, 25.11-28.11.2002 (Details)
  Leydold, J.. 2002. Theory and Practice of Automatic Generators for Non-Uniform Random Variates. Workshop on random number generators and highly uniform point sets, CRM, Université de Montreal, Canada, 17.06-28.06.2002 (Details)
2000 Leydold, J.. 2000. Black Box Algorithms for Generating Non-Uniform Continuous Random Variates. Compstat 2000, Utrecht, The Netherlands, 21.08 -25.08.2000 (Details)
  Leydold, J.. 2000. Universal Algorithms as an Alternative for Generating Non-Uniform Continuous Random Variates. International Conference on Monte Carlo Simulation, Monaco, 18.06-21.06.2000. (Details)

Habilitation

2000 Leydold, J.. 2000. Automatische Erzeugung von nicht-gleichverteilten Zufallsvariablen. Habilitation, Institut für Statistik, WU Wien (Details)

Unpublished lecture

2003 Leydold, J.. 2003. Principles of nonuniform random variate generation. Universität Leipzig, February (Details)
2002 Leydold, J.. 2002. Automatic Generation of Nonuniform Continuous Random Variates. ISDS-Kolloquium, Universität Wien, May (Details)
2000 Leydold, J.. 2000. Automatic Sampling with the Ratio-of-Uniforms Method. Institut fuer Statistik, TU Graz, Jänner (Details)
  Leydold, J.. 2000. Automatische Erzeugung von nichtgleichverteilten Zufallszahlen am Beispiel der Quotientenmethode. Habilitationsvortrag, WU Wien, 22.11. (Details)

Classification

  • 1104 Applied mathematics (Details)
  • 1114 Numerical mathematics (Details)

Expertise

  • random variates