  In sampling tasks, it is common for target distributions to be known up to a
normalising constant. However, in many situations, evaluating even the
unnormalised distribution can be costly or infeasible. This issue arises in
scenarios such as sampling from the Bayesian posterior for tall datasets and
the 'doubly-intractable' distributions. In this paper, we begin by observing
that seemingly different Markov chain Monte Carlo (MCMC) algorithms, such as
the exchange algorithm, PoissonMH, and TunaMH, can be unified under a simple
common procedure. We then extend this procedure into a novel framework that
allows the use of auxiliary variables in both the proposal and
acceptance-rejection steps. We develop the theory of the new framework,
applying it to existing algorithms to simplify and extend their results.
Several new algorithms emerge from this framework, with improved performance
demonstrated on both synthetic and real datasets.
