The Monte-Carlo dynamics of a binary Lennard-Jones glass-forming mixture

Ludovic Berthier, Walter Kob

We use a standard Monte-Carlo algorithm to study the slow dynamics of a binary Lennard-Jones glass-forming mixture at low temperature. We find that Monte-Carlo is by far the most efficient way to simulate a stochastic dynamics since relaxation is about 10 times faster than in Brownian Dynamics and about 30 times faster than in Stochastic Dynamics. Moreover, the average dynamical behaviour of the system is in quantitative agreement with the one obtained using Newtonian dynamics, apart at very short times where thermal vibrations are suppressed. We show, however, that dynamic fluctuations quantified by four-point dynamic susceptibilities do retain a dependence on the microscopic dynamics, as recently predicted theoretically.

see more here

Monte Carlo, and Other Kinds of Stochastic Simulation

by Cosma

Monte Carlo is an estimation procedure. The basic idea is as follows. You want to know the average value of some random variable. You can’t work out what its distribution is, exactly, but you can take samples from that distribution. (The random variable may, for instance, be some complicated function of variables with simple distributions.) To estimate it, you simply take samples, independently, and average them. If you take enough samples, then the law of large numbers says your average must be close to the true value. The central limit theorem says that your average has a Gaussian distribution around the true value.

Here’s one of the canonical examples. Say you want to measure the area of a shape with a complicated, irregular outline. The Monte Carlo approach is to draw a square around the shape and measure the square. Now you throw darts into the square, as uniformly as possible. The fraction of darts falling on the shape gives the ratio of the area of the shape to the area of the square. Now, in fact, you can cast almost any integral problem, or any averaging problem, into this form. So you need a good way to tell if you’re inside the outline, and you need a good way to figure out how many darts you should throw. Last but not least, you need a good way to throw darts uniformly, i.e., a good random number generator. That’s a whole separate art I shan’t attempt to describe.

Now, in fact, you don’t strictly need to sample independently. You can have dependence, so long as you end up visiting each point just as many times as you would with independent samples. This is useful, since it gives a way to exploit properties of Markov chains in designing your sampling strategy, and even of speeding up the convergence of your estimates to the true averages.

Monte Carlo methods originated in physics, where the integrals desired involved hydrodynamics in complicated geometries with internal heating, i.e., designing nukes. The statisticans were surprisingly slow to pick up on it, though by now they have, especially as “Markov chain Monte Carlo,” abbreviated “MC Monte Carlo” (suggesting an gambling rapper) or just “MCMC”. Along the way they picked up the odd idea that Monte Carlo had something to do with Bayesianism. In fact it’s a general technique for estimating sample distributions and related quantities, and as such it’s entirely legitimate for frequentists. Physicists now sometimes use the term for any kind of stochastic estimation or simulation procedure, though I think it’s properly reserved for estimating integrals and averages.

See also: Markov Models; Statistical Mechanics; Statistics; Stochastic Approximation

Recommended:

1. Roland Assaraf and Michel Caffarel, “Zero-Variance Principle for Monte Carlo Algorithms,” Physical Review Letters 83 (1999): 4682–4685
2. P. Kevin MacKeown, Stochastic Simulation in Physics
3. Mark E. J. Newman and G. T. Barkema, Monte Carlo Methods in Statistical Physics
4. MCMC Preprint Service
5. On-line things to look at:
   • Sequential Monte Carlo a.k.a. particle filtering

To read:

1. Rosalind J. Allen, Patrick B. Warren and Pieter Rein ten Wolde, “Sampling Rare Switching Events in Biochemical Networks”, q-bio.MN/0406006 = Physical Review Letters 94 (2005): 018104
2. Christophe Andrieu, Éric Moulines, “On the ergodicity properties of some adaptive MCMC algorithms”, math.PR/0610317 = Annals of Applied Probability 16 (2006): 1462–1505
3. Andriy Bandrivskyy, S. Beri, D. G. Luchinsky, R. Mannella, and P. V. E. McClintock, “Fast Monte Carlo simulations and singularities in the probability distributions of non-equilibrium systems,” nlin.AO/0212038
4. Bernd A. Berg “Generalized Ensemble Simulations for Complex Systems,” cond-mat/0110521;“Introduction to Markov Chain Monte Carlo Simulations and their Statistical Analysis”, cond-mat/0410490
5. James A. Bucklew, “Conditional Importance Sampling Estimators”, IEEE Transactions on Information Theory 51 (2005): 143–153
6. James A. Bucklew, Sirin Nitinawarat and Jay Wierer, “Universal Simulation Distributions”, IEEE Transactions on Information Theory 50 (2004): 2674–2685
7. Fabien Campillo and Vivien Rossi, “Parallel and interacting Markov chains Monte Carlo method”, math.PR/0610181
8. A. C. Carter, Alan J. Bray and M. A. Moore, “On the Use of Finite-Size Scaling to Measure Spin-Glass Exponents,” cond-mat/0302207
9. Fergal P. Casey, Joshua J. Waterfall, Ryan N. Gutenkunst, Christopher R. Myers, James P. Sethna, “Variational method for estimating the rate of convergence of Markov Chain Monte Carlo algorithms”, physics/0609001
10. Yuguo Chen, “Another look at rejection sampling through importance sampling”, Statistics and Probability Letters 72 (2005): 277–283 ["We show that ejection sampling is inferior to the importance sampling algorithm in terms of the \chi^2 distance between the proposal distribution and the target distribution..."]
11. Andrew M. Childs, Ryan B. Patterson and David J. C. MacKay, “Exact Sampling from Non-Attractive Distributions Using Summary States,” cond-mat/0005132
12. C. I. Chou, Rongsheng Han, S. P. Li and T. K. Leem “Guided Simulated Annealing Method for Optimization Problems,” cond-mat/0302137
13. Francis Comets, Roberto Fernandez and Pablo A. Ferrari, “Processes with Long Memory: Regenerative Construction and Perfect Simulation,” math.PR/0009204
14. Radu V. Craiu and Xiao-Li Meng, “Multiprocess parallel antithetic coupling for backward and forward Markov Chain Monte Carlo”, math.ST/0505631 = Annals of Statistics 33 (2005): 661–697
15. Keith Crank and James Allen Fill, “Interruptible exact sampling in the passive case,” math.PR/0202136
16. Frederic Dambreville, “Cross-Entropy method: convergence issues for extended implementation”, math.OC/0609461
17. A. B. Deeker and M. Mandjes, “On asymptotically efficient simulation of large deviation probabilities”, Advances in Applied Probability 37 (2005): 539–552
18. R. Douc and France E. Moulines, “Limit theorems for weighted samples with applications to Sequential Monte Carlo Methods”, math.ST/0507042 [With application to state-space filtering]
19. Arnaud Doucet, Nando De Freitas and Neil Gordon (eds.), Sequential Monte Carlo Methods in Practice
20. Paul Dupuis and Hui Wang, “Dynamic importance sampling for uniformly recurrent markov chains”, Annals of Applied Probability 15 (2005): 1–38 = math.PR/0503454
21. Tilman Enss, Malte Henkel, Alan Picone and Ulrich Schollwöck, “Ageing phenomena without detailed balance: the contact process”, cond-mat/0406147 [Abstract: "The long-time dynamics of the 1D contact process suddenly brought out of an uncorrelated initial state is studied through a light-cone transfer-matrix renormalisation group approach. At criticality, the system undergoes ageing which is characterised through the dynamical scaling of the two-times autocorrelation and autoresponse functions. The observed non-equality of the ageing exponents a and b excludes the possibility of a finite fluctuation-dissipation ratio in the ageing regime. The scaling form of the critical autoresponse function is in agreement with the prediction of local scale-invariance." This approach is supposedly an alternative to some kinds of Monte Carlo]
22. Daniel Egloff, “Monte Carlo Algorithms for Optimal Stopping and Statistical Learning”, math.PR/0408276
23. Jean-David Fermanian and Bernard Salanié “A Nonparametric Simulated Maximum Likelihood Estimation Method”, Econometric Theory 20 (2004): 701–734
24. Pedro J. Fernandez, Pablo A. Ferrari and Sebastian Grynberg, “Perfectly random sampling of truncated multinormal distributions”, math.PR/0505522
25. James Allen Fill and Mark Huber, “The Randomness Recycler: A New Technique for Perfect Sampling,” math.PR/0009242
26. James M. Flegal, Murali Haran, Galin L. Jones, “Markov Chain Monte Carlo: Can We Trust the Third Significant Figure?”, math.ST/0703746
27. W. R. Gilks et al, Markov Chain Monte Carlo in Practice
28. Peter Grassberger, “Go with the Winners: a General Monte Carlo Strategy,” cond-mat/0201313 = Computer Physics Communications 147 (2002): 64–70
29. Alexander K. Hartmann, “Sampling rare events: statistics of local sequence alginments,” cond-mat/0108201
30. U. D. Jentschura, S. V. Aksenov, P. J. Mohr, M. A. Savageau, and G. Soff, “Convergence Acceleration Techniques,” math.NA/0202009
31. Mark Jerrum, “On the approximation of one Markov chain by another”, Probability Theory and Related Fields 135 (2006): 1–14 [with special reference to MCMC]
32. S. C. Kou, Qing Zhou and Wing Hung Wong, “Equi-Energy Sampler with Applications in Statistical Inference and Statistical Mechanics”, math.ST/0507080
33. David Landau and Kurt Binder, A Guide to Monte Carlo Simulations in Statistical Physics
34. Azi Lipshtat, “An ‘All Possible Steps’ Approach to the Accelerated Use of Gillespie’s Algorithm”, q-bio.QM/0703048
35. Neal Madras and Dana Randall, “Markov chain decomposition for convergence rate analysis”, Annals of Applied Probability 12 (2002): 581–606
36. S. Malefaki and G. Iliopoulos, “On convergence of importance sampling and other properly weighted samples to the target distribution”, math.ST/0505045
37. Paul Marjoram, John Molitor, Vincent Plagnol and Simon Tavaré, “Markov chain Monte Carlo without likelihoods”, PNAS 101 (2004): 15324–15328
38. J. D. Munoz, M. A. Novotny and S. J. Mitchell, “Reject-ion-free Monte Carlo algorithms for models with continuous degrees of freedom,” Physical Review E 67 (2003): 026101
39. K. P. N. Murthy, “Monte Carlo: Basics,” cond-mat/0104215
40. Radford M. Neal, “Slice Sampling,” physics/0009028; “The Short-Cut Metropolis Method”, math.ST/0508060
41. M. A. Novotny, “A Tutorial on Advanced Dynamic Monte Carlo Methods for Systems with Discrete State Spaces,” cond-mat/0109182
42. Christian Robert and George Casella, Monte Carlo Statistical Methods
43. Gareth O. Roberts and Jeffrey S. Rosenthal, “General state space Markov chains and MCMC algorithms”, math.PR/0404033
44. Sylvain Rubenthaler, Tobias Ryden and Magnus Wiktorsson, “Fast simulated annealing in $\R^d$ and an application to maximum likelihood estimation”, math.PR/0609353
45. R. Y. Rubinstein, “A Stochastic Minimum Cross-Entropy Method for Combinatorial Optimization and Rare-event Estimation”, Methodology and Computing in Applied Probability 7 (2005): 5–50
46. Tilman Sauer, “The Feynman Path Goes Monte Carlo,” physics/0107010
47. Gabriel Stoltz, “Path Sampling with Stochastic Dynamics: Some New Algorithms”, cond-mat/0607650
48. F. V. Tkachov, “Quasi-optimal observables: Attaining the quality of maximal likelihood in parameter estimation when only a MC event generator is available,” physics/0108030
49. Fugao Wang and David P. Landau, “Determining the density of states for classical statistical models: A random walk algorithm to produce a flat histogram,” cond-mat/0107006
50. Jian-Sheng Wang, “Efficient Monte Carlo Simulation Methods in Statistical Physics,” cond-mat/0103318
51. Jian-Sheng Wang and Robert H. Swendsen, “Transition Matrix Monte Carlo Method,” cond-mat/0104418
52. Stephen Whitelam and Phillip L. Geissler, “Cluster algorithm for pairwise-interacting particles”, cond-mat/0508100 [with special application to self-assembling particle systems]
53. David H. Wolpert and Chiu Fan Lee, “An adaptive Metropolis-Hastings scheme: sampling and optimization”, cond-mat/0504163