  Markov Chain Monte Carlo (MCMC) algorithms are routinely used to draw samples
from distributions with intractable normalization constants. However, standard
MCMC algorithms do not apply to doubly-intractable distributions in which there
are additional parameter-dependent normalization terms; for example, the
posterior over parameters of an undirected graphical model. An ingenious
auxiliary-variable scheme (Moeller et al., 2004) offers a solution: exact
sampling (Propp and Wilson, 1996) is used to sample from a Metropolis-Hastings
proposal for which the acceptance probability is tractable. Unfortunately the
acceptance probability of these expensive updates can be low. This paper
provides a generalization of Moeller et al. (2004) and a new MCMC algorithm,
which obtains better acceptance probabilities for the same amount of exact
sampling, and removes the need to estimate model parameters before sampling
begins.
