A Theoretical Comparison of the Data Augmentation, Marginal Augmentation and PX-DA Algorithms

The data augmentation (DA) algorithm is a widely used Markov chain Monte Carlo (MCMC) algorithm that is based on a Markov transition density of the form $p(x|x^{\prime})=\int_{{\ssf Y}}f_{X|Y}(x|y)f_{Y|X}(y|x^{\prime})dy$, where $f_{X/Y}$ and $f_{Y|X}$ are conditional densities. The PX-DA and marginal augmentation algorithms of Liu and Wu [J. Amer. Statist. Assoc. 94 (1999) 1264-1274] and Meng and van Dyk [Biometrika 86 (1999) 301-320] are alternatives to DA that often converge much faster and are only slightly more computationally demanding. The transition densities of these alternative algorithms can be written in the form $p_{R}(x|x^{\prime})=\int_{{\ssf Y}}\int_{{\ssf Y}}f_{X|Y}(x|y^{\prime})R(y,dy^{\prime})f_{Y|X}(y|x^{\prime})dy$, where R is a Markov transition function on Y. We prove that when R satisfies certain conditions, the MCMC algorithm driven by $p_{R}$ is at least as good as that driven by p in terms of performance in the central limit theorem and in the operator norm sense. These results are brought to bear on a theoretical comparison of the DA, PX-DA and marginal augmentation algorithms. Our focus is on situations where the group structure exploited by Liu and Wu is available. We show that the PX-DA algorithm based on Haar measure is at least as good as any PX-DA algorithm constructed using a proper prior on the group.