Skip to main content
main-content
Top

About this book

Non-uniform random variate generation is an established research area in the intersection of mathematics, statistics and computer science. Although random variate generation with popular standard distributions have become part of every course on discrete event simulation and on Monte Carlo methods, the recent concept of universal (also called automatic or black-box) random variate generation can only be found dispersed in literature. This new concept has great practical advantages that are little known to most simulation practitioners. Being unique in its overall organization the book covers not only the mathematical and statistical theory, but also deals with the implementation of such methods. All algorithms introduced in the book are designed for practical use in simulation and have been coded and made available by the authors. Examples of possible applications of the presented algorithms (including option pricing, VaR and Bayesian statistics) are presented at the end of the book.

Table of Contents

Frontmatter

Preliminaries

Frontmatter

1. Introduction

Abstract
Non-uniform random variate generation is a small field of research somewhere between mathematics, statistics and computer science. It started in the fifties of the last century in the “stone-age” of computers. Since then its development has mainly been driven by the wish of researchers to solve generation problems necessary to run their simulation models. Also the need for fast generators has been an important driving force. The main mathematical problems that have to be solved concern the distribution of transformed random variates and finding tight inequalities. Also implementing and testing the proposed algorithms has been an important part of the research work. A large number of research papers in this field has been published in the seventies and early eighties. The main bibliographical landmark of this development is the book of Devroye (1986a), that is commonly addressed as the “bible” of random variate generation. We can certainly say that random variate generation has become an accepted research area considered as a subarea of statistical computing and simulation methodology. Practically all text-books on discrete event simulation or Monte Carlo methods include at least one chapter on random variate generation; within simulation courses it is taught even to undergraduate students.
Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger

2. General Principles in Random Variate Generation

Abstract
This chapter is collecting the basic ideas and methods for the generation of continuous non-uniform random variates. They serve as the building blocks of universal algorithms. Most of these methods can also be used for discrete distributions which will be presented in Chap. 3. These methods can also be used as starting points for compiling algorithms to generate random vectors, which will be done in Chap. 11.
Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger

3. General Principles for Discrete Distributions

Abstract
A discrete random variable is a random variable taking only integer values. The distribution of a discrete random variable X is determined by its probability mass function (pmf), p k = Prob(X = k). It is also called probability vector if its support is bounded from below. In the latter case we assume without loss of generality that X is only taking values on the nonnegative integers. We then write (p 0, p 1...) for the probability vector. To generate discrete random variates we can apply the inversion (Sect. 3.1) and the rejection principle (Sect. 3.3) that are also of major importance for continuous distributions. We also present the alias method (Sect. 3.2) which was developed especially for discrete distributions.
Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger

Continuous Univariate Distributions

Frontmatter

4. Transformed Density Rejection (TDR)

Abstract
The main problem when utilizing the acceptance-rejection method for designing a random variate generator is the choice of the hat function. In Sect. 2.2 we have demonstrated how we can find a hat function “by hand” for some simple examples. But for an automatic algorithm we need a design method that can be executed by the computer. It is possible to find a single hat that can be used for all distributions of fairly large families but it is obvious that the fit of such a “global hat” cannot be very close for all distributions. In Chap. 6 we are going to discuss how to find and use such global hat functions. In this chapter we are dealing with methods that can construct hat functions automatically around a given point locally, at least if the density satisfies some regularity conditions. Transformed density rejection is such a principle that can be applied to a large class of continuous distributions. A first variant has been published by Gilks and Wild (1992) under the name adaptive rejection sampling. The use of a general transformation and the name transformed density rejection was suggested by Hörmann (1995). In this presentation we try to develop the idea such that the reader can also see the (in our opinion) “beautiful” mathematical background (Sects. 4.2–4.4). The details and variants of the algorithms are presented in Sect. 4.4. Generalizations and special cases are discussed in Sects. 4.6 and 4.7.
Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger

5. Strip Methods

Abstract
Transformed density rejection as developed in Chap. 4 is a very flexible and efficient universal method for generating non-uniform random variates at the price of some computational effort and the necessity of some mathematical theory. In this chapter we follow a different strategy: Make the generation method as simple as possible. Thus we try to cover the region A f between a density f and the x-axis by a union of rectangles. When making this enveloping region fit better and better these rectangles become more and more skinny, i.e. strips. The resulting algorithms are quite simple and (very) fast. It should be noted here, however, that this method obviously only works for bounded densities with bounded domains.
Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger

6. Methods Based on General Inequalities

Abstract
The methods developed in Chaps. 4 and 5 result in fast algorithms at the price of a complex and expensive setup. In this chapter we do it the other way round and try to find methods with hardly any setup by means of universal inequalities. The resulting algorithms are short and more robust against round-off errors since no complicated hat function has to be computed.
Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger

7. Numerical Inversion

Abstract
The inversion method (see Sect. 2.1) is one of the most important key-stones of random variate generation. In this chapter we try to demonstrate how the inversion principle can be applied to obtain universal algorithms. If the inverse of the cumulative distribution function F -1 is computable, we can generate variates of the desired distribution without any additional information. So we could speak of a “true” black-box algorithm in this case, as we simply can return F -1 (U). Unfortunately most important distributions have a cdf that cannot be expressed in terms of elementary functions and the inverse cdf is even more difficult. Hence the assumption that F -1 is available as a black-box is often of little practical relevance.
Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger

8. Comparison and General Considerations

Abstract
In the previous Chaps. 4, 5, 6, and 7 we have presented a lot of algorithms for sampling from univariate continuous distributions. The variety of methods is at a first glance confusing. On the other hand, it gives the reader the possibility to select the algorithm that is best suited for the given simulation problem. We have implemented most of the presented algorithms in a library called UNU.RAN (Universal Non-Uniform RANdom number generators) which can be downloaded from our web site as C source, see Sect. 8.1. It is not only a ready to use implementation of these algorithms, it is also a detailed reference of how these algorithms can be implemented in a programming language.
Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger

9. Distributions Where the Density Is Not Known Explicitly

Abstract
There are situations in the practice of statistical research where continuous distributions are not characterized by their density or cumulative distribution function. Instead some other functions like the hazard rate (Sect. 9.1), the characteristic function (Sect. 9.4), or a sequence of Fourier coefficients (Sect. 9.3) are known. In such cases it can be very useful to have the possibility to sample directly from these distributions without computing the density, which is often very difficult and cumbersome in such situations. Luc Devroye (1981; 1984a; 1986c; 1986d; 1989) has introduced most of these methods. We give an overview and present the details of those algorithms that seem to be most useful in practice; among them a new automatic algorithm for distributions with increasing hazard rate.
Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger

Discrete Univariate Distributions

Frontmatter

10. Discrete Distributions

Abstract
A discrete random variable is a random variable taking only values on integers. The distribution of a discrete random variable X is determined by its probability mass function, p k = Prob(X = k). It is also called probability vector if its support is bounded from below. In the latter case we assume without loss of generality that X is only taking values on the nonnegative integers. We then write (p 0 ,p 1 , …) for the probability vector. Analogously to the continuous case we use the terms quasi-probability mass function for a nonnegative summable function that need not be normalized.
Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger

Random Vectors

Frontmatter

11. Multivariate Distributions

Abstract
It is a commonplace for all fields of computational mathematics that in the multivariate situation everything becomes much more difficult. But on the other hand tools for handling multivariate distributions are of greatest importance as one of the most common modeling errors is to overlook dependencies between input variables of a stochastic system. This error can make simulation results totally useless. Thus it is important to have generation procedures for random vectors available. There are few commonly accepted standard distributions for random vectors; even for these distributions generation procedures are difficult to find. Nevertheless, there are quite a few papers discussing the design of multivariate families that are well suited for random vector generation. For many of these families the marginals are known as well. The monograph of Johnson (1987) is presenting this branch of multivariate simulation. You can also find many of these distributions in Devroye (1986a, Chap. XI).
Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger

Implicit Modeling

Frontmatter

12. Combination of Generation and Modeling

Abstract
Up to now we have assumed that we have a full characterization of the distribution we want to sample from. In most cases the distribution was characterized by its density and we tried to find universal algorithms that are able to sample exactly from that distribution. This is a well posed and often interesting mathematical problem but for the simulation practitioner the problem starts earlier: He has to decide about the input distribution before he can think about generating the variates. There are quite a few different approaches to tackle this task. They depend on the information we have available from the stochastic input we should model. For example, data from the real system might be available. Then we should sample random variates that have the “same property” as the observed sample. Strictly speaking questions of this kind are not the subject of a book dealing with random variate generation. But due to its great practical importance we decided to include this chapter.
Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger

13. Time Series (Authors Michael Hauser and Wolfgang Hörmann)

Abstract
In this chapter we are concerned with times series, i.e. with the generation of sample paths of stochastic non-deterministic processes in discrete time, (X t ,t ∈ ℤ), where X t are continuous random variates. In the first part we will focus our presentation on stationary Gaussian processes. These are most widely used in the analysis of, e.g., economic series or in signal processing.
Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger

14. Markov Chain Monte Carlo Methods

Abstract
We have seen in Chapter 11 that the generation of random vectors is often not easy. The rejection based algorithms what we presented there are from a practical point of view limited to small dimensions up to at most 10. And there are lots of distributions that are even difficult to sample from in dimension three or four. A totally different approach is based on the fact that we always can easily construct a Markov chain that has the desired fixed multivariate distribution as its unique stationary distribution. Of course there is a price we have to pay for this simplicity: the dependence of the generated vectors.
Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger

15. Some Simulation Examples

Abstract
We hope that the reader has seen so far that random variate generation leads to interesting algorithms and is linked with sometimes difficult mathematical questions. But we should not overlook the fact that random variate generation is an applied discipline in the sense that its new developments were mainly driven by the needs of scientists and engineers using simulation. In recent years two of the most rapidly evolving areas of simulation have been Bayesian statistics and financial engineering. So we think it goes well with the aims of our book to include this final chapter, that demonstrates some very “modern” applications of random variate generation.
Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger

Backmatter

Additional information