Mixing time for the solid-on-solid model

ABSTRACT

We analyze the mixing time of a natural local Markov chain (the Glauber dynamics) on configurations of the solid-on-solid model of statistical physics. This model has been proposed, among other things, as an idealization of the behavior of contours in the Ising model at low temperatures. Our main result is an upper bound on the mixing time of O~(n^3.5), which is tight within a factor of O~(√n). The proof, which in addition gives insight into the actual evolution of the contours, requires the introduction of several novel analytical techniques that we conjecture will have other applications.

REFERENCES

• 1: N.Berger, C.Kenyon, E.Mossel and Y.Peres. Glauber dynamics on trees and hyperbolic graphs. Prob. Th. Rel. Fields 131 (2005), pp. 311--340.
• 2: F.Cesi. Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields. Prob. Th. Rel. Fields 120 (2001), pp. 569--584.
• 3: L.Chayes, R.Schonmann and G.Swindle. Lifshitz law for the volume of a 2-dimensional droplet at zero temperature. J. Stat. Phys. 79 (1995), pp. 821--831.
• 4: P.Diaconis and L.Saloff-Coste. Comparison theorems for reversible Markov chains. Annals of Applied Probability 3 (1993), pp. 696--730.
• 5: R.L.Dobrushin, R.Kotecky and S.Shlosman. The Wulff construction: a global shape from local interactions. AMS Translations Of Mathematical Monographs 104, Providence, 1992.
• 6: F.Dunlop, P.Ferrari and L.Fontes A dynamic one-dimensional interface interacting with a wall. J. Stat. Phys. 107 (2002), pp. 705--727.
• 7: T. Funaki. Stochastic interface models. Lectures on Probability Theory and Statistics, Springer Lecture Notes in Mathematics 1869, 2005, pp. 103--294.
• 8: G.Giacomin. Random polymer models. Imperial College Press, World Scientific, London, 2007.
• 9: D.Huse and D. Fisher. Dynamics of droplet fluctuations in pure and random Ising systems. Physics Review B 35 (13), 1987.
• 10: Michael Luby , Dana Randall , Alistair Sinclair, Markov Chain Algorithms for Planar Lattice Structures, SIAM Journal on Computing, v.31 n.1, p.167-192, 2001 [doi>10.1137/S0097539799360355]
• 11: F.Martinelli. Lectures on Glauber dynamics for discrete spin models. Lectures on Probability Theory and Statistics, Springer Lecture Notes in Mathematics 1717, 1998, pp. 93--191,
• 12: F.Martinelli and E.Olivieri. Approach to equilibrium of Glauber dynamics in the one phase region I: The attractive case. Comm. Math. Phys. 161 (1994), pp. 447--486.
• 13: F.Martinelli and A.Sinclair. Mixing time for the solid-on-solid model. Full version, arxiv.org, 2009.
• 14: Fabio Martinelli , Alistair Sinclair , Dror Weitz, The Ising Model on Trees: Boundary Conditions and Mixing Time, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.628, October 11-14, 2003
• 15: F.Martinelli and F.Toninelli. On the mixing time of the 2D Ising model with plus boundary conditions at low temperature. Manuscript, 2009.
• 16: Y. Peres. Mixing for Markov chains and spin systems. Lecture Notes for PIMS Summer School at UBC, August 2005. www.stat.berkeley.edu/ peres/ubc.pdf
• 17: G. Posta. Spectral gap for an unrestricted Kawasaki type dynamics. ESAIM: Probability &#; Statistics 1 (1995), pp. 145--181.
• 18: V.Privman and N.Svrakic. Difference equations in statistical mechanics II: Solid-on-solid models in two dimensions. J. Stat. Phys. 51 (1988), pp. 1111--1126.
• 19: V. Privman and Svrakic. Line interfaces in two dimensions: Solid-on-solid models. Lecture Notes in Physics 338, Springer, 1989, pp. 32--60.
• 20: James Gary Propp , David Bruce Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Structures & Algorithms, v.9 n.1-2, p.223-252, Aug./Sept. 1996
• 21: D.Randall and P.Tetali. Analyzing Glauber dynamics by comparison of Markov chains. Journal of Mathematical Physics 41 (2000), pp. 1598--1615.
• 22: F.Spitzer. Principles of Random Walks. Van Nostrand, Princeton, 1964.
• 23: D.W.Stroock and B.Zegarlinski. The logarithmic Sobolev inequality for discrete spin systems on a lattice. Comm. Math. Phys. 149 (1992), pp. 175--194.
• 24: D.B.Wilson. Mixing times of lozenge tiling and card shuffling Markov chains. Annals of Applied Probability 14 (2004), pp. 274--325.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

Additional Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Physics

General Terms:
Algorithms, Theory

Keywords:
glauber dynamics, ising model, markov chain monte carlo (mcmc), mixing time, statistical physics