Adaptive rejection sampling with fixed number of nodes

ABSTRACT

The adaptive rejection sampling (ARS) algorithm is a universal random generator for drawing samples efficiently from a univariate log-concave target probability density function (pdf). ARS generates independent samples from the target via rejection sampling with high acceptance rates. Indeed, ARS yields a sequence of proposal functions that converge toward the target pdf, so that the probability of accepting a sample approaches one. However, sampling from the proposal pdf becomes more computational demanding each time it is updated. In this work, we propose a novel ARS scheme, called Cheap Adaptive Rejection Sampling (CARS), where the computational effort for drawing from the proposal remains constant, decided in advance by the user. For generating a large number of desired samples, CARS is faster than ARS.

KEYWORDS:

• Adaptive rejection sampling
• Monte Carlo methods
• Rejection sampling

MATHEMATICS SUBJECT CLASSIFICATION:

• 65C05
• 62F15

Funding

This work has been supported by the Grant 2014/23160-6 of São Paulo Research Foundation (FAPESP) and by the Grant 305361/2013-3 of National Council for Scientific and Technological Development (CNPq).

Notes

1 The possibility of applying ARS for drawing for multivariate densities depends on the ability of constructing a sequence of non-parametric proposal pdfs in higher dimensions. See, for instance, the piecewise constant construction in Martino et al. (2015a) as a simpler alternative procedure.

2 The evaluation of V′(x) is not strictly necessary, since the function q_t(x) can also construct using a derivative-free procedure (e.g., see Gilks (1992) or the piecewise constant construction in Martino et al. (2015a)). For the sake of simplicity, we consider the construction involving tangent lines.

3 In the following, we denote as E[η_t] the acceptance rate, at the tth iteration, averaged over several (theoretically infinite) runs.

4 The best configuration ${\mathcal{S}}_{\infty }$ depends on the specific construction procedure employed for building the sequence of proposal functions q₁, q₂…, q_t, ….

5 Clearly, the configurations of either all negative or all positive are discarded since they yield improper proposal pdf by construction.