  We consider Metropolis Hastings MCMC in cases where the log of the ratio of
target distributions is replaced by an estimator. The estimator is based on m
samples from an independent online Monte Carlo simulation. Under some
conditions on the distribution of the estimator the process resembles
Metropolis Hastings MCMC with a randomized transition kernel. When this is the
case there is a correction to the estimated acceptance probability which
ensures that the target distribution remains the equilibrium distribution. The
simplest versions of the Penalty Method of Ceperley and Dewing (1999), the
Universal Algorithm of Ball et al. (2003) and the Single Variable Exchange
algorithm of Murray et al. (2006) are special cases. In many applications of
interest the correction terms cannot be computed. We consider approximate
versions of the algorithms. We show that on average O(m) of the samples
realized by a simulation approximating a randomized chain of length n are
exactly the same as those of a coupled (exact) randomized chain. Approximation
biases Monte Carlo estimates with terms O(1/m) or smaller. This should be
compared to the Monte Carlo error which is O(1/sqrt(n)).
