Chapters I–XIV are based on the premises that a perfect uniform [0,1] random variate generator is available and that real numbers can be manipulated and stored. Now we drop the first of these premises and Instead assume a perfect bit generator (i.e., a source capable of generating lid {0,1} random varlates B1,B2,…), While still assuming that real numbers can be manipulated and stored, as before: this is for example necessary when someone gives us the probabilities pn for discrete random variate generation. The cost of an algorithm can be measured in terms of the number of bits required to generate a random variate. This model is due to Knuth and Yao (1976) who introduced a complexity theory for nonuniform random variate generation. We will report the main ideas of Knuth and Yao in this chapter.
Random number generation has intrigued scientists for a few decades, and a lot of effort has been spent on the creation of randomness on a deterministic (non-random) machine, that is, on the design of computer algorithms that are able to produce “random” sequences of integers. This is a difficult task. Such algorithms are called generators, and all generators have flaws because all of them construct the n-th number in the sequence in function of the n − 1 numbers preceding it, initialized with a nonrandom seed. Numerous quantities have been invented over the years that measure just how “random” a sequence is, and most well-known generators have been subjected to rigorous statistical testing. However, for every generator, it is always possible to find a statistical test of a (possibly odd) property to make the generator flunk. The mathematical tools that are needed to design and analyze these generators are largely number theoretic and combinatorial. These tools differ drastically from those needed when we want to generate sequences of integers with certain non-uniform distributions, given that a perfect uniform random number generator is available. The reader should be aware that we provide him with only half the story (the second half). The assumption that a perfect uniform random number generator is available is now quite unrealistic, but, with time, it should become less so. Having made the assumption, we can build quite a powerful theory of non-uniform random variate generation.
In this chapter we introduce the reader to the fundamental principles in non-uniform random variate generation. This chapter is a must for the serious reader. On its own it can be used as part of a course in simulation.
A discrete random variable is a random variable taking only values on the nonnegatlve integers. In probability theoritical texts, a discrete random variable is a random variable which takes with probability one values in a given countable set of points. Since there is a one-to-one correspondence between any countable set and the nonnegative integers, it is clear that we need not consider the general case. In most cases of interest to the practitioner, this one-to-one correspondence is obvious.
The main techniques for random varlate generation were developed in chapters II and III. These will be supplemented in this chapter with a host of other techniques: these include historically important methods (such as the Forsythe-von Neumann method), methods based upon specific properties of the uniform distribution (such as the polar method for the normal density), methods for densities that are given as convergent series (the series method) and methods that have proven particularly successful for many distributions (such as the ratlo-of-unlforms method).
The goal of this book is to demonstrate that random varlates with various distributions can be obtained by cleverly manipulating iid uniform [0,1] random varlates. As we will see in this chapter, normal, exponential, beta, gamma and t distributed random varlates can be obtained by manipulation of the order statistics or spaclngs defined by samples of iid uniform [0,1] random varlates. For example, the celebrated polar method or Box-Muller method for normal random varlates will be derived in this manner (Box and Muller, 1958).
One of the most important processes occurring in nature is the Poisson point process. It is therefore important to understand how such processes can be simulated. The methods of simulation vary with the type of Poisson point process, i.e. with the space in which the process occurs, and with the homogeneity or nonhomogeneity of the process. We will not be concerned with the genesis of the Poisson point process, or with important applications in various areas. To make this material come alive, the reader is urged to read the relevant sections in Feller (1965) and Cinlar (1975) for the basic theory, and some sections in Trivedi (1982) for computer science applications.
In the next two chapters we will apply the tools of the previous chapters in the design of algorithms that are applicable to large families of distributions. Described in terms of a common property, such as the family of all unimodal densities with mode at 0, these families are generally speaking nonparametric in nature. A method that is applicable to such a large family is called a universal method. For example, the rejection method can be used for all bounded densities on [0,1], and is thus a universal method. But to actually apply the rejection method correctly and efficiently would require knowledge of the supremum of the density. This value cannot be estimated in a finite amount of time unless we have more information about the density in question, usually in the form of an explicit analytic definition. Universal methods which do not require anything beyond what is given in the definition of the family are called black box methods.
We have Illustrated how algorithms can be sped up if we are willing to compute certain constants beforehand. For example, when a discrete random varlate is generated by the inversion method, it pays to compute and store the individual probabilities pn beforehand. This information can speed up sequential search, or could be used in the method of guide tables. For continuous random varlates, the same remains true. Because we know many ultra fast discrete random varlate generation methods, but very few fast continuous random varlate generation techniques, there is a more pressing need for acceleration in the continuous case. Globally speaking, dlscretlzlng the problem speeds generation.
Chapters IX and X are included for the convenience of a large subpopulation of users, the statisticians. The main principles in random varlate generation were developed in the first eight chapters. Most particular distributions found here are members of special classes of densities for which universal methods are available. For example, a short algorithm for log-concave densities was developed in section VII.2. When speed is at a premium, then one of the table methods of the previous chapter could be used. This chapter is purely complementary. We are not in the least interested in a historical review of the different methods proposed over the years for the popular densities. Some interesting developments which give us new insight or illustrate certain general principles will be reported. The list of distributions corresponds roughly speaking to the list of distributions in the three volumes of Johnson and Kotz.
We will provide the reader with some generators for the most popular families of discrete distributions, such as the geometric, binomial and Poisson distributions. These distributions are the fundamental building blocks in discrete probability. It is impossible to cover most distributions commonly used in practice. Indeed, there is a strong tendency to work more and more with so-called generalized distributions. These distributions are either defined constructively by combining more elementary distributions, or analytically by providing a multiparameter expression for the probability vector. In the latter case, random variate generation can be problematic since we cannot fall back on known distributions. Users are sometimes reluctant to design their own algorithms by mimicking the designs for similar distributions. We therefore include a short section with universal algorithms. These are in the spirit of chapter VII: the algorithms are very simple albeit not extremely fast, and very Importantly, their expected time performance is known. Armed with the universal algorithms, the worked out examples of this chapter and the table methods of chapter VIII, the users should be able to handle most distributions to their satisfaction.
We assume throughout this chapter that the discrete random variables are all integer-valued.
In this chapter we consider the problem of the selection of a random sample of size k from a set of n objects. This is also called sampling without replacement since duplicates are not allowed. There are several issues here which should be clarified in this, the introductory section.
Some applications demand that random combinatorial objects be generated: by definition, a combinatorial object is an object that can be put into one-to-one correspondence with a finite set of integers. The main difference with discrete random varlate generation is that the one-to-one mapping is usually complicated, so that it may not be very efficient to generate a random integer and then determine the object by using the one-to-one mapping. Another characteristic is the size of the problem: typically, the number of different objects is phenomenally large. A final distinguishing feature is that most users are interested in the uniform distribution over the set of objects.
A probabilistic shortcut in random varlate generation is a method for reducing the expected time in a simulation by recognizing a certain structure in the problem. This principle can be illustrated in hundreds of ways. Indeed, there is not a single example that could be called “typical”. It should be stressed that the efficiency is derived from the problem itself, and is probabilistic in nature. This distinguishes these shortcuts from certain techniques that are based upon clever data structures or fast algorithms for certain sub-tasks. We will draw our examples from three sources: the simulation of maxima and sums of lid random variables, and the simulation of regenerative processes.
