Stochastic Numerical Methods: An Introduction for Students and Scientists

Stochastic Numerical Methods introduces at Master level the numerical methods that use probability or stochastic concepts to analyze random processes. The book aims at being rather general and is addressed at students of natural sciences (Physics, Chemistry, Mathematics, Biology, etc.) and Engineering, but also social sciences (Economy, Sociology, etc.) where some of the techniques have been used recently to numerically simulate different agent–based models. Examples included in the book range from phase–transitions and critical phenomena, including details of data analysis (extraction of critical exponents, finite–size effects, etc.), to population dynamics, interfacial growth, chemical reactions, etc. Program listings are integrated in the discussion of numerical algorithms to facilitate their understanding. From the contents: • Review of Probability Concepts • Monte Carlo Integration • Generation of Uniform and Non–uniform Random Numbers: Non–correlated Values • Dynamical Methods • Applications to Statistical Mechanics • Introduction to Stochastic Processes • Numerical Simulation of Ordinary and Partial Stochastic Diff erential Equations •Introduction to Master Equations • Numerical Simulations of Master Equations • Hybrid Monte Carlo • Generation of n–Dimensional Correlated Gaussian Variables • Collective Algorithms for Spin Systems • Histogram Extrapolation • Multicanonical Simulations

Preface XIII 1 Review of probability concepts 1 1.1 Random Variables 1 1.2 Average Values, Moments 6 1.3 Some Important Probability Distributions with a Given Name 6 1.3.1 Bernoulli Distribution 6 1.3.2 Binomial Distribution 7 1.3.3 Geometric Distribution 8 1.3.4 Uniform Distribution 8 1.3.5 Poisson Distribution 10 1.3.6 Exponential Distribution 11 1.3.7 Gaussian Distribution 12 1.3.8 Gamma Distribution 13 1.3.9 Chi and Chi–Square Distributions 14 1.4 Successions of Random Variables 16 1.5 Jointly Gaussian Random Variables 18 1.6 Interpretation of the Variance: Statistical Errors 20 1.7 Sums of Random Variables 22 1.8 Conditional Probabilities 23 1.9 Markov Chains 26 Further Reading and References 28 Exercises 29 2 Monte Carlo Integration 31 2.1 Hit and Miss 31 2.2 Uniform Sampling 34 2.3 General Sampling Methods 36 2.4 Generation of Nonuniform Random Numbers: Basic Concepts 37 2.5 Importance Sampling 50 2.6 Advantages of Monte Carlo Integration 56 2.7 Monte Carlo Importance Sampling for Sums 57 2.8 Efficiency of an Integration Method 60 2.9 Final Remarks 61 Further Reading and References 62 Exercises 62 3 Generation of Nonuniform Random Numbers: Noncorrelated Values 65 3.1 General Method 65 3.2 Change of Variables 67 3.3 Combination of Variables 72 3.3.1 A Rejection Method 74 3.4 Multidimensional Distributions 76 3.5 Gaussian Distribution 81 3.6 Rejection Methods 84 Further Reading and References 94 Exercises 94 4 Dynamical Methods 97 4.1 Rejection with Repetition: a Simple Case 97 4.2 Statistical Errors 100 4.3 Dynamical Methods 103 4.4 Metropolis et al. Algorithm 107 4.4.1 Gaussian Distribution 108 4.4.2 Poisson Distribution 110 4.5 Multidimensional Distributions 112 4.6 Heat–Bath Method 116 4.7 Tuning the Algorithms 117 4.7.1 Parameter Tuning 117 4.7.2 How Often? 118 4.7.3 Thermalization 119 Further Reading and References 121 Exercises 121 5 Applications to Statistical Mechanics 125 5.1 Introduction 125 5.2 Average Acceptance Probability 129 5.3 Interacting Particles 130 5.4 Ising Model 134 5.4.1 Metropolis Algorithm 137 5.4.2 Kawasaki Interpretation of the Ising Model 143 5.4.3 Heat–Bath Algorithm 146 5.5 Heisenberg Model 148 5.6 Lattice Φ4 Model 149 5.6.1 Monte Carlo Methods 152 5.7 Data Analysis: Problems around the Critical Region 155 5.7.1 Finite–Size Effects 157 5.7.2 Increase of Fluctuations 160 5.7.3 Critical Slowing Down 161 5.7.4 Thermalization 163 Further Reading and References 163 Exercises 163 6 Introduction to Stochastic Processes 167 6.1 Brownian Motion 167 6.2 Stochastic Processes 170 6.3 Stochastic Differential Equations 172 6.4 White Noise 174 6.5 Stochastic Integrals. Itˆo and Stratonovich Interpretations 177 6.6 The Ornstein–Uhlenbeck Process 180 6.6.1 Colored Noise 181 6.7 The Fokker–Planck Equation 181 6.7.1 Stationary Solution 185 Further Reading and References 186 Exercises 187 7 Numerical Simulation of Stochastic Differential Equations 191 7.1 Numerical Integration of Stochastic Differential Equations with Gaussian White Noise 192 7.1.1 Integration Error 197 7.2 The Ornstein–Uhlenbeck Process: Exact Generation of Trajectories 201 7.3 Numerical Integration of Stochastic Differential Equations with Ornstein–Uhlenbeck Noise 202 7.3.1 Exact Generation of the Process gh(t) 205 7.4 Runge–Kutta–Type Methods 208 7.5 Numerical Integration of Stochastic Differential Equations with Several Variables 212 7.6 Rare Events: The Linear Equation with Linear Multiplicative Noise 217 7.7 First Passage Time Problems 221 7.8 Higher Order (?) Methods 225 7.8.1 Heun Method 226 7.8.2 Midpoint Runge–Kutta 228 7.8.3 Predictor–Corrector 228 7.8.4 Higher Order? 230 Further Reading and References 230 Exercises 231 8 Introduction to Master Equations 235 8.1 A Two–State System with Constant Rates 235 8.1.1 The Particle Point of View 236 8.1.2 The Occupation Numbers Point of View 239 8.2 The General Case 242 8.3 Examples 244 8.3.1 Radioactive Decay 244 8.3.2 Birth (from a Reservoir) and Death Process 245 8.3.3 A Chemical Reaction 246 8.3.4 Self–Annihilation 248 8.3.5 The Prey–Predator Lotka–Volterra Model 249 8.4 The Generating Function Method for Solving Master Equations 251 8.5 The Mean–Field Theory 254 8.6 The Fokker–Planck Equation 256 Further Reading and References 257 Exercises 257 9 Numerical Simulations of Master Equations 261 9.1 The First Reaction Method 261 9.2 The Residence Time Algorithm 268 Further Reading and References 273 Exercises 273 10 Hybrid Monte Carlo 275 10.1 Molecular Dynamics 275 10.2 Hybrid Steps 279 10.3 Tuning of Parameters 281 10.4 Relation to Langevin Dynamics 283 10.5 Generalized Hybrid Monte Carlo 284 Further Reading and References 285 Exercises 286 11 Stochastic Partial Differential Equations 287 11.1 Stochastic Partial Differential Equations 288 11.1.1 Kardar–Parisi–Zhang Equation 288 11.2 Coarse Graining 289 11.3 Finite Difference Methods for Stochastic Differential Equations 291 11.4 Time Discretization: von Neumann Stability Analysis 293 11.5 Pseudospectral Algorithms for Deterministic Partial Differential Equations 300 11.5.1 Evaluation of the Nonlinear Term 303 11.5.2 Storage of the Fourier Modes 304 11.5.3 Exact Integration of the Linear Terms 305 11.5.4 Change of Variables 306 11.5.5 Heun Method 306 11.5.6 Midpoint Runge–Kutta Method 307 11.5.7 Predictor–Corrector 308 11.5.8 Fourth–Order Runge–Kutta 310 11.6 Pseudospectral Algorithms for Stochastic Differential Equations 311 11.6.1 Heun Method 314 11.6.2 Predictor–Corrector 315 11.7 Errors in the Pseudospectral Methods 316 Further Reading and References 321 Exercises 321 A Generation of Uniform ̂ (0, 1) Random Numbers 327 A.1 Pseudorandom Numbers 327 A.2 Congruential Generators 329 A.3 A Theorem by Marsaglia 332 A.4 Feedback Shift Register Generators 333 A.5 RCARRY and Lagged Fibonacci Generators 334 A.6 Final Advice 335 Exercises 335 B Generation of n–Dimensional Correlated Gaussian Variables 337 B.1 The Gaussian Free Model 338 B.2 Translational Invariance 340 Exercises 344 C Calculation of the Correlation Function of a Series 347 Exercises 350 D Collective Algorithms for Spin Systems 351 E Histogram Extrapolation 357 F Multicanonical Simulations 361 G Discrete Fourier Transform 367 G.1 Relation Between the Fourier Series and the Discrete Fourier Transform 367 G.2 Evaluation of Spatial Derivatives 373 G.3 The Fast Fourier Transform 373 Further Reading 375 References 377 Index 383

Raul Toral is head of the department of Complex Systems at IFISC (Palma de Mallorca, Spain). He obtained his academic degrees from Barcelona university (Spain), spent two years at THE Physics Department of Edinburgh University (UK), and two more years at Lehigh University (Pennsylvania, USA), before joining the University of Balearic Islands where he has been a full professor since 1994. Prof. Toral has authored 200 scientific publications. He was the director of the Physbio International Summer School on Stochastic Processes in Biology held in St. Etienne de Tinnée (France) in 2006, and a member of the editorial board of Fluctuations and Noise Letters (2005–2007), as well as the organizer of several conferences devoted to basic issues and applications of Nonlinear and Statistical Physics. Pere Colet is Research Professor at IFISC (CSIC–UIB). He obtained his M.Sc. degree in physics from Universitat de Barcelona (1987) and his Ph. D. also in Physics from Universitat de les Illes Balears (1991), Spain. He was a postdoctoral Fulbright fellow at the School of Physics of the Georgia Institute of Tecnology. In May 1995, he joined the Spanish Consejo Superior de Investigaciones Cientificas. He has co–authored over 100 papers in ISI journals as well as 35 other scientific publications. His research interests include fluctuations and nonlinear dynamics of semiconductor lasers, synchronization of chaotic lasers and encoded communications, synchronization of coupled nonlinear oscillators, pattern formation, and quantum fluctuations in nonlinear optical cavities and dynamics of dissipative solitons.