0
$\begingroup$

The statistical physics literature is replete with papers describing simulations of lattice models, such as the Ising model. Typically, these are done through Monte Carlo methods, such as the Metropolis algorithm. A major concern in these studies is whether the algorithm has reached equilibrium. If the dynamics are not run for a long enough time, they will not produce draws from the desired equilibrium distribution. Further, in many cases, the algorithm is never actually at equilibrium, but rather approximates it to a finer and finer resolution as the simulation proceeds. Hence, the distance to equilibrium is one key source of error in these simulation methods.

There is, however, a Monte Carlo method for sampling exactly from the equilibrium distribution. In general it is extremely computationally expensive, and therefore inferior to standard methods, but there are many cases where the specific structure of the problem can be leveraged to make it practical. The Ising model is one such case, and the algorithm proceeds as follows. Start one chain in the state with all spins up, and one chain in the state with all spins down. Couple the chains by choosing the same proposal spin for each step of the dynamics for each chain. Run the Metropolis dynamics until the chains coalesce at some time $T$. The value of the chain at the random time $T$ will be distributed exactly as the equilibrium distribution.

This is known as coupling from the past and is originally due to Propp and Wilson, in the paper
Exact Sampling with Coupled Markov Chains and Applications to Statistical Mechanics, published 1996. Further, it is known that the coalescence time is on average approximately the same as the mixing time for the chain (in the Ising case).

Naively, I would think perfect sampling in this way might be superior to traditional algorithms, such as Metropolis. At the cost of running two chains for the mixing time, I get a perfect i.i.d. sample from the target distribution. In comparison, I need to run the chain for the mixing time in the Metropolis algorithm to get what is merely an approximation to an i.i.d. sample (with each roughly independent sample requiring the mixing time again). Thus, for the cost of running twice as many chains, I am able to remove to the equilibration error completely. It's not obvious to me this is better, given a fixed budget of Metropolis runs (trading eliminating the error for halving the number of samples), but it seems like it might be. At the very least, I hoped to find some discussion of this method in the statistical physics simulation literature.

However, I did not. I looked in what I was told was the standard reference, A Guide to Monte Carlo Simulations by Binder and Landau, and could not find any mention of coupling from the past or other perfect sampling methods. Further, among the citations to the Propp and Wilson paper, I could not find any statistical physics papers.

I wonder then, why is the physics community not interested in perfect sampling? For most problems, there is not any monotonicity structure as in the Ising model, so it is clearly inferior to usual methods. But, there are also many cases where this kind of structure can be exploited. My guess is that the method is known to researchers but not used because it is inferior to the usual methods in some clear way, which I am not able to discern.

So, to conclude: is perfect sampling not used by physicists because there it is obviously worse than other Monte Carlo methods? If so, why is it worse?

(If the answer is model-dependent, let us restrict ourselves to the Ising and related – e.g. Edwards–Anderson – models, since those are the ones I am interested in at the moment.)

$\endgroup$
4
  • $\begingroup$ Just a methodic comment: in order to check for the influence of a given paper, go to Google Scholar and use the "cited by" links to work through all relevant works that cite your selected paper. In these you'll likely find at least hints on how to proceed. And if you find nothing... well, then that's your time. $\endgroup$ – davidhigh Dec 1 '20 at 21:06
  • $\begingroup$ The paper has 1500 citations. In the first 10 pages of "cited by" results I did not find papers from physicists, hence my question. $\endgroup$ – alligator Dec 1 '20 at 22:23
  • $\begingroup$ I don't want to bother you, but you can also search in the list of citations for further keywords, e.g. Ising. You'll find a few hits there, and within also some physical papers. I would skim through these. $\endgroup$ – davidhigh Dec 2 '20 at 15:10
  • $\begingroup$ @davidhigh Thank you. Searching for "Ising" I did find a few papers published in physics journals. One says: "Also, the long expected run times seem to make the application of these types of algorithms rather limited in studies of low-temperature behavior for systems with quenched randomness and high barriers." I guess other MCMC methods, which are not amenable to coupling from the past, are better at low temperature. (From "Introduction to the Propp-Wilson Method of Exact Sampling for the Ising Model," N.A. Novotny.) $\endgroup$ – alligator Dec 2 '20 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.