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 vertical bar x') = integral y fx vertical bar y (x vertical bar y)fY vertical bar X (y vertical bar x') dy, where fX vertical bar Y and fY vertical bar 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 PR (x vertical bar x') = integral Y integral y fX vertical bar Y (x vertical bar y') R(y, dy')fY vertical bar X (y vertical bar x') dy, where R is a Markov transition function on Y. We prove that when R satisfies certain conditions, the MCMC algorithm driven by PR 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.