PROBABILISTIC INFERENCE USING MARKOV CHAIN MONTE CARLO METHODS Radford M. Neal Department of Computer Science University of Toronto 25 September 1993 TABLE OF CONTENTS 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Probabilistic Inference for Artificial Intelligence. . . . . . 4 2.1 Probabilistic inference with a fully-specified model . . . 5 2.2 Statistical inference for model parameters . . . . . . . . 13 2.3 Bayesian model comparison. . . . . . . . . . . . . . . . . 23 2.4 Statistical physics. . . . . . . . . . . . . . . . . . . . 25 3 Background on the Problem and its Solution . . . . . . . . . . 30 3.1 Definition of the problem. . . . . . . . . . . . . . . . . 30 3.2 Approaches to solving the problem. . . . . . . . . . . . . 32 3.3 Theory of Markov chains . . . . . . . . . . . . . . . . . 36 4 The Metropolis and Gibbs Sampling Algorithms . . . . . . . . . 47 4.1 Gibbs sampling . . . . . . . . . . . . . . . . . . . . . . 47 4.2 The Metropolis algorithm . . . . . . . . . . . . . . . . . 54 4.3 Variations on the Metropolis algorithm . . . . . . . . . . 59 4.4 Analysis of the Metropolis and Gibbs sampling algorithms . 64 5 The Dynamical and Hybrid Monte Carlo Methods . . . . . . . . . 70 5.1 The stochastic dynamics method . . . . . . . . . . . . . . 70 5.2 The hybrid Monte Carlo algorithm . . . . . . . . . . . . . 77 5.3 Other dynamical methods. . . . . . . . . . . . . . . . . . 81 5.4 Analysis of the hybrid Monte Carlo algorithm . . . . . . . 83 6 Extensions and Refinements . . . . . . . . . . . . . . . . . . 87 6.1 Simulated annealing. . . . . . . . . . . . . . . . . . . . 87 6.2 Free energy estimation . . . . . . . . . . . . . . . . . . 94 6.3 Error assessment and reduction . . . . . . . . . . . . . . 102 6.4 Parallel implementation. . . . . . . . . . . . . . . . . . 114 7 Directions for Research. . . . . . . . . . . . . . . . . . . . 116 7.1 Improvements in the algorithms . . . . . . . . . . . . . . 116 7.2 Scope for applications . . . . . . . . . . . . . . . . . . 118 8 Annotated Bibliography . . . . . . . . . . . . . . . . . . . . 121 Total length: 144 pages