Random Variate Generation and Markov Chain Monte Carlo


Type Research Project

Funding Bodies
  • Austrian Science Fund

Duration Nov. 1, 2003 - Oct. 31, 2006

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)
  • Hörmann, Wolfgang (Former researcher)
  • Karawatzki, Roman (Former researcher)
  • Leydold, Josef (Details) Project Head
  • Tirler, Günter (Former researcher)
 

Abstract (German)

Stochastische Simulation ist ein bekanntes und wichtiges Werkzeug in vielen Forschungsgebieten und Anwendungen. Grundlage dieser dieser Technik ist jedoch, dass Zufallsvariate von vielen verschiedenen Verteilungen erzeugt werden können. Daher hat man bereits in den Fünfzigerjahren des letzten Jahrhunderts begonnen Methoden zu deren Erzeugung zu entwickeln. Im Vordergrund der hierbei entwickelten Algorithmen standen hohe Generierungsgeschwindigkeit und geringer Speicherverbrauch. In den letzten zehn Jahren wurden sogenannte automatische Methoden entwickelt, die es ermöglichen mit Hilfe eines einzigen Computerprogrammes Zufallszahlen aus einer großen Klasse von Verteilungen zu erzeugen. Diese Algorithmen arbeiten relativ effizient und benötigen aber einen Initialisierungsschrittes, der für manche Verteilungen/Methoden relativ zeitaufwendig sein kann. Obwohl in den letzten Jahren einige derartige Algorithmen entwickelt wurden, gibt es noch viele ungelöste Probleme.
Im Bereich der Markov Chain Monte Carlo Methoden ist es notwendig, dass immer nur eine Zufallsvariate von einer Verteilung erzeugt wird; das aber sehr oft. Methoden mit schnellem Initialisierungsschritt wären daher wichtig.
Methoden zur Erzeugung von unabhängigen multivariaten Zufallsvektoren sind von Bedeutung, aber die heute verfügbaren Algorithmen sind aber sehr langsam.
Für Quasi-Monte Carlo Methoden (QMC) werden Algorithmen benötigt, die gleichverteilte Zahlentupel mit kleiner Diskrepanz in entsprechende Zufallsvektoren mit vorgegebener Dichte transformieren.
Eine andere Problematik liegt darin begründet, dass die mathematischen Theorien, die diesen automatischen Methoden zugrunde liegen, von reellen Zahlen ausgehen. Implementiert werden diese Algorithmen jedoch in Computern die nur
über eine Gleitkommaarithmetik mit begrenzter Genauigkeit verfügen, typischerweise 16 Dezimalstellen.
Ziel dieses Forschungsprojektes ist es, Lösungen für diese und ähnliche Probleme zu erarbeiten.


Abstract (English)

Stochastic simulation is a tool of well known and appreciated importance in many fields of research and application. To use stochastic simulation the generation of random variates from different distributions is a necessary prerequisite.
Therefore the first considerations how to generate random numbers started already in the fifties of the last century. Many methods for sampling from standard distributions have been proposed. The design goals for these algorithms are speed and little memory requirements. If random variates from non-standard distributions or for special simulation problems are required new algorithms are necessary. In the last decade so-called automatic methods have been developed that allow to sample from a large class of distributions with a single piece of code. These algorithms are efficient and have some advantages that makes them attractive even for sampling from standard distributions. The price for using such algorithms is that a setup is required that might be quite expensive for some methods/distributions. Although some research was done there are still a lot of open generation problems. In the framework of Markov Chain Monte Carlo (MCMC) sampling routines with a fast setup are needed. Methods for
sampling independent points from multivariate distributions are important but existing algorithms are slow or work only for low dimensions. For quasi-Monte Carlo methods (QMC) the development of fast automatic algorithms to generate non-uniformly distributed low-discrepancy sequences (quasi-random variates) is required. Another problem is that the mathematical theory behind such automatic methods is based on real numbers, whereas the environment in wich the algorithms are implemented uses so-called floating point numbers which have a limited precision, usually 16 decimal digits. The aim of this project is to find some solutions to these and similar problems.

Publications

Journal article

2007 Hörmann, Wolfgang, Leydold, Josef, Derflinger, Gerhard. 2007. Inverse Transformed Density Rejection for Unbounded Monotone Densities. ACM Transactions on Modeling and Computer Simulation 17 (4): 18/1-18/16. (Details)
2005 L'Ecuyer, Pierre, Leydold, Josef. 2005. Rstream: Streams of Random Numbers for Stochastic Simulation. R News 5 (2): 16-20. open access (Details)

Paper presented at an academic conference or symposium

2007 Leydold, Josef. 2007. UNU.RAN - A Library for Universal Non-Uniform RANdom Variate Generators. ROOT Workshop'07, Genf, Schweiz, 26.03.-29.03.. (Details)
2006 Leydold, Josef. 2006. Black-Box Algorithms for Sampling from Continuous Distributions. Winter Simulation Conference '06, Monterey, CA, Vereinigte Staaten/USA, 03.12.-07.12.. (Details)
  Leydold, Josef. 2006. HITRO. 21th TBI Winterseminar, Bled, Slowenien, 19.02-25.02. (Details)
  Leydold, Josef. 2006. New Densities for (Quasi-) Importance Sampling. 7th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Ulm, Deutschland, 14.08-18.08. (Details)
2004 Leydold,J.. 2004. RNGstreams - An R package for multiple independent streams of uniform random numbers. UseR! 2004, Vienna, Austria, 20.05-22.05.2004 (Details)
  Leydold, J.. 2004. Some remarks on F-discrepancy, numerical inversion and integration errors. Number Theoretic Algorithms and Related Topics, Strobl, Austria, 27.09-01.10.2004 (Details)

Working/discussion paper, preprint

2003 Hörmann, W., Leydold, J.. 2003. Improved Perfect Slice Sampling. Research Report Series, Report 49, Department of Applied Statistics and Data Processing, WU Wien. (Details)
  Leydold, J., Hörmann, W.. 2003. Smoothed Transformed Density Rejection. Institut für Statistik, WU Wien (Details)

Unpublished lecture

2007 Leydold, Josef. 2007. Non-Uniform Random Variate Generation for Monte Carlo Methods. Forschungsseminar, Institut für Mathematik, Isik University, Istanbul-Sile, Türkei, 20.04. (Details)
2006 Leydold, Josef. 2006. Importance Sampling and Quasi-Monte Carlo Integration. Department for Industrial Engineering, Bogazici University Istanbul, Istanbul, 12.09. (Details)

Classification

  • 1104 Applied mathematics (Details)
  • 1105 Computer software (Details)
  • 1113 Mathematical statistics (Details)
  • 1133 Computer-aided simulation (Details)

Expertise

  • nonuniform random variate generation
  • automatic method
  • Markov chain Monte Carlo
  • quasi-Monte Carlo
  • stochastic simulation