  Polynomial time reductions between problems have long been used to delineate
problem classes. Simulation reductions also exist, where an oracle for
simulation from some probability distribution can be employed together with an
oracle for Bernoulli draws in order to obtain a draw from a different
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.
