Efficiency of Markov Chain Monte Carlo for Bayesian Computation

• Activity Number: 621
• Type: Invited
• Date/Time: Thursday, August 8, 2013 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Computing
• Author(s): Dawn B Woodard*+
• Companies: Cornell University
• Keywords: Markov chain ; computing ; Bayesian ; genomics ; mixture models ; efficiency

Abstract

We analyze the efficiency of Markov chain methods used in Bayesian computation. While convergence diagnosis is used to choose how long to run a Markov chain, it can be inaccurate and does not provide insight as to how the efficiency scales with the number of parameters or other quantities of interest. We instead characterize the number of iterations of the Markov chain required to guarantee a fixed accuracy (the run time). We show that in many situations where the likelihood satisfies local asymptotic normality, the Markov chain run time grows linearly in the number of observations n, if the chain is initialized close to the MLE. If the chain is initialized far from the MLE, it can become trapped in local modes of the likelihood function, causing the run time to grow exponentially in n. We apply our results to Metropolis-Hastings for mixture models, showing that if the data are generated from a mixture with more components than in the model, then the chain has exponentially long run time. We also analyze a popular Gibbs sampling method for discovery of gene regulatory binding motifs, showing that the run time often increases exponentially in the length of the DNA sequence.