Regenerative Rejection Sampling

Abstract

This Master’s Thesis research project presents Regenerative Rejection Sampling (RRS), a novel approximate sampling algorithm inspired by classical Rejection Sampling and Markov Chain Monte Carlo methods. The method constructs a continuous-time regenerative process whose stationary distribution coincides with a target density known only up to a normalizing constant. Unlike standard Rejection Sampling, RRS does not require the existence of a finite constant that upper-bounds the likelihood ratio. As a result, its total variation convergence rate remains exponential for a larger class of scenarios compared to, for example, the Independent Metropolis-Hastings sampler, which requires a finite bounding constant.

To explain the workings of the method, we first present a review of renewal and regenerative processes, including their stationary versions, and convergence properties.

We then introduce the RRS algorithm and derive its convergence rate. Its performance is compared theretically and empirically with classical MCMC methods. Numerical experiments demonstrate that RRS can exhibit lower autocorrelations and faster effective mixing, both in synthetic examples and in a Bayesian probit regression model applied to a real medical dataset. Moreover, we show that the bias of the time-average estimator constructed from the RRS method is of order O(1/t2), not of the usual order O(1/t), and provide easy-to-estimate non-asymptotic bound for this bias.