A generalization of the adaptive rejection sampling algorithm Articles uri icon

publication date

  • October 2011

start page

  • 633

end page

  • 647

issue

  • 4

volume

  • 21

international standard serial number (ISSN)

  • 0960-3174

electronic international standard serial number (EISSN)

  • 1573-1375

abstract

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

keywords

  • rejection sampling; adaptive rejection sampling; gibbs sampling; monte carlo integration; sensor networks; target localization