2003 Royal Statistical Society 1369–7412/03/65679J. R. Statist. Soc. B (2003)65, Part 3, pp. 679–700Reversible jump, birth-and-death and more generalcontinuous time Markov chain Monte Carlo samplersOlivier Capp´e,Centre National de la Recherche Scientifique, Paris, FranceChristian P. RobertUniversit´e Paris Dauphine, Paris, and Centre de Recherche en Economie et Statistique,Paris, Franceand Tobias Ryd´enLund University, Sweden[Received September 2001. Final revision December 2002]Summary. Reversible jump methods are the most commonly used Markov chain Monte Carlotool for exploring variable dimension statistical models. Recently, however, an alternative ap-proach based on birth-and-death processes has been proposed by Stephens for mixtures ofdistributions.We show that the birth-and-death setting can be generalized to include other typesof continuous time jumps like split-and-combine moves in the spirit of Richardson and Green.We illustrate these extensions both for mixtures of distributions and for hidden Markov models.We demonstrate the strong similarity of reversible jump and continuous time methodologies byshowing that, on appropriate rescaling of time, the reversible jump chain converges to a limitingcontinuous time birth-and-death process. A numerical comparison in the setting of mixtures ofdistributions highlights this similarity.Keywords: Birth-and-death process; Hidden Markov model; Markov chain Monte Carloalgorithms; Mixture distribution; Rao–Blackwellization; Rescaling1. IntroductionMarkov chain Monte Carlo (MCMC) methods for statistical inference, in particular Bayesianinference, have become standard during the past 10 years (Capp´e and Robert, 2000). For vari-able dimension problems, often arising through model selection, a popular approach is Green’s(1995) reversible jump MCMC (RJMCMC) methodology. Recently, however, in the contextof mixtures of distributions, Stephens (2000) rekindled interest in the use of continuous timebirth-and-death processes for variable dimension problems, following earlier proposals by Rip-ley (1977), Geyer and Møller (1994), Grenander and Miller (1994) and Phillips and Smith(1996). We shall call this approach birth-and-death MCMC (BDMCMC) sampling and itsgeneralizations continuous time MCMC (CTMCMC) sampling.In this paper, we investigate the similarity between the reversible jump and birth-and-deathmethodologies. In particular, it is shown in Section 4 that, for any BDMCMC process satisfyingAddress for correspondence: Christian P. Robert, Centre de Recherche en Math´ematiques de la D´ecision,Universit´e Paris 9—Dauphine, F-75775 Paris Cedex 16, France.E-mail: [email protected] O. Capp´e, C. P. Robert and T. Ryd ´ensome weak regularity conditions, there is a sequence of RJMCMC processes that converges, ina sense specified later, to the BDMCMC process.In their application of RJMCMC methods to mixtures of distributions, Richardson andGreen (1997) implemented two types of move that could change the number of componentsof the mixture: one was the birth-and-death move, in which a new component is created or anexisting one is deleted, and the other was the split-and-combine move, in which one componentis split in two, or two components are combined into one. In contrast, Stephens (2000) only dealtwith birth-and-death moves to keep the algorithm within the theory of marked point processeson general spaces, while pointing out that ‘one can envision a continuous time version of thegeneral reversible jump formulation’. We show here that continuous time algorithms are not lim-ited to the birth-and-death structure and that convergence of reversible jump to birth-and-deathMCMC methodology is much more general. For example, split-and-combine moves could beincorporated, resulting in more general CTMCMC algorithms, and the appropriate theoreticalframework is that of Markov jump processes. To complete our study of the connections betweenRJMCMC and CTMCMC methods, we implemented a full-scale numerical comparison withmoves similar to those in Richardson and Green (1997) used in both algorithms: the outcomeis the same for both samplers, with a longer execution time for CTMCMC algorithms.The paper is organized as follows: in Section 2 we review the main features of the BDMCMCmethodology, including moves that are more general than birth-and-death moves in Section 2.4and variance reduction techniques in Section 2.5. This technology is exemplified for hidden Mar-kov models in Section 3. Section 4 addresses a comparison of this approach with RJMCMCmethodology, recalling the basics of RJMCMC methods in Section 4.1, establishing conver-gence of RJMCMC to BDMCMC methods in Section 4.2 and detailing the numerical compar-ison of both algorithms in Section 4.4. Section 5 concludes the paper with a discussion.2. Continuous time Markov chain Monte Carlo methodologiesIn this section we review BDMCMC methods in the mixture case that was considered by Ste-phens (2000) and we discuss the extension of the birth-and-death moves to other continuoustime moves. Although Stephens (2000) provided a full description of the method in the specificset-up of mixtures of distributions, CTMCMC sampling is limited neither to birth-and-deathmoves nor to mixture models. For example, CTMCMC methods may be applied to any of theexamples in Green (1995). See also Ripley (1977), Geyer and Møller (1994), Grenander andMiller (1994) and Phillips and Smith (1996), where broader descriptions of continuous timeapproaches can be found. In particular, Ripley (1977) introduced the concept of simulating abirth-and-death process to approximate its limiting distribution, even though he was interestedin a problem of fixed dimension, whereas Geyer and Møller (1994) proposed a Metropolis–Hastings algorithm for spatial point processes and argued the superiority of this scheme com-pared with a continuous time approach, as did Clifford and Nicholls (1994).2.1. A reference example: mixture modelsOur bench-mark is a mixture model, with probability density function of the formp.y|k, w, / =ki=1wif.y|φi/,where k is the unknown number of components, w = .w1,...,wk/ are the component weights, = .φ1,...,φk/ are the component parameters and f.·|φ/ is some parametric class of densitiesReversible Jump and Continuous Time Markov Chain Monte Carlo Samplers 681indexed by a parameter φ, like the Gaussian, the gamma, the beta or the Poisson family.The component weights