Monte Carlo Statistical Methods

Description

Monte Carlo statistical methods, particularly those based on Markov chains, are now an essential component of the standard set of techniques used by statisticians. This new edition has been revised towards a coherent and flowing coverage of these simulation techniques, with incorporation of the most recent developments in the field. In particular, the introductory coverage of random variable generation has been totally revised, with many concepts being unified through a fundamental theorem of simulation There are five completely new chapters that cover Monte Carlo control, reversible jump, slice sampling, sequential Monte Carlo, and perfect sampling. There is a more in-depth coverage of Gibbs sampling, which is now contained in three consecutive chapters. The development of Gibbs sampling starts with slice sampling and its connection with the fundamental theorem of simulation, and builds up to two-stage Gibbs sampling and its theoretical properties. A third chapter covers the multi-stage Gibbs sampler and its variety of applications. Lastly, chapters from the previous edition have been revised towards easier access, with the examples getting more detailed coverage. This textbook is intended for a second year graduate course, but will also be useful to someone who either wants to apply simulation techniques for the resolution of practical problems or wishes to grasp the fundamental principles behind those methods. The authors do not assume familiarity with Monte Carlo techniques (such as random variable generation), with computer programming, or with any Markov chain theory (the necessary concepts are developed in Chapter 6). A solutions manual, which covers approximately 40% of the problems, is available for instructors who require the book for a course. Christian P. Robert is Professor of Statistics in the Applied Mathematics Department at Universit� Paris Dauphine, France. He is also Head of the Statistics Laboratory at the Center for Research in Economics and Statistics (CREST) of the National Institute for Statistics and Economic Studies (INSEE) in Paris, and Adjunct Professor at Ecole Polytechnique. He has written three other books, including The Bayesian Choice, Second Edition, Springer 2001. He also edited Discretization and MCMC Convergence Assessment, Springer 1998. He has served as associate editor for the Annals of Statistics and the Journal of the American Statistical Association. He is a fellow of the Institute of Mathematical Statistics, and a winner of the Young Statistician Award of the Societi� de Statistique de Paris in 1995. George Casella is Distinguished Professor and Chair, Department of Statistics, University of Florida. He has served as the Theory and Methods Editor of the Journal of the American Statistical Association and Executive Editor of Statistical Science. He has authored three other textbooks: Statistical Inference, Second Edition, 2001, with Roger L. Berger; Theory of Point Estimation, 1998, with Erich Lehmann; and Variance Components, 1992, with Shayle R. Searle and Charles E. McCulloch. He is a fellow of the Institute of Mathematical Statistics and the American Statistical Association, and an elected fellow of the International Statistical Institute. Cover Page Title Page Copyright Page Dedication Page Preface to Second Edition Preface to First Edition Table of Contents List of Tables List of Figures 1 Introduction 1.1 Statistical Models 1.2 Likelihood Methods 1.3 Bayesian Methods 1.4 Deterministic Numerical Methods 1.4.1 Optimization 1.4.2 Integration 1.4.3 Comparison 1.5 Problems 1.6 Notes 1.6.1 Prior Distributions 1.6.2 Bootstrap Methods 2 Random V^ariable Generation 2.1 Introduction 2.1.1 Uniform Simulation 2.1.2 The Inverse Transform 2.1.3 Alternatives 2.1.4 Optimal Algorithms 2.2 General Transformation Methods 2.3 Accept-Reject Methods 2.3.1 The Fundamental Theorem of Simulation 2.3.2 The Accept-Reject Algorithm 2.4 Envelope Accept-Reject Methods 2.4.1 The Squeeze Principle 2.4.2 Log-Concave Densities 2.5 Problems 2.6 Notes 2.6.1 The Kiss Generator 2.6.2 Quasi-Monte Carlo Methods 2.6.3 Mixture Representations 3 Monte Carlo Integration 3.1 Introduction 3.2 Classical Monte Carlo Integration 3.3 Importance Sampling 3.3.1 Principles 3.3.2 Finite Variance Estimators 3.3.3 Comparing Importance Sampling with Accept-Reject . . 3.4 Laplace Approximations 3.5 Problems 3.6 Notes 3.6.1 Large Deviations Techniques 3.6.2 The Saddlepoint Approximation 4 Controling Monte Carlo V^ariance 4.1 Monitoring Variation with the CLT 4.1.1 Univariate Monitoring 4.1.2 Multivariate Monitoring 4.2 Rao-Blackwellization 4.3 Riemann Approximations 4.4 Acceleration Methods 4.4.1 Antithetic Variables 4.4.2 Control Variates 4.5 Problems 4.6 Notes 4.6.1 Monitoring Importance Sampling Convergence 4.6.2 Accept-Reject with Loose Bounds 4.6.3 Partitioning 5 Monte Carlos Optimization 5.1 Introduction 5.2 Stochastic Exploration 5.2.1 A Basic Solution 5.2.2 Gradient Methods 5.2.3 Simulated Annealing 5.2.4 Prior Feedback 5.3 Stochastic Approximation 5.3.1 Missing Data Models and Demarginalization 5.3.2 The EM Algorithm 5.3.3 Monte Carlo EM 5.3.4 EM Standard Errors 5.4 Problems 5.5 Notes 5.5.1 Variations on EM 5.5.2 Neural Networks 5.5.3 The Robbins-Monro procedure 5.5.4 Monte Carlo Approximation 6 Markov Chains 6.1 Essentials for MCMC 6.2 Basic Notions 6.3 Irreducibility, Atoms, and Small Sets 6.3.1 Irreducibility 6.3.2 Atoms and Small Sets 6.3.3 Cycles and Aperiodicity 6.4 Transience and Recurrence 6.4.1 Classification of Irreducible Chains 6.4.2 Criteria for Recurrence 6.4.3 Harris Recurrence 6.5 Invariant Measures 6.5.1 Stationary Chains 6.5.2 Kacs Theorem 6.5.3 Reversibility and the Detailed Balance Condition 6.6 Ergodicity and Convergence 6.6.1 Ergodicity 6.6.2 Geometric Convergence 6.6.3 Uniform Ergodicity 6.7 Limit Theorems 6.7.1 Ergodic Theorems 6.7.2 Central Limit Theorems 6.8 Problems 6.9 Notes 6.9.1 Drift Conditions 6.9.2 Eatons Admissibility Condition 6.9.3 Alternative Convergence Conditions 6.9.4 Mixing Conditions and Central Limit Theorems 6.9.5 Covariance in Markov Chains 7 The Metropolis-Hastings Algorithm 7.1 The MCMC Principle 7.2 Monte Carlo Methods Based on Markov Chains 7.3 The Metropolis-Hastings algorithm 7.3.1 Definition 7.3.2 Convergence Properties 7.4 The Independent Metropolis-Hastings Algorithm 7.4.1 Fixed Proposals 7.4.2 A Metropolis-Hastings Version of ARS 7.5 Random Walks 7.6 Optimization and Control 7.6.1 Optimizing the Acceptance Rate 7.6.2 Conditioning and Accelerations 7.6.3 Adaptive Schemes 7.7 Problems 7.8 Notes 7.8.1 Background of the Metropolis Algorithm 7.8.2 Geometric Convergence of Metropolis-Hastings Algorithms 7.8.3 A Reinterpretation of Simulated Annealing 7.8.4 Reference Acceptance Rates 7.8.5 Langevin Algorithms 8 The Slice Sampler 8.1 Another Look at the Fundamental Theorem 8.2 The General Slice Sampler 8.3 Convergence Properties of the Slice Sampler 8.4 Problems 8.5 Notes 8.5.1 Dealing with Difficult Slices 9 The Two-Stage Gibbs Sampler 9.1 A General Class of Two-Stage Algorithms 9.1.1 Prom Slice Sampling to Gibbs Sampling 9.1.2 Definition 9.1.3 Back to the Slice Sampler 9.1.4 The Hammersley-Clifford Theorem 9.2 Fundamental Properties 9.2.1 Probabilistic Structures 9.2.2 Reversible and Interleaving Chains 9.2.3 The Duality Principle 9.3 Monotone Covariance and Rao-Blackwellization 9.4 The EM-Gibbs Connection 9.5 Transition 9.6 Problems 9.7 Notes 9.7.1 Inference for Mixtures 9.7.2 ARCH Models 10 The Multi-Stage Gibbs Sampler 10.1 Basic Derivations 10.1.1 Definition 10.1.2 Completion 10.1.3 The General Hammersley-Clifford Theorem 10.2 Theoretical Justifications 10.2.1 Markov Properties of the Gibbs Sampler 10.2.2 Gibbs Sampling as Metropolis-Hastings 10.2.3 Hierarchical Structures 10.3 Hybrid Gibbs Samplers 10.3.1 Comparison with Metropolis-Hastings Algorithms 10.3.2 Mixtures and Cycles 10.3.3 Metropolizing the Gibbs Sampler 10.4 Statistical Considerations 10.4.1 Reparameterization 10.4.2 Rao-Blackwellization 10.4.3 Improper Priors 10.5 Problems 10.6 Notes 10.6.1 A Bit of Background 10.6.2 The BUGS Software 10.6.3 Nonparametric Mixtures 10.6.4 Graphical Models 11 Variable Dimension Models and Reversible Jump Algorithms 11.1 Variable Dimension Models 11.1.1 Bayesian Model Choice 11.1.2 Difficulties in Model Choice 11.2 Reversible Jump Algorithms 11.2.1 Greens Algorithm 11.2.2 A Fixed Dimension Reassessment 11.2.3 The Practice of Reversible Jump MCMC 11.3 Alternatives to Reversible Jump MCMC 11.3.1 Saturation 11.3.2 Continuous-Time Jump Processes 11.4 Problems 11.5 Notes 11.5.1 Occams Razor 12 Diagnosing Convergence 12.1 Stopping the Chain 12.1.1 Convergence Criteria 12.1.2 Multiple Chains 12.1.3 Monitoring Reconsidered 12.2 Monitoring Convergence to the Stationary Distribution 12.2.1 A First Illustration 12.2.2 Nonparametric Tests of Stationarity 12.2.3 Renewal Methods 12.2.4 Missing Mass 12.2.5 Distance Evaluations 12.3 Monitoring Convergence of Averages 12.3.1 A First Illustration 12.3.2 Multiple Estimates 12.3.3 Renewal Theory 12.3.4 Within and Between Variances 12.3.5 Effective Sample Size 12.4 Simultaneous Monitoring 12.4.1 Binary Control 12.4.2 Valid Discretization 12.5 Problems 12.6 Notes 12.6.1 Spectral Analysis 12.6.2 The CODA Software 13 Perfect Sampling 13.1 Introduction 13.2 Coupling from the Past 13.2.1 Random Mappings and Coupling 13.2.2 Propp and Wilsons Algorithm 13.2.3 Monotonicity and Envelopes 13.2.4 Continuous States Spaces 13.2.5 Perfect Slice Sampling 13.2.6 Perfect Sampling via Automatic Coupling 13.3 Forward Coupling 13.4 Perfect Sampling in Practice 13.5 Problems 13.6 Notes 13.6.1 History 13.6.2 Perfect Sampling and Tempering 14 Iterated and Sequential Importance Sampling 14.1 Introduction 14.2 Generalized Importance Sampling 14.3 Particle Systems 14.3.1 Sequential Monte Carlo 14.3.2 Hidden Markov Models 14.3.3 Weight Degeneracy 14.3.4 Particle Filters 14.3.5 Sampling Strategies 14.3.6 Fighting the Degeneracy 14.3.7 Convergence of Particle Systems 14.4 Population Monte Carlo 14.4.1 Sample Simulation 14.4.2 General Iterative Importance Sampling 14.4.3 Population Monte Carlo 14.4.4 An Illustration for the Mixture Model 14.4.5 Adaptativity in Sequential Algorithms 14.5 Problems 14.6 Notes 14.6.1 A Brief History of Particle Systems 14.6.2 Dynamic Importance Sampling 14.6.3 Hidden Markov Models A Probability Distributions B Notation B.1 Mathematical B.2 Probability B.3 Distributions B.4 Markov Chains B.5 Statistics B.6 Algorithms References Index of Names Index of Subjects