Honest Exploration of Intractable Probability Distributions via Markov Chain Monte Carlo
Statistical SciencePublished 1 November 2001Open access
James P. Hobert, Galin L. Jones
Citations256
SJR quartileQ1
SJR score1.67
SNIP2.24
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The goal of this paper is to demystify the analysis that leads to honest answers to (Q1) and (Q2) and to serve as a bridge between those developing Markov chain theory and practitioners using MCMC to solve practical problems.
Abstract
Two important questions that must be answered whenever a Markov\nchain Monte Carlo (MCMC) algorithm is used are (Q1) What is an appropriate\nburn-in? and (Q2) How long should the sampling continue after\nburn-in?Developing rigorous answers to these questions presently requires a\ndetailed study of the convergence properties of the underlying Markov chain.\nConsequently, in most practical applications of MCMC, exact answers to (Q1)and\n(Q2) are not sought. The goal of this paper is to demystify the analysis that\nleads to honest answers to (Q1) and (Q2). The authors hope that this article\nwill serve as a bridge between those developing Markov chain theory and\npractitioners using MCMC to solve practical problems.\n¶ The ability to address (Q1) and (Q2) formally comes from\nestablishing a drift condition and an associated minorization\ncondition, which together imply that the underlying Markov chain is\ngeometrically ergodic. In this article, we explain exactly what drift\nand minorization are as well as how and why these conditions can be used to\nform rigorous answers to (Q1) and (Q2). The basic ideas are as follows. The\nresults of Rosenthal (1995) and Roberts and Tweedie (1999) allow one to use\ndrift and minorization conditions to construct a formula giving an\nanalytic upper bound on the distance to stationarity. A rigorous answer to (Q1)\ncan be calculated using this formula. The desired characteristics of the target\ndistribution are typically estimated using ergodic averages. Geometric\nergodicity of the underlying Markov chain implies that there are central limit\ntheorems available for ergodic averages (Chan and Geyer 1994). The regenerative\nsimulation technique (Mykland, Tierney and Yu, 1995; Robert, 1995) can be used\nto get a consistent estimate of the variance of the asymptotic normal\ndistribution. Hence, an asymptotic standard error can be calculated, which\nprovides an answer to (Q2) in the sense that an appropriate time to stop\nsampling can be determined. The methods are illustrated using a Gibbs sampler\nfor a Bayesian version of the one-way random effects model and a data set\nconcerning styrene exposure.
Keywords
Computer ScienceMathematics
Markov Chain Monte Carlo in Practice
7,730 Citations1995Walter R. Gilks, Sylvia Richardson +1 more
Journal of the American Statistical AssociationSampling-Based Approaches to Calculating Marginal Densities
6,616 Citations1990Alan E. Gelfand, A. F. M. Smith
Stochastic substitution, the Gibbs sampler, and the sampling-importance-resampling algorithm can be viewed as three alternative sampling- (or Monte Carlo-) based approaches to the calculation of numerical estimates of marginal probability distributions.
TechnometricsMonte Carlo Statistical Methods
5,612 Citations2000Hoon Kim, Christian P. Robert +1 more
Markov Chains and Stochastic Stability
5,130 Citations1993Sean Meyn, Richard L. Tweedie
This second edition reflects the same discipline and style that marked out the original and helped it to become a classic: proofs are rigorous and concise, the range of applications is broad and knowledgeable, and key ideas are accessible to practitioners with limited mathematical background.
The American StatisticianUnderstanding the Metropolis-Hastings Algorithm
3,714 Citations1995Siddhartha Chib, Edward Greenberg
A detailed, introductory exposition of the Metropolis-Hastings algorithm, a powerful Markov chain method to simulate multivariate distributions, and a simple, intuitive derivation of this method is given along with guidance on implementation.
The Annals of StatisticsMarkov Chains for Exploring Posterior Distributions
3,472 Citations1994Luke Tierney
This paper outlines some of the basic methods and strategies of Markov chain methods and discusses some related theoretical and practical issues.
Springer texts in statisticsMonte Carlo Statistical Methods
2,245 Citations1999Christian P. Robert, George Casella
Wiley series in probability and statisticsVariance Components
1,918 Citations1992S. R. Searle, George Casella +1 more
Journal of the American Statistical AssociationSampling-Based Approaches to Calculating Marginal Densities
1,519 Citations1990Alan E. Gelfand, A. F. M. Smith
CERN Document Server (European Organization for Nuclear Research)Lectures on the Coupling Method
1,168 Citations1992Torgny Lindvall
Journal of Computational and Graphical StatisticsThe Art of Data Augmentation
1,076 Citations2001David A. van Dyk, Xiao‐Li Meng
An effective search strategy is introduced that combines the ideas of marginal augmentation and conditional augmentation, together with a deterministic approximation method for selecting good augmentation schemes to obtain efficient Markov chain Monte Carlo algorithms for posterior sampling.
Journal of the American Statistical AssociationIllustration of Bayesian Inference in Normal Data Models Using Gibbs Sampling
966 Citations1990Alan E. Gelfand, Susan E. Hills +2 more
The use of the Gibbs sampler as a method for calculating Bayesian marginal posterior and predictive densities is reviewed and illustrated with a range of normal data models, including variance components, unordered and ordered means, hierarchical growth curves, and missing data in a crossover trial.
Statistical ScienceBayesian Computation and Stochastic Systems
953 Citations1995Julian Besag, Peter Green +2 more
Basic methodology of MCMC is presented, emphasizing the Bayesian paradigm, conditional probability and the intimate relationship with Markov random fields in spatial statistics, and particular emphasis on the calculation of posterior probabilities.
The Annals of Applied ProbabilityGeometric Bounds for Eigenvalues of Markov Chains
886 Citations1991Persi Diaconis, Daniel W. Stroock
Journal of the American Statistical AssociationAnnealing Markov Chain Monte Carlo with Applications to Ancestral Inference
845 Citations1995Charles J. Geyer, E. A. Thompson
This work proposes MCMC methods distantly related to simulated annealing, which simulate realizations from a sequence of distributions, allowing the distribution being simulated to vary randomly over time.
Journal of the American Statistical AssociationMaximum Likelihood Algorithms for Generalized Linear Mixed Models
739 Citations1997Charles E. McCulloch
Journal of the American Statistical AssociationThe Calculation of Posterior Distributions by Data Augmentation
718 Citations1987Martin A. Tanner, Wing Hung Wong
The Annals of StatisticsAlgebraic algorithms for sampling from conditional distributions
663 Citations1998Persi Diaconis, Bernd Sturmfels
This work constructs Markov chain algorithms for sampling from discrete exponential families conditional on a sufficient statistic for examples including contingency tables, logistic regression, and spectral analysis of permutation data.
Cambridge University Press eBooksGeneral Irreducible Markov Chains and Non-Negative Operators
629 Citations1984Esa Nummelin
Journal of the Royal Statistical Society Series A (General)General Irreducible Markov Chains and Non-Negative Operators.
613 Citations1985M. Bhaskara Rao, Esa Nummelin
The Annals of StatisticsRates of convergence of the Hastings and Metropolis algorithms
570 Citations1996Kerrie Mengersen, Richard L. Tweedie
Recent results in Markov chain theory are applied to Hastings and Metropolis algorithms with either independent or symmetric candidate distributions, and it is shown geometric convergence essentially occurs if and only if $pi$ has geometric tails.
BiometrikaCovariance structure of the Gibbs sampler with applications to the comparisons of estimators and augmentation schemes
540 Citations1994Jun S. Liu, Wing Hung Wong +1 more
It is proved that Rao-Blackwellization causes a one-lag delay for the autocovariances among dependent samples obtained from data augmentation, and consequently, the mixture approximation produces estimates with smaller variances than the empirical approximation.
Journal of the American Statistical AssociationMinorization Conditions and Convergence Rates for Markov Chain Monte Carlo
463 Citations1995Jeffrey S. Rosenthal
Transactions of the American Mathematical SocietyA new approach to the limit theory of recurrent Markov chains
418 Citations1978Krishna B. Athreya, Peter Ney
Journal of the Royal Statistical Society Series B (Statistical Methodology)Updating Schemes, Correlation Structure, Blocking and Parameterization for the Gibbs Sampler
414 Citations1997Gareth O. Roberts, Sujit K. Sahu
Exact computable rates of convergence for Gaussian target distributions are obtained and different random and non‐random updating strategies and blocking combinations are compared using the rates.
BiometrikaGeometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms
412 Citations1996Gareth O. Roberts
Results on geometric ergodicity of Markov chains are developed and central limit theorems for the Metropolis algorithm are developed, showing that the negative-definiteness property is not redundant.
Operations ResearchBatch Size Effects in the Analysis of Simulation Output
372 Citations1982Bruce W. Schmeiser
This paper quantifies the effects of using batch sizes larger than necessary to satisfy normality and independence assumptions and finds that the effects are large and small, respectively.
The Annals of Applied ProbabilityA note on Metropolis-Hastings kernels for general state spaces
345 Citations1998Luke Tierney
Probability Theory and Related FieldsA splitting technique for Harris recurrent Markov chains
323 Citations1978Esa Nummelin
The Annals of Applied ProbabilityComputable Bounds for Geometric Convergence Rates of Markov Chains
299 Citations1994Sean Meyn, Richard L. Tweedie
Journal of the American Statistical AssociationAdaptive Markov Chain Monte Carlo through Regeneration
284 Citations1998Walter R. Gilks, Gareth O. Roberts +1 more
A framework is described, based on the concept of Markov chain regeneration, which allows adaptation to occur infinitely often but does not disturb the stationary distribution of the chain or the consistency of sample path averages.
Operations ResearchSimulating Stable Stochastic Systems: III. Regenerative Processes and Discrete-Event Simulations
282 Citations1975Michael A. Crane, Donald L. Iglehart
This paper shows that a previously developed technique for analyzing simulations of GI/G/s queues and Markov chains applies to discrete-event simulations that can be modeled as regenerative processes.
Journal of Computational and Graphical StatisticsImplementations of the Monte Carlo EM Algorithm
237 Citations2001Richard A. Levine, George Casella
The Monte Carlo EM (MCEM) algorithm is a modification of the EM algorithm where the expectation in the E-step is computed numerically through Monte Carlo simulations and an automated rule is applied for increasing the Monte Carlo sample size whenthe Monte Carlo error overwhelms the EM estimate at any given iteration.
Mathematics of Operations ResearchSimulation Output Analysis Using Standardized Time Series
237 Citations1990Peter W. Glynn, Donald L. Iglehart
The goal in this paper is to generalize the STS method and to study some of its basic properties, finding a lower bound is obtained for the expected length of the asymptotic as the run size becomes large STS confidence intervals.
Journal of the American Statistical AssociationRegeneration in Markov Chain Samplers
222 Citations1995Per A. Mykland, Luke Tierney +1 more
The use of Markov chain splitting, originally developed for the theoretical analysis of general state-space Markov chains, is discussed, to introduce regeneration into MarkovChain samplers, which allows the use of regenerative methods for analyzing the output of these sampler output and can provide a useful diagnostic of sampler performance.
Stochastic Processes and their ApplicationsGeometric ergodicity of Metropolis algorithms
221 Citations2000Søren Fiig Jarner, Ernst Hansen
It is shown that at least exponentially light tails of the target density is a necessity and conditions for geometric ergodicity of the random-walk-based Metropolis algorithm are derived.
The Annals of Applied ProbabilityPolynomial Convergence Rates of Markov Chains
189 Citations2002Søren Fiig Jarner, Gareth O. Roberts
Journal of the American Statistical AssociationMaximum Likelihood Algorithms for Generalized Linear Mixed Models
165 Citations1997Charles E. McCulloch
Stochastic Processes and their ApplicationsBounds on regeneration times and convergence rates for Markov chainsfn1fn1Work supported in part by NSF Grant DMS 9504561 and EPSRC grant GR/J19900.
154 Citations1999Gareth O. Roberts, Richard L. Tweedie
Canadian Journal of StatisticsMarkov‐chain monte carlo: Some practical implications of theoretical results
142 Citations1998Gareth O. Roberts, Jeffrey S. Rosenthal
This work reviews and discusses some recent progress in the theory of Markov-chain Monte Carlo applications and attempts to assess the relevance of this theory for practical applications.
Journal of the Royal Statistical Society Series B (Statistical Methodology)Convergence of Slice Sampler Markov Chains
136 Citations1999Gareth O. Roberts, Jeffrey S. Rosenthal
Statistical ScienceConvergence Control Methods for Markov Chain Monte Carlo Algorithms
114 Citations1995Christian P. Robert
Different approaches toward the control of convergence for Markov chain Monte Carlo algorithms are presented based on functional and mixing theories, while paying particular attention to the central limit theorem and to the approximation of the limiting variance.
BiometrikaOn the applicability of regenerative simulation in Markov chain Monte Carlo
114 Citations2002James P. Hobert
Mathematics of Operations ResearchGeometric Convergence Rates for Stochastically Ordered Markov Chains
108 Citations1996Robert Lund, Richard L. Tweedie
A dependent sample path coupling and a Foster-Lyapunov drift inequality are used to derive convergence rate bounds and it is shown that the bounds obtained are frequently the best possible.
Journal of the American Statistical AssociationMinorization Conditions and Convergence Rates for Markov Chain Monte Carlo
85 Citations1995Jeffrey S. Rosenthal
Journal of the Royal Statistical Society Series B (Statistical Methodology)Convergence Rates of the Gibbs Sampler, the Metropolis Algorithm and Other Single-Site Updating Dynamics
83 Citations1993Arnoldo Frigessi, P. Di Stefano +2 more
Journal of Computational and Graphical StatisticsGibbs Sampling with Diffuse Proper Priors: A Valid Approach to Data-Driven Inference?
82 Citations1998Ranjini Natarajan, Charles E. McCulloch
It is demonstrated by example that the use of the Gibbs sampler with diffuse proper priors can lead to inaccurate posterior estimates, and that such inaccuracies are not merely limited to small sample settings.
Statistics and ComputingAnalysis of the Gibbs sampler for a model related to James-Stein estimators
75 Citations1996Jeffrey S. Rosenthal
A hierarchical Bayes model which is related to the usual empirical Bayes formulation of James-Stein estimators is analysed, and it is proved that the Gibbs sampler will fail to converge, and the associated posterior distribution is non-normalizable.
Journal of Multivariate AnalysisGeometric Ergodicity of Gibbs and Block Gibbs Samplers for a Hierarchical Random Effects Model
74 Citations1998James P. Hobert, Charles J. Geyer
Statistical ScienceA Geometric Interpretation of the Metropolis-Hastings Algorithm
68 Citations2001Louis J. Billera, Persi Diaconis
The Metropolis-Hastings algorithm transforms a given stochastic matrix into a reversible stochastics matrix with a prescribed stationary distribution and gives the min- imum distance solution in an L 1 metric.
Journal of the American Statistical AssociationAdaptive Markov Chain Monte Carlo through Regeneration
56 Citations1998Walter R. Gilks, Gareth O. Roberts +1 more
Transactions of the American Mathematical SocietyA New Approach to the Limit Theory of Recurrent Markov Chains
44 Citations1978Krishna B. Athreya, P. Ney
Statistics and ComputingA simulation approach to convergence rates for Markov chain Monte Carlo algorithms
44 Citations1998Mary Kathryn Cowles, Jeffrey S. Rosenthal
This paper proposes the use of auxiliary simulations to estimate the numerical values needed in this theorem and makes it possible to compute quantitative convergence bounds for models for which the requisite analytical computations would be prohibitively difficult or impossible.
The Annals of Applied ProbabilityOn the Rate of Convergence of the Metropolis Algorithm and Gibbs Sampler by Geometric Bounds
44 Citations1994Salvatore Ingrassia
Journal of the American Statistical AssociationRegeneration in Markov Chain Samplers
39 Citations1995Per A. Mykland, Luke Tierney +1 more
Annals of Operations ResearchA joint central limit theorem for the sample mean and regenerative variance estimator
34 Citations1987Peter W. Glynn, Donald L. Iglehart
Journal of Applied ProbabilityA note on acceptance rate criteria for CLTS for Metropolis–Hastings algorithms
26 Citations1999Gareth O. Roberts
This paper considers positive recurrent Markov chains where the probability of remaining in the current state is arbitrarily close to 1 and conditions are given which ensure the non-existence of central limit theorems for ergodic averages of functionals of the chain.
The Annals of Applied ProbabilityOn convergence rates of Gibbs samplers for uniform distributions
23 Citations1998Gareth O. Roberts, Jeffrey S. Rosenthal
It is shown that the convergence properties of the Gibbs sampler depend greatly on the smoothness of the boundary of R, and for sufficiently smooth boundaries the sampler is uniformly ergodic, while for jagged boundaries theSampler could fail to even be geometrically er godic.
A review of asymptotic convergence for general state space Markov chains
21 Citations2002Stephanie Rosenthal
Stochastic Processes and their ApplicationsApplications of geometric bounds to the convergence rate of Markov chains on Rn
19 Citations2000Wai Kong Yuen
Operations Research LettersRegenerative structure of Markov chains simulated via common random numbers
12 Citations1985Peter W. Glynn
Stochastic Processes and their ApplicationsCorrigendum to “Bounds on regeneration times and convergence rates for Markov chains”
12 Citations2001Gareth O. Roberts, Richard L. Tweedie
Journal of the American Statistical AssociationDiscretization of Continuous Markov Chains and Markov Chain Monte Carlo Convergence Assessment
5 Citations1998Chantal Guihenneuc‐Jouyaux, Christian P. Robert