A generalization of the adaptive rejection sampling algorithm

• DOI: 10.1007/s11222-010-9197-9
• Publication Date: 2010-08-24T21:09:14Z
• Authors: Luca Martino; Joaquín Míguez
• Keywords: Rejection sampling; Sequence (biology); Sample (material)

This work has been partially supported by the Ministry of Science and Innovation of Spain (project MONIN, ref. TEC-2006-13514-C02-01/TCM, project DEIPRO, ref. TEC-2009- 14504-C02-01 and program Consolider-Ingenio 2010 CSD2008- 00010 COMONSENS) and the Autonomous Community of Madrid (project PROMULTIDIS-CM, ref. S-0505/TIC/0233).<br/>Publicado<br/>Rejection sampling is a well-known method to generate random samples from arbitrary target probability distributions. It demands the design of a suitable proposal probability density function (pdf) from which candidate samples can be drawn. These samples are either accepted or rejected depending on a test involving the ratio of the target and proposal densities. The adaptive rejection sampling method is an efficient algorithm to sample from a log-concave target density, that attains high acceptance rates by improving the proposal density whenever a sample is rejected. In this paper we introduce a generalized adaptive rejection sampling procedure that can be applied with a broad class of target probability distributions, possibly non-log-concave and exhibiting multiple modes. The proposed technique yields a sequence of proposal densities that converge toward the target pdf, thus achieving very high acceptance rates. We provide a simple numerical example to illustrate the basic use of the proposed technique, together with a more elaborate positioning application using real data.<br/>The original publication is available at www.springerlink.com<br/>