Simulation reduction of the Ising model to general matchings

Mark L Huber (Claremont McKenna College)
Jenny Law (Duke University)

Abstract


A distribution is tractable if it is possible to approximately sample from the distribution in polynomial time. Here the ferromagnetic Ising model with unidrectional magnetic field is shown to be reducible to a standard distribution on matchings that is tractable. This provides an alternate method to the original Jerrum and Sinclair approach to show that the Ising distribution itself is tractable. Previous reductions of the Ising model to perfect matchings on different graphs exist, but these older distributions are not tractable. Also, the older reductions did not consider an external magnetic field, while the new reduction explictly includes such a field. The new reduction also helps to explain why the idea of canonical paths is so useful inapproximately sampling from both problems. In addition, the reduction allows any algorithm for matchings to immediately be applied to the Ising model. For instance, this immediately yields a fully polynomial time approximation scheme for the Ising model on a bounded degree graph with magnetization bounded away from 0, merely by invoking an existing algorithm for matchings.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-15

Publication Date: April 29, 2012

DOI: 10.1214/EJP.v17-1998

References

  • Bayati, Mohsen; Gamarnik, David; Katz, Dimitriy; Nair, Chandra; Tetali, Prasad. Simple deterministic approximation algorithms for counting matchings. STOC'07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 122--127, ACM, New York, 2007. MR2402435
  • Caianiello, E. R. Combinatorics and renormalization in quantum field theory. Frontiers in Physics. W. A. Benjamin, Inc., Reading, Mass.-London-Amsterdam, 1973. xv+121 pp. MR0464973
  • M.E. Fisher. On the dimer solution of planar Ising models, J. of Math. Phys. 7 (1966), 1776--1781.
  • Fishman, George S., Monte Carlo. Concepts, algorithms, and applications. Springer Series in Operations Research. Springer-Verlag, New York, 1996. xxvi+698 pp. ISBN: 0-387-94527-X MR1392474
  • Huber, Mark. Simulation reductions for the Ising model, J. Stat. Theory Pract., to appear.
  • Jerrum, Mark and Sinclair, Alistair. Approximating the permanent. SIAM J. Comput. 18 (1989), no. 6, 1149--1178. MR1025467
  • Jerrum, Mark and Sinclair, Alistair. Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput. 22 (1993), no. 5, 1087--1116. MR1237164
  • M. Jerrum and A. Sinclair. The Markov chain Monte Carlo method: An approach to approximate counting and integration, pp. 482--520, PWS, 1996.
  • Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V. Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43 (1986), no. 2-3, 169--188. MR0855970
  • R. Karp, Approximate counting and sampling [lecture notes], Recorded by Alexandre Bouchard-Côté, http://www.cs.berkeley.edu/~karp/greatalgo/lecture16.pdf.
  • Law, Wai Jing. Approximately counting perfect and general matchings in bipartite and general graphs. Thesis (Ph.D.)–Duke University. ProQuest LLC, Ann Arbor, MI, 2009. 227 pp. ISBN: 978-1109-08252-4 MR2712989
  • Montroll, Elliott W. Lattice statistics, Applied combinatorial mathematics. University of California Engineering and Physical Sciences Extension Series John Wiley and Sons, Inc., New York-London-Sydney, 1964, MR0174486
  • Newell, Gordon F.; Montroll, Elliott W. On the theory of the Ising model of ferromagnetism. Rev. Modern Physics 25, (1953). 353--389. MR0056511
  • Papadimitriou, Christos H.; Steiglitz, Kenneth. Combinatorial optimization: algorithms and complexity. Dover Publications, Inc., Mineola, NY, 1998. xvi+496 pp. ISBN: 0-486-40258-4 MR1637890
  • Sinclair, Alistair. Algorithms for random generation and counting. A Markov chain approach. Progress in Theoretical Computer Science. Birkhäuser Boston, Inc., Boston, MA, 1993. vi+146 pp. ISBN: 0-8176-3658-7 MR1201590
  • B. L. van~der Waerden, Die lange Reichweite der regelmässigen Atomanordnung in Mischkristallen, Z. Physik 118 (1941), 473--488.
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.