Simulation Reductions for the Ising Model

Abstract

Polynomial time reductions between problems have long been used to delineate problem classes, where an oracle for solving one problem yields a solution to another. Simulation reductions also exist, where an oracle for simulation from a probability distribution is employed in order to obtain draws from another distribution. Here linear time simulation reductions are given for: The Ising spins world to the Ising subgraphs world and the Ising subgraphs world to the Ising spins world. This answers a long standing question of whether such a direct relationship between these two versions of the Ising model existed. Moreover, these reductions result in the first method for perfect simulation from the subgraphs world and a new Swendsen-Wang style Markov chain for the Ising model. The method used is to write the desired distribution with set parameters as a mixture of distributions where the parameters are at their extreme values.

Key Words:

• Monte Carlo
• Simulation reduction
• Ising model
• High temperature expansion