August17,2005 MasterReviewVol.9inx6in–(forLectureNoteSeries,IMS,NUS) ims7-contents CONTENTS Foreword vii Preface ix Glossary xiii Introduction to Markov Chain Monte Carlo Simulations and Their Statistical Analysis B. A. Berg 1 An Introduction to Monte Carlo Methods in Statistical Physics D. P. Landau 53 Notes on Perfect Simulation W. S. Kendall 93 Sequential Monte Carlo Methods and Their Applications R. Chen 147 MCMC in the Analysis of Genetic Data on Pedigrees E. A. Thompson 183 Index 217 v.
June28,2005 MasterReviewVol.9inx6in–(forLectureNoteSeries,IMS,NUS) ims7-foreword FOREWORD The Institute for Mathematical Sciences at the National University of Sin- gapore was established on 1 July 2000 with funding from the Ministry of Education and the University. Its mission is to provide an international center of excellence in mathematical research and, in particular, to pro- mote within Singapore and the region active research in the mathematical sciences and their applications. It seeks to serve as a focal point for scien- tistsofdiversebackgroundstointeractandcollaborateinresearchthrough tutorials, workshops,seminars and informal discussions.
June28,2005 MasterReviewVol.9inx6in–(forLectureNoteSeries,IMS,NUS) ims7-preface PREFACE ThetechniqueofMarkovchainMonteCarlo(MCMC)ﬁrstaroseinstatisti- calphysics,markedbythecelebrated1953paperofMetropolis,Rosenbluth, Rosenbluth, Teller and Teller. The underlying principle is simple: if one wishes to sample randomly from a speciﬁc probability distribution then design a Markov chain whose long-time equilibrium is that distribution, write a computer programto simulate the Markov chain, and run the pro- grammed chain for a time long enough to be conﬁdent that approximate equilibrium has been attained; ﬁnally recordthe state of the Markovchain asanapproximatedrawfromequilibrium.TheMetropoliset al.paperused a symmetric Markov chain; later developments included adaptation to the case of non-symmetric Markov chains.
August16,2005 MasterReviewVol.9inx6in–(forLectureNoteSeries,IMS,NUS) ims7-glossary GLOSSARY Contributors to this volume come from several diﬀerent ﬁelds, each with theirownpreferredterminology,whichcanoftenoverlap.Toaidthereader, we have therefore assembled the following glossary of terms and brief deﬁ- nitions, which we have organizedunder the titles of Probability,Statistical Physics, and Mathematical Genetics.
August16,2005 MasterReviewVol.9inx6in–(forLectureNoteSeries,IMS,NUS) ims7-glossary GLOSSARY Contributors to this volume come from several diﬀerent ﬁelds, each with theirownpreferredterminology,whichcanoftenoverlap.Toaidthereader, we have therefore assembled the following glossary of terms and brief deﬁ- nitions, which we have organizedunder the titles of Probability,Statistical Physics, and Mathematical Genetics.
August16,2005 MasterReviewVol.9inx6in–(forLectureNoteSeries,IMS,NUS) ims7-glossary Glossary xvii 3. Mathematical Genetics • allele: One of two or more alternative forms of a gene, only one of which can be present in a chromosome.
September 13,2005 MasterReviewVol.9inx6in–(forLectureNoteSeries,IMS,NUS) berg INTRODUCTION TO MARKOV CHAIN MONTE CARLO SIMULATIONS AND THEIR STATISTICAL ANALYSIS Bernd A. Berg Department of Physics Florida State University Tallahassee, Florida 32306-4350, USA and School of Computational Science Florida State University Tallahassee, Florida 32306-4120, USA E-mail: [email protected] This article is a tutorial on Markov chain Monte Carlo simulations and theirstatisticalanalysis.Thetheoreticalconceptsareillustratedthrough many numerical assignments from the author’s book [7] on the subject.
September 13,2005 MasterReviewVol.9inx6in–(forLectureNoteSeries,IMS,NUS) berg INTRODUCTION TO MARKOV CHAIN MONTE CARLO SIMULATIONS AND THEIR STATISTICAL ANALYSIS Bernd A. Berg Department of Physics Florida State University Tallahassee, Florida 32306-4350, USA and School of Computational Science Florida State University Tallahassee, Florida 32306-4120, USA E-mail: [email protected] This article is a tutorial on Markov chain Monte Carlo simulations and theirstatisticalanalysis.Thetheoreticalconceptsareillustratedthrough many numerical assignments from the author’s book [7] on the subject.
September 13,2005 MasterReviewVol.9inx6in–(forLectureNoteSeries,IMS,NUS) berg 2 B. A. Berg 9.3 ExampleRuns 26 10Statistical Errors of Markov Chain Monte Carlo Data 30 10.1Autocorrelations 31 10.2Integrated Autocorrelation Time and Binning 33 10.3Illustration: Metropolis Generation of Normally Distributed Data 34 11Self-Consistent versusReasonable Error Analysis 37 12Comparison of Markov Chain MC Algorithms 38 13Multicanonical Simulations 40 13.1Howto Get theWeights? 43 14Multicanonical ExampleRuns(2d Ising and Potts Models) 44 14.1Energy and Speciﬁc Heat Calculation 46 14.2FreeEnergy and Entropy Calculation 48 14.3Time Series Analysis 49 References 51 1. Introduction Markov chain Monte Carlo (MC) simulations started in earnest with the 1953 article by Nicholas Metropolis, Arianna Rosenbluth, Marshall Rosen- bluth, Augusta Teller and Edward Teller [18]. Since then MC simulations have become an indispensable tool with applications in many branches of science. Some of those are reviewed in the proceedings [13] of the 2003 Los Alamos conference, which celebrated the 50th birthday of Metropolis simulations.