Faming Liang, Associate Professor, Department of Statistics, Texas A&M University. Chuanhai Liu, Professor, Department of Statistics, Purdue University. Raymond J. Carroll, Distinguished Professor, Department of Statistics, Texas A&M University.

"The book is suitable as a textbook for one-semester courses on Monte Carlo methods, offered at the advance postgraduate levels." (Mathematical Reviews, 1 December 2012)"Researchers working in the field of applied statistics will profit from this easy-to-access presentation. Further illustration is done by discussing interesting examples and relevant applications. The valuable reference list includes technical reports which are hard to and by searching in public data bases." (Zentralblatt MATH, 2011)"This book can be used as a textbook or a reference book for a one-semester graduate course in statistics, computational biology, engineering, and computer sciences. Applied or theoretical researchers will also find this book beneficial." (Breitbart.com: Business Wire , 1 February 2011)"The Markov Chain Monte Carlo method has now become the dominant methodology for solving many classes of computational problems in science and technology." (SciTech Book News, December 2010)

• Preface xiiiAcknowledgments xviiPublisher’s Acknowledgments xix1 Bayesian Inference and Markov Chain Monte Carlo 11.1 Bayes 11.1.1 Specification of Bayesian Models 21.1.2 The Jeffreys Priors and Beyond 21.2 Bayes Output 41.2.1 Credible Intervals and Regions 41.2.2 Hypothesis Testing: Bayes Factors 51.3 Monte Carlo Integration 81.3.1 The Problem 81.3.2 Monte Carlo Approximation 91.3.3 Monte Carlo via Importance Sampling 91.4 Random Variable Generation 101.4.1 Direct or Transformation Methods 11.4.2 Acceptance-Rejection Methods 111.4.3 The Ratio-of-Uniforms Method and Beyond 141.4.4 Adaptive Rejection Sampling 181.4.5 Perfect Sampling 181.5 Markov Chain Monte Carlo 181.5.1 Markov Chains 181.5.2 Convergence Results 201.5.3 Convergence Diagnostics 23Exercises 242 The Gibbs Sampler 272.1 The Gibbs Sampler 272.2 Data Augmentation 302.3 Implementation Strategies and Acceleration Methods 332.3.1 Blocking and Collapsing 332.3.2 Hierarchical Centering and Reparameterization 342.3.3 Parameter Expansion for Data Augmentation 352.3.4 Alternating Subspace-Spanning Resampling 432.4 Applications 452.4.1 The Student-t Model 452.4.2 Robit Regression or Binary Regression with the Student-t Link 472.4.3 Linear Regression with Interval-Censored Responses 50Exercises 54Appendix 2A: The EM and PX-EM Algorithms 563 The Metropolis-Hastings Algorithm 593.1 The Metropolis-Hastings Algorithm 593.1.1 Independence Sampler 623.1.2 Random Walk Chains 633.1.3 Problems with Metropolis-Hastings Simulations 633.2 Variants of the Metropolis-Hastings Algorithm 653.2.1 The Hit-and-Run Algorithm. 653.2.2 The Langevin Algorithm 653.2.3 The Multiple-Try MH Algorithm 663.3 Reversible Jump MCMC Algorithm for Bayesian Model Selection Problems 673.3.1 Reversible Jump MCMC Algorithm 673.3.2 Change-Point Identification 703.4 Metropolis-Within-Gibbs Sampler for ChIP-chip Data Analysis 753.4.1 Metropolis-Within-Gibbs Sampler 753.4.2 Bayesian Analysis for ChIP-chip Data 76Exercises 834 Auxiliary Variable MCMC Methods 854.1 Simulated Annealing 864.2 Simulated Tempering 884.3 The Slice Sampler 904.4 The Swendsen-Wang Algorithm 914.5 The Wolff Algorithm 934.6 The Mo/ller Algorithm 954.7 The Exchange Algorithm 974.8 The Double MH Sampler 984.8.1 Spatial Autologistic Models 994.9 Monte Carlo MH Sampler 1034.9.1 Monte Carlo MH Algorithm 1034.9.2 Convergence 1074.9.3 Spatial Autologistic Models (Revisited) 1104.9.4 Marginal Inference 1114.10 Applications 1134.10.1 Autonormal Models 1144.10.2 Social Networks 116Exercises 1215 Population-Based MCMC Methods 1235.1 Adaptive Direction Sampling 1245.2 Conjugate Gradient Monte Carlo 1255.3 Sample Metropolis-Hastings Algorithm 1265.4 Parallel Tempering 1275.5 Evolutionary Monte Carlo 1285.5.1 Evolutionary Monte Carlo in Binary-Coded Space 1295.5.2 Evolutionary Monte Carlo in Continuous Space 1325.5.3 Implementation Issues 1335.5.4 Two Illustrative Examples 1345.5.5 Discussion 1395.6 Sequential Parallel Tempering for Simulation of High Dimensional Systems 1405.6.1 Build-up Ladder Construction 1415.6.2 Sequential Parallel Tempering 1425.6.3 An Illustrative Example: the Witch’s Hat Distribution 1425.6.4 Discussion 1455.7 Equi-Energy Sampler 1465.8 Applications 1485.8.1 Bayesian Curve Fitting 1485.8.2 Protein Folding Simulations: 2D HP Model 1535.8.3 Bayesian Neural Networks for Nonlinear Time Series Forecasting 156Exercises 162Appendix 5A: Protein Sequences for 2D HP Models 1636 Dynamic Weighting 1656.1 Dynamic Weighting 1656.1.1 The IWIW Principle 1656.1.2 Tempering Dynamic Weighting Algorithm 1676.1.3 Dynamic Weighting in Optimization 1716.2 Dynamically Weighted Importance Sampling 1736.2.1 The Basic Idea 1736.2.2 A Theory of DWIS 1746.2.3 Some IWIWp Transition Rules 1766.2.4 Two DWIS Schemes 1796.2.5 Weight Behavior Analysis 1806.2.6 A Numerical Example 1836.3 Monte Carlo Dynamically Weighted Importance Sampling 1856.3.1 Sampling from Distributions with Intractable Normalizing Constants 1856.3.2 Monte Carlo Dynamically Weighted Importance Sampling 1866.3.3 Bayesian Analysis for Spatial Autologistic Models 1916.4 Sequentially Dynamically Weighted Importance Sampling 195Exercises 1977 Stochastic Approximation Monte Carlo 1997.1 Multicanonical Monte Carlo 2007.2 1/k-Ensemble Sampling 2027.3 The Wang-Landau Algorithm 2047.4 Stochastic Approximation Monte Carlo 2077.5 Applications of Stochastic Approximation Monte Carlo 2187.5.1 Efficient p-Value Evaluation for Resampling-Based Tests 2187.5.2 Bayesian Phylogeny Inference 2227.5.3 Bayesian Network Learning 2277.6 Variants of Stochastic Approximation Monte Carlo 2337.6.1 Smoothing SAMC for Model Selection Problems 2337.6.2 Continuous SAMC for Marginal Density Estimation 2397.6.3 Annealing SAMC for Global Optimization 2447.7 Theory of Stochastic Approximation Monte Carlo 2537.7.1 Convergence 2537.7.2 Convergence Rate 2677.7.3 Ergodicity and its IWIW Property 2717.8 Trajectory Averaging: Toward the Optimal Convergence Rate 2757.8.1 Trajectory Averaging for a SAMCMC Algorithm 2777.8.2 Trajectory Averaging for SAMC 2797.8.3 Proof of Theorems 7.8.2 and 7.8.3 281Exercises 296Appendix 7A: Test Functions for Global Optimization 2988 Markov Chain Monte Carlo with Adaptive Proposals 3058.1 Stochastic Approximation-Based Adaptive Algorithms 3068.1.1 Ergodicity and Weak Law of Large Numbers 3078.1.2 Adaptive Metropolis Algorithms 3098.2 Adaptive Independent Metropolis-Hastings Algorithms 3128.3 Regeneration-Based Adaptive Algorithms 3158.3.1 Identification of Regeneration Times 3158.3.2 Proposal Adaptation at Regeneration Times 3178.4 Population-Based Adaptive Algorithms 3178.4.1 ADS, EMC, NKC and More 3178.4.2 Adaptive EMC 3188.4.3 Application to Sensor Placement Problems 323Exercises 324References 327Index 353

Faming Liang, Associate Professor, Department of Statistics, Texas A&M University. Chuanhai Liu, Professor, Department of Statistics, Purdue University. Raymond J. Carroll, Distinguished Professor, Department of Statistics, Texas A&M University.

"The book is suitable as a textbook for one-semester courses on Monte Carlo methods, offered at the advance postgraduate levels." (Mathematical Reviews, 1 December 2012)"Researchers working in the field of applied statistics will profit from this easy-to-access presentation. Further illustration is done by discussing interesting examples and relevant applications. The valuable reference list includes technical reports which are hard to and by searching in public data bases." (Zentralblatt MATH, 2011)"This book can be used as a textbook or a reference book for a one-semester graduate course in statistics, computational biology, engineering, and computer sciences. Applied or theoretical researchers will also find this book beneficial." (Breitbart.com: Business Wire , 1 February 2011)"The Markov Chain Monte Carlo method has now become the dominant methodology for solving many classes of computational problems in science and technology." (SciTech Book News, December 2010)

• Preface xiiiAcknowledgments xviiPublisher’s Acknowledgments xix1 Bayesian Inference and Markov Chain Monte Carlo 11.1 Bayes 11.1.1 Specification of Bayesian Models 21.1.2 The Jeffreys Priors and Beyond 21.2 Bayes Output 41.2.1 Credible Intervals and Regions 41.2.2 Hypothesis Testing: Bayes Factors 51.3 Monte Carlo Integration 81.3.1 The Problem 81.3.2 Monte Carlo Approximation 91.3.3 Monte Carlo via Importance Sampling 91.4 Random Variable Generation 101.4.1 Direct or Transformation Methods 11.4.2 Acceptance-Rejection Methods 111.4.3 The Ratio-of-Uniforms Method and Beyond 141.4.4 Adaptive Rejection Sampling 181.4.5 Perfect Sampling 181.5 Markov Chain Monte Carlo 181.5.1 Markov Chains 181.5.2 Convergence Results 201.5.3 Convergence Diagnostics 23Exercises 242 The Gibbs Sampler 272.1 The Gibbs Sampler 272.2 Data Augmentation 302.3 Implementation Strategies and Acceleration Methods 332.3.1 Blocking and Collapsing 332.3.2 Hierarchical Centering and Reparameterization 342.3.3 Parameter Expansion for Data Augmentation 352.3.4 Alternating Subspace-Spanning Resampling 432.4 Applications 452.4.1 The Student-t Model 452.4.2 Robit Regression or Binary Regression with the Student-t Link 472.4.3 Linear Regression with Interval-Censored Responses 50Exercises 54Appendix 2A: The EM and PX-EM Algorithms 563 The Metropolis-Hastings Algorithm 593.1 The Metropolis-Hastings Algorithm 593.1.1 Independence Sampler 623.1.2 Random Walk Chains 633.1.3 Problems with Metropolis-Hastings Simulations 633.2 Variants of the Metropolis-Hastings Algorithm 653.2.1 The Hit-and-Run Algorithm. 653.2.2 The Langevin Algorithm 653.2.3 The Multiple-Try MH Algorithm 663.3 Reversible Jump MCMC Algorithm for Bayesian Model Selection Problems 673.3.1 Reversible Jump MCMC Algorithm 673.3.2 Change-Point Identification 703.4 Metropolis-Within-Gibbs Sampler for ChIP-chip Data Analysis 753.4.1 Metropolis-Within-Gibbs Sampler 753.4.2 Bayesian Analysis for ChIP-chip Data 76Exercises 834 Auxiliary Variable MCMC Methods 854.1 Simulated Annealing 864.2 Simulated Tempering 884.3 The Slice Sampler 904.4 The Swendsen-Wang Algorithm 914.5 The Wolff Algorithm 934.6 The Mo/ller Algorithm 954.7 The Exchange Algorithm 974.8 The Double MH Sampler 984.8.1 Spatial Autologistic Models 994.9 Monte Carlo MH Sampler 1034.9.1 Monte Carlo MH Algorithm 1034.9.2 Convergence 1074.9.3 Spatial Autologistic Models (Revisited) 1104.9.4 Marginal Inference 1114.10 Applications 1134.10.1 Autonormal Models 1144.10.2 Social Networks 116Exercises 1215 Population-Based MCMC Methods 1235.1 Adaptive Direction Sampling 1245.2 Conjugate Gradient Monte Carlo 1255.3 Sample Metropolis-Hastings Algorithm 1265.4 Parallel Tempering 1275.5 Evolutionary Monte Carlo 1285.5.1 Evolutionary Monte Carlo in Binary-Coded Space 1295.5.2 Evolutionary Monte Carlo in Continuous Space 1325.5.3 Implementation Issues 1335.5.4 Two Illustrative Examples 1345.5.5 Discussion 1395.6 Sequential Parallel Tempering for Simulation of High Dimensional Systems 1405.6.1 Build-up Ladder Construction 1415.6.2 Sequential Parallel Tempering 1425.6.3 An Illustrative Example: the Witch’s Hat Distribution 1425.6.4 Discussion 1455.7 Equi-Energy Sampler 1465.8 Applications 1485.8.1 Bayesian Curve Fitting 1485.8.2 Protein Folding Simulations: 2D HP Model 1535.8.3 Bayesian Neural Networks for Nonlinear Time Series Forecasting 156Exercises 162Appendix 5A: Protein Sequences for 2D HP Models 1636 Dynamic Weighting 1656.1 Dynamic Weighting 1656.1.1 The IWIW Principle 1656.1.2 Tempering Dynamic Weighting Algorithm 1676.1.3 Dynamic Weighting in Optimization 1716.2 Dynamically Weighted Importance Sampling 1736.2.1 The Basic Idea 1736.2.2 A Theory of DWIS 1746.2.3 Some IWIWp Transition Rules 1766.2.4 Two DWIS Schemes 1796.2.5 Weight Behavior Analysis 1806.2.6 A Numerical Example 1836.3 Monte Carlo Dynamically Weighted Importance Sampling 1856.3.1 Sampling from Distributions with Intractable Normalizing Constants 1856.3.2 Monte Carlo Dynamically Weighted Importance Sampling 1866.3.3 Bayesian Analysis for Spatial Autologistic Models 1916.4 Sequentially Dynamically Weighted Importance Sampling 195Exercises 1977 Stochastic Approximation Monte Carlo 1997.1 Multicanonical Monte Carlo 2007.2 1/k-Ensemble Sampling 2027.3 The Wang-Landau Algorithm 2047.4 Stochastic Approximation Monte Carlo 2077.5 Applications of Stochastic Approximation Monte Carlo 2187.5.1 Efficient p-Value Evaluation for Resampling-Based Tests 2187.5.2 Bayesian Phylogeny Inference 2227.5.3 Bayesian Network Learning 2277.6 Variants of Stochastic Approximation Monte Carlo 2337.6.1 Smoothing SAMC for Model Selection Problems 2337.6.2 Continuous SAMC for Marginal Density Estimation 2397.6.3 Annealing SAMC for Global Optimization 2447.7 Theory of Stochastic Approximation Monte Carlo 2537.7.1 Convergence 2537.7.2 Convergence Rate 2677.7.3 Ergodicity and its IWIW Property 2717.8 Trajectory Averaging: Toward the Optimal Convergence Rate 2757.8.1 Trajectory Averaging for a SAMCMC Algorithm 2777.8.2 Trajectory Averaging for SAMC 2797.8.3 Proof of Theorems 7.8.2 and 7.8.3 281Exercises 296Appendix 7A: Test Functions for Global Optimization 2988 Markov Chain Monte Carlo with Adaptive Proposals 3058.1 Stochastic Approximation-Based Adaptive Algorithms 3068.1.1 Ergodicity and Weak Law of Large Numbers 3078.1.2 Adaptive Metropolis Algorithms 3098.2 Adaptive Independent Metropolis-Hastings Algorithms 3128.3 Regeneration-Based Adaptive Algorithms 3158.3.1 Identification of Regeneration Times 3158.3.2 Proposal Adaptation at Regeneration Times 3178.4 Population-Based Adaptive Algorithms 3178.4.1 ADS, EMC, NKC and More 3178.4.2 Adaptive EMC 3188.4.3 Application to Sensor Placement Problems 323Exercises 324References 327Index 353