main-content

This book systematically addresses the design and analysis of efficient techniques for independent random sampling. Both general-purpose approaches, which can be used to generate samples from arbitrary probability distributions, and tailored techniques, designed to efficiently address common real-world practical problems, are introduced and discussed in detail. In turn, the monograph presents fundamental results and methodologies in the field, elaborating and developing them into the latest techniques. The theory and methods are illustrated with a varied collection of examples, which are discussed in detail in the text and supplemented with ready-to-run computer code.

The main problem addressed in the book is how to generate independent random samples from an arbitrary probability distribution with the weakest possible constraints or assumptions in a form suitable for practical implementation. The authors review the fundamental results and methods in the field, address the latest methods, and emphasize the links and interplay between ostensibly diverse techniques.

### Chapter 1. Introduction

Abstract
This chapter provides an introduction to the different approaches available for sampling from a given probability distribution. We start with a brief history of the Monte Carlo (MC) method, one of the most influential algorithms of the twentieth century and the main driver for the current widespread use of random samples in many scientific fields. Then we discuss the need for MC approaches through a few selected examples, starting with two important classical applications (numerical integration and importance sampling), and finishing with two more recent developments (inverse Monte Carlo and quasi Monte Carlo). This is followed by a review of the three types of “random numbers” which can be generated (“truly” random, pseudo-random, and quasi-random), a brief description of some pseudo-random number generators and an overview of the different classes of random sampling methods available in the literature: direct, accept/reject, MCMC, importance sampling, and hybrid. Finally, the chapter concludes with an exposition of the motivation, goals, and organization of the book.
Luca Martino, David Luengo, Joaquín Míguez

### Chapter 2. Direct Methods

Abstract
In this chapter we look into a collection of direct methods for random sampling. The term direct is used here to indicate that i.i.d. random draws with exactly the desired probability distribution are produced by applying a transformation that maps one (or many) realizations from the available random source into a realization from the target random variable. Most often, this transformation can be described as a deterministic map. However, we also include here techniques that rely on either discrete or continuous mixtures of densities and which can be interpreted as (pseudo)stochastic transformations of the random source.
Furthermore, many of the techniques proposed in the literature are found to be closely related when studied in sufficient detail. We pay here specific attention to some of these links, as they can be later exploited for the design of more efficient samplers, or simply to attain a better understanding of the field.
Luca Martino, David Luengo, Joaquín Míguez

### Chapter 3. Accept–Reject Methods

Abstract
The accept/reject method, also known as rejection sampling (RS), was suggested by John von Neumann in 1951. It is a classical Monte Carlo technique for universal sampling that can be used to generate samples virtually from any target density p o (x) by drawing from a simpler proposal density π(x). The sample is either accepted or rejected by an adequate test of the ratio of the two pdfs, and it can be proved that accepted samples are actually distributed according to the target distribution. Specifically, the RS algorithm can be viewed as choosing a subsequence of i.i.d. realizations from the proposal density π(x) in such a way that the elements of the subsequence have density p o (x).
In this chapter, we present the basic theory of RS as well as different variants found in the literature. Computational cost issues and the range of applications are analyzed in depth. Several combinations with other Monte Carlo techniques are also described.
Luca Martino, David Luengo, Joaquín Míguez

### Chapter 4. Adaptive Rejection Sampling Methods

Abstract
This chapter is devoted to describing the class of the adaptive rejection sampling (ARS) schemes. These (theoretically) universal methods are very efficient samplers that update the proposal density whenever a generated sample is rejected in the RS test. In this way, they can produce i.i.d. samples from the target with an increasing acceptance rate that can converge to 1. As a by-product, these techniques also generate a sequence of proposal pdfs converging to the true shape of the target density. Another advantage of the ARS samplers is that, when they can be applied, the user only has to select a set of initial conditions. After the initialization, they are completely automatic, self-tuning algorithms (i.e., no parameters need to be adjusted by the user) regardless of the specific target density. However, the need to construct a suitable sequence of proposal densities restricts the practical applicability of this methodology. As a consequence, ARS schemes are often tailored to specific classes of target distributions. Indeed, the construction of the proposal is particularly hard in multidimensional spaces. Hence, ARS algorithms are usually designed only for drawing from univariate densities.
In this chapter we discuss the basic adaptive structure shared by all ARS algorithms. Then we look into the performance of the method, characterized by the acceptance probability (which increases as the proposal is adapted), and describe various extensions of the standard ARS approach which are aimed either at improving the efficiency of the method or at covering a broader class of target pdfs. Finally, we consider a hybrid method that combines the ARS and Metropolis-Hastings schemes.
Luca Martino, David Luengo, Joaquín Míguez

### Chapter 5. Ratio of Uniforms

Abstract
This chapter provides a detailed description of the so-called ratio-of-uniforms (RoU) methods. The RoU and the generalized RoU (GRoU) techniques were introduced in Kinderman and Monahan (ACM Trans Math Softw 3(3):257–260, 1977); Wakefield et al. (Stat Comput 1(2):129–133, 1991) as bivariate transformations of the bidimensional region $$\mathcal {A}_0$$ below the target pdf p o (x) ∝ p(x). To be specific, the RoU techniques can be seen as a transformation of a bidimensional uniform random variable, defined over $$\mathcal {A}_0$$, into another two-dimensional random variable defined over an alternative set $$\mathcal {A}$$. RoU schemes also convert samples uniformly distributed on $$\mathcal {A}$$ into samples with density p o (x) ∝ p(x) (which is equivalent to draw uniformly from $$\mathcal {A}_0$$). Therefore, RoU methods are useful when drawing uniformly from the region $$\mathcal {A}$$ is comparatively simpler than drawing from p o (x) itself (i.e., simpler than drawing uniformly from $$\mathcal {A}_0$$). In general, RoU algorithms are applied in combination with the rejection sampling principle and they turn out especially advantageous when $$\mathcal {A}$$ is bounded. In this chapter, we present first the basic theory underlying RoU methods, and then study in depth the connections with other sampling techniques. Several extensions, as well as different variants and point of views, are discussed.
Luca Martino, David Luengo, Joaquín Míguez

### Chapter 6. Independent Sampling for Multivariate Densities

Abstract
In this chapter, we present several techniques for multivariate independent sampling. We recall some techniques introduced in the previous chapters and show how they can be adapted to a multidimensional setup. Additionally, we provide guidelines for their application in higher dimensional spaces. We also consider the problem of drawing uniformly from a measurable set embedded in $$\mathbb {R}^n$$. With this goal, an exhaustive description of transformations of random vectors is given, which extends the study of this approach in the previous chapters.
The problem of sampling a random vector can often be conveniently viewed as generating a (finite) sequence of statistically dependent scalar samples. Thus, in this chapter, we take a slight detour from the main course of the book and show different methods that yield dependent samples, including the use of stochastic processes. Furthermore, a collection of efficient samplers for specific multivariate distributions is described.
Luca Martino, David Luengo, Joaquín Míguez

### Chapter 7. Asymptotically Independent Samplers

Abstract
Markov Chain Monte Carlo (MCMC) methods are possibly the most popular tools for random sampling nowadays. They generate “chains” (sequences) of samples from a target distribution that can be selected with few constraints. However, as highlighted by the term “chain,” the draws output by the MCMC method are statistically dependent (and often highly correlated), which makes such algorithms not directly comparable with the methods in the rest of this monograph. In this chapter, we describe two families of non-standard MCMC techniques that enjoy the property of producing samples that become asymptotically independent as a parameter grows to infinity or the number of random draws in the algorithm is increased. The methods of the first family are based on generating a pool of candidate samples at each iteration of the chain, instead of only one as in conventional procedures. The techniques in the second family rely on an adaptive, non-parametric approximation of the target density, which is improved as new samples are generated. We describe the general methodology for the two families, and provide some specific algorithms as examples.
Luca Martino, David Luengo, Joaquín Míguez

### Chapter 8. Summary and Outlook

Abstract
In this monograph, we have described the theory and practice of pseudo-random variate generation. This is the core of Monte Carlo simulations and, hence, of practical importance for a large number of applications in various fields, including computational statistics, cryptography, computer modeling, games, etc. The focus has been placed on independent and exact sampling methods, as opposed to techniques that produce weighted (e.g., importance sampling) and/or correlated populations (e.g., MCMC).
Luca Martino, David Luengo, Joaquín Míguez