Simple perfect samplers using monotone birth-and-death processes

MaRDI QIDQ6283347zbMATH OpenFDO

Authors Hiroyuki Masuyama

Publication date 19 February 2017

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Random number generation in numerical analysis (65C10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: This paper proposes simple perfect samplers using monotone birth-and-death processes (BD-processes), which draw samples from an arbitrary finite discrete target distribution. We first construct a monotone BD-process whose stationary distribution is equal to the target distribution. We then derive upper bounds for the expected coalescence time of the copies of the monotone BD-process. We also establish upper bounds for the expected values and tail probabilities of the running times of two perfect samplers, which are Doubling CFTP and Read-once CFTP using our monotone BD-process. The latter sampler can draw samples exactly from unnormalized target distributions with little memory consumption.

This page was built for publication: Simple perfect samplers using monotone birth-and-death processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6283347)