  In this paper, we study the asymptotic variance of sample path averages for
inhomogeneous Markov chains that evolve alternatingly according to two
different $\pi$-reversible Markov transition kernels $P$ and $Q$. More
specifically, our main result allows us to compare directly the asymptotic
variances of two inhomogeneous Markov chains associated with different kernels
$P_i$ and $Q_i$, $i\in\{0,1\}$, as soon as the kernels of each pair $(P_0,P_1)$
and $(Q_0,Q_1)$ can be ordered in the sense of lag-one autocovariance. As an
important application, we use this result for comparing different
data-augmentation-type Metropolis-Hastings algorithms. In particular, we
compare some pseudo-marginal algorithms and propose a novel exact algorithm,
referred to as the random refreshment algorithm, which is more efficient, in
terms of asymptotic variance, than the Grouped Independence Metropolis-Hastings
algorithm and has a computational complexity that does not exceed that of the
Monte Carlo Within Metropolis algorithm.

Methodology;Computation