Statistical Mechanics Algorithms and Computations

OXFORD MASTER SERIES IN STATISTICAL,

COMPUTATIONAL, AND THEORETICAL PHYSICS

OXFORD MASTER SERIES IN PHYSICS

The Oxford Master Series is designed for final year undergraduate and

beginning graduate students in physics and related disciplines. It has

been driven by a perceived gap in the literature today. While basic

undergraduate physics texts often show little or no connection with the

huge explosion of research over the last two decades, more advanced

and specialized texts tend to be rather daunting for students. In this

series, all topics and their consequences are treated at a simple level,

while pointers to recent developments are provided at various stages.

The emphasis in on clear physical principles like symmetry, quantum

mechanics, and electromagnetism which underlie the whole of physics.

At the same time, the subjects are related to real measurements and to

the experimental techniques and devices currently used by physicists in

academe and industry. Books in this series are written as course books,

and include ample tutorial material, examples, illustrations, revision

points, and problem sets. They can likewise be used as preparation for

students starting a doctorate in physics and related fields, or for recent

graduates starting research in one of these fields in industry.

CONDENSED MATTER PHYSICS

1. M.T. Dove: Structure and dynamics: an atomic view of materials

2. J. Singleton: Band theory and electronic properties of solids

3. A.M. Fox: Optical properties of solids

4. S.J. Blundell: Magnetism in condensed matter

5. J.F. Annett: Superconductivity, superfluids, and condensates

6. R.A.L. Jones: Soft condensed matter

ATOMIC, OPTICAL, AND LASER PHYSICS

7. C.J. Foot: Atomic physics

8. G.A. Brooker: Modern classical optics

9. S.M. Hooker, C.E. Webb: Laser physics

15. A.M. Fox: Quantum optics: an introduction

PARTICLE PHYSICS, ASTROPHYSICS, AND COSMOLOGY

10. D.H. Perkins: Particle astrophysics

11. Ta-Pei Cheng: Relativity, gravitation and cosmology

STATISTICAL, COMPUTATIONAL, AND THEORETICAL

PHYSICS

12. M. Maggiore: A modern introduction to quantum field theory

13. W. Krauth: Statistical mechanics: algorithms and computations

14. J.P. Sethna: Statistical mechanics: entropy, order parameters, and

complexity

Statistical Mechanics

Algorithms and Computations

Werner Krauth

Laboratoire de Physique Statistique, Ecole Normale

Sup´erieure, Paris

1

3

Great Clarendon Street, Oxford OX2 6DP

Oxford University Press is a department of the University of Oxford.

It furthers the University’s objective of excellence in research, scholarship,

and education by publishing worldwide in

Oxford New York

Auckland Cape Town Dar es Salaam Hong Kong Karachi

Kuala Lumpur Madrid Melbourne Mexico City Nairobi

New Delhi Shanghai Taipei Toronto

With offices in

Argentina Austria Brazil Chile Czech Republic France Greece

Guatemala Hungary Italy Japan Poland Portugal Singapore

South Korea Switzerland Thailand Turkey Ukraine Vietnam

Oxford is a registered trade mark of Oxford University Press

in the UK and in certain other countries

Published in the United States

by Oxford University Press Inc., New York

c Oxford University Press 2006

The moral rights of the author have been asserted

Database right Oxford University Press (maker)

First published 2006

All rights reserved. No part of this publication may be reproduced,

stored in a retrieval system, or transmitted, in any form or by any means,

without the prior permission in writing of Oxford University Press,

or as expressly permitted by law, or under terms agreed with the appropriate

reprographics rights organization. Enquiries concerning reproduction

outside the scope of the above should be sent to the Rights Department,

Oxford University Press, at the address above

You must not circulate this book in any other binding or cover

and you must impose the same condition on any acquirer

British Library Cataloguing in Publication Data

Data available

Library of Congress Cataloging in Publication Data

Data available

Printed in Great Britain

on acid-free paper by

CPI Antony Rowe, Chippenham, Wilts.

ISBN 0–19–851535–9 (Hbk) 978–0–19–851535–7

ISBN 0–19–851536–7 (Pbk) 978–0–19–851536–4

10 9 8 7 6 5 4 3 2 1

F¨ur Silvia, Alban und Felix

This page intentionally left blank

Preface

This book is meant for students and researchers ready to plunge into

statistical physics, or into computing, or both. It has grown out of my

research experience, and out of courses that I have had the good fortune

to give, over the years, to beginning graduate students at the Ecole Nor￾male Sup´erieure and the Universities of Paris VI and VII, and also to

summer school students in Drakensberg, South Africa, undergraduates

in Salem, Germany, theorists and experimentalists in Lausanne, Switzer￾land, young physicists in Shanghai, China, among others. Hundreds of

students from many different walks of life, with quite different back￾grounds, listened to lectures and tried to understand, made comments,

corrected me, and in short helped shape what has now been written

up, for their benefit, and for the benefit of new readers that I hope to

attract to this exciting, interdisciplinary field. Many of the students sat

down afterwards, by themselves or in groups, to implement short pro￾grams, or to solve other problems. With programming assignments, lack

of experience with computers was rarely a problem: there were always

more knowledgeable students around who would help others with the

first steps in computer programming. Mastering technical coding prob￾lems should also only be a secondary problem for readers of this book:

all programs here have been stripped to the bare minimum. None exceed

a few dozen lines of code.

We shall focus on the concepts of classical and quantum statistical

physics and of computing: the meaning of sampling, random variables,

ergodicity, equidistribution, pressure, temperature, quantum statistical

mechanics, the path integral, enumerations, cluster algorithms, and the

connections between algorithmic complexity and analytic solutions, to

name but a few. These concepts built the backbone of my courses, and

now form the tissue of the book. I hope that the simple language and

the concrete settings chosen throughout the chapters take away none of

the beauty, and only add to the clarity, of the difficult and profound

subject of statistical physics.

I also hope that readers will feel challenged to implement many of

the programs. Writing and debugging computer code, even for the naive

programs, remains a difficult task, especially in the beginning, but it is

certainly a successful strategy for learning, and for approaching the deep

understanding that we must reach before we can translate the lessons of

the past into our own research ideas.

This book is accompanied by a compact disc containing more than one

hundred pseudocode programs and close to 300 figures, line drawings,

viii Preface

and tables contained in the book. Readers are free to use this mate￾rial for lectures and presentations, but must ask for permission if they

want to include it in their own publications. For all questions, please

contact me at www.lps.ens.fr/
krauth. (This website will also keep a

list of misprints.) Readers of the book may want to get in contact with

each other, and some may feel challenged to translate the pseudocode

programs into one of the popular computer languages;Iwill be happy

to assist initiatives in this direction, and to announce them on the above

website.

Contents

1 Monte Carlo methods 1

1.1 Popular games in Monaco 3

1.1.1 Direct sampling 3

1.1.2 Markov-chain sampling 4

1.1.3 Historical origins 9

1.1.4 Detailed balance 15

1.1.5 The Metropolis algorithm 21

1.1.6 A priori probabilities, triangle algorithm 22

1.1.7 Perfect sampling with Markov chains 24

1.2 Basic sampling 27

1.2.1 Real random numbers 27

1.2.2 Random integers, permutations, and combinations 29

1.2.3 Finite distributions 33

1.2.4 Continuous distributions and sample transformation 35

1.2.5 Gaussians 37

1.2.6 Random points in/on a sphere 39

1.3 Statistical data analysis 44

1.3.1 Sum of random variables, convolution 44

1.3.2 Mean value and variance 48

1.3.3 The central limit theorem 52

1.3.4 Data analysis for independent variables 55

1.3.5 Error estimates for Markov chains 59

1.4 Computing 62

1.4.1 Ergodicity 62

1.4.2 Importance sampling 63

1.4.3 Monte Carlo quality control 68

1.4.4 Stable distributions 70

1.4.5 Minimum number of samples 76

Exercises 77

References 79

2 Hard disks and spheres 81

2.1 Newtonian deterministic mechanics 83

2.1.1 Pair collisions and wall collisions 83

2.1.2 Chaotic dynamics 86

2.1.3 Observables 87

2.1.4 Periodic boundary conditions 90

2.2 Boltzmann’s statistical mechanics 92

2.2.1 Direct disk sampling 95

x Contents

2.2.2 Partition function for hard disks 97

2.2.3 Markov-chain hard-sphere algorithm 100

2.2.4 Velocities: the Maxwell distribution 103

2.2.5 Hydrodynamics: long-time tails 105

2.3 Pressure and the Boltzmann distribution 108

2.3.1 Bath-and-plate system 109

2.3.2 Piston-and-plate system 111

2.3.3 Ideal gas at constant pressure 113

2.3.4 Constant-pressure simulation of hard spheres 115

2.4 Large hard-sphere systems 119

2.4.1 Grid/cell schemes 119

2.4.2 Liquid–solid transitions 120

2.5 Cluster algorithms 122

2.5.1 Avalanches and independent sets 123

2.5.2 Hard-sphere cluster algorithm 125

Exercises 128

References 130

3 Density matrices and path integrals 131

3.1 Density matrices 133

3.1.1 The quantum harmonic oscillator 133

3.1.2 Free density matrix 135

3.1.3 Density matrices forabox 137

3.1.4 Density matrix in a rotating box 139

3.2 Matrix squaring 143

3.2.1 High-temperature limit, convolution 143

3.2.2 Harmonic oscillator (exact solution) 145

3.2.3 Infinitesimal matrix products 148

3.3 The Feynman path integral 149

3.3.1 Naive path sampling 150

3.3.2 Direct path sampling and the L´evy construction 152

3.3.3 Periodic boundary conditions, paths in a box 155

3.4 Pair density matrices 159

3.4.1 Two quantum hard spheres 160

3.4.2 Perfect pair action 162

3.4.3 Many-particle density matrix 167

3.5 Geometry of paths 168

3.5.1 Paths in Fourier space 169

3.5.2 Path maxima, correlation functions 174

3.5.3 Classical random paths 177

Exercises 182

References 184

4 Bosons 185

4.1 Ideal bosons (energy levels) 187

4.1.1 Single-particle density of states 187

4.1.2 Trapped bosons (canonical ensemble) 190

4.1.3 Trapped bosons (grand canonical ensemble) 196

Contents xi

4.1.4 Large-N limit in the grand canonical ensemble 200

4.1.5 Differences between ensembles—fluctuations 205

4.1.6 Homogeneous Bose gas 206

4.2 The ideal Bose gas (density matrices) 209

4.2.1 Bosonic density matrix 209

4.2.2 Recursive counting of permutations 212

4.2.3 Canonical partition function of ideal bosons 213

4.2.4 Cycle-length distribution, condensate fraction 217

4.2.5 Direct-sampling algorithm for ideal bosons 219

4.2.6 Homogeneous Bose gas, winding numbers 221

4.2.7 Interacting bosons 224

Exercises 225

References 227

5 Order and disorder in spin systems 229

5.1 The Ising model—exact computations 231

5.1.1 Listing spin configurations 232

5.1.2 Thermodynamics, specific heat capacity, and mag￾netization 234

5.1.3 Listing loop configurations 236

5.1.4 Counting (not listing) loops in two dimensions 240

5.1.5 Density of states from thermodynamics 247

5.2 The Ising model—Monte Carlo algorithms 249

5.2.1 Local sampling methods 249

5.2.2 Heat bath and perfect sampling 252

5.2.3 Cluster algorithms 254

5.3 Generalized Ising models 259

5.3.1 The two-dimensional spin glass 259

5.3.2 Liquids as Ising-spin-glass models 262

Exercises 264

References 266

6 Entropic forces 267

6.1 Entropic continuum models and mixtures 269

6.1.1 Random clothes-pins 269

6.1.2 The Asakura–Oosawa depletion interaction 273

6.1.3 Binary mixtures 277

6.2 Entropic lattice model: dimers 281

6.2.1 Basic enumeration 281

6.2.2 Breadth-first and depth-first enumeration 284

6.2.3 Pfaffian dimer enumerations 288

6.2.4 Monte Carlo algorithms for the monomer–dimer

problem 296

6.2.5 Monomer–dimer partition function 299

Exercises 303

References 305

7 Dynamic Monte Carlo methods 307

xii Contents

7.1 Random sequential deposition 309

7.1.1 Faster-than-the-clock algorithms 310

7.2 Dynamic spin algorithms 313

7.2.1 Spin-flips and dice throws 314

7.2.2 Accelerated algorithms for discrete systems 317

7.2.3 Futility 319

7.3 Disks on the unit sphere 321

7.3.1 Simulated annealing 324

7.3.2 Asymptotic densities and paper-cutting 327

7.3.3 Polydisperse disks and the glass transition 330

7.3.4 Jamming and planar graphs 331

Exercises 333

References 335

Acknowledgements 337

Index 339

Monte Carlo methods 1

1.1 Popular games in Monaco 3

1.2 Basic sampling 27

1.3 Statistical data analysis 44

1.4 Computing 62

Exercises 77

References 79

Starting with this chapter, we embark onajourney into the fascinating

realms of statistical mechanics and computational physics. We set out to

study a host of classical and quantum problems, all of value as models

and with numerous applications and generalizations. Many computa￾tional methods will be visited, by choice or by necessity. Not all of these

methods are, however, properly speaking, computer algorithms. Never￾theless, they often help us tackle, and understand, properties of physical

systems. Sometimes we can even say that computational methods give

numerically exact solutions, because few questions remain unanswered.

Among all the computational techniques in this book, one stands out:

the Monte Carlo method. It stems from the same roots as statistical

physics itself, it is increasingly becoming part of the discipline it is meant

to study, and it is widely applied in the natural sciences, mathematics,

engineering, and even the social sciences. The Monte Carlo method is

the first essential stop on our journey.

In the most general terms, the Monte Carlo method is a statistical—

almost experimental—approach to computing integrals using random1

positions, called samples,1 whose distribution is carefully chosen. In this

chapter, we concentrate on how to obtain these samples, how to process

them in order to approximately evaluate the integral in question, and

how to get good results with as few samples as possible. Starting with

very simple example, we shall introduce to the basic sampling techniques

for continuous and discrete variables, and discuss the specific problems

of high-dimensional integrals. We shall also discuss the basic principles

of statistical data analysis: how to extract results from well-behaved

simulations. We shall also spend much time discussing the simulations

where something goes wrong.

The Monte Carlo method is extremely general, and the basic recipes

allow us—in principle—to solve any problem in statistical physics. In

practice, however, much effort has to be spent in designing algorithms

specifically geared to the problem at hand. The design principles are

introduced in the present chapter; they will come up time and again in

the real-world settings of later parts of this book.

1“Random” comes from the old French word randon (to run around); “sample” is

derived from the Latin exemplum (example).

Children randomly throwing pebbles into a square, as in Fig. 1.1, illus￾trate a very simple direct-sampling Monte Carlo algorithm that can be

adapted to a wide range of problems in science and engineering, most

of them quite difficult, some of them discussed in this book. The basic

principles of Monte Carlo computing are nowhere clearer than where it

all started: on the beach, computing ￾.

Fig. 1.1 Children computing the number ￾ on the Monte Carlo beac