Automatic Nonuniform Random Variate Generation

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.

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.

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 ₀, p ₁...) 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.

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.

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.

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.

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.

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.

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.

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 ₀ ,p ₁ , …) 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.

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).

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.

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.

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.

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.