Reducing the Ising model to matchings

Mark Huber, Jenny Law

Published 2009-07-02Version 1

Canonical paths is one of the most powerful tools available to show that a Markov chain is rapidly mixing, thereby enabling approximate sampling from complex high dimensional distributions. Two success stories for the canonical paths method are chains for drawing matchings in a graph, and a chain for a version of the Ising model called the subgraphs world. In this paper, it is shown that a subgraphs world draw can be obtained by taking a draw from matchings on a graph that is linear in the size of the original graph. This provides a partial answer to why canonical paths works so well for both problems, as well as providing a new source of algorithms for the Ising model. For instance, this new reduction immediately yields a fully polynomial time approximation scheme for the Ising model on a bounded degree graph when the magnitization is bounded away from 0.