Comparing the Efficiency of General State Space Reversible MCMC Algorithms

Abstract We prove new results about comparing the efficiency of general state space Markov chain Monte Carlo algorithms that randomly select a possibly different reversible method at each step (previously known only for finite state spaces). We also provide new, simpler, more accessible proofs of key results, and analyse numerous examples. We provide a full proof of the formula for the asymptotic variance for real-valued functionals on $\varphi$ -irreducible reversible Markov chains, first introduced by Kipnis and Varadhan (1986, Commun. Math. Phys. 104 , 1–19). Given two Markov kernels P and Q with stationary measure $\pi$ , we say that the Markov kernel P efficiency-dominates the Markov kernel Q if the asymptotic variance with respect to P is at most the asymptotic variance with respect to Q for every real-valued functional $f\in L^2(\pi)$ . Assuming only a basic background in functional analysis, we prove that for two reversible Markov kernels P and Q , P efficiency-dominates Q if and only if the operator $\mathcal{Q}-\mathcal{P}$ , where $\mathcal{P}$ is the operator on $L^2(\pi)$ that maps $f\mapsto\int f(y)P(\cdot,\mathrm{d}y)$ and similarly for $\mathcal{Q}$ , is positive on $L^2(\pi)$ , i.e. $\langle f,\left(\mathcal{Q}-\mathcal{P}\right)f\rangle\geq0$ for every $f\in L^2(\pi)$ (previous proofs for general state spaces use technical results from monotone operator function theory). We use this result to show that under mild conditions, sandwich variants of data augmentation algorithms efficiency-dominate the original algorithm. We also provide other easy-to-check sufficient conditions for efficiency dominance, some of which are generalized from the finite state space case. We also provide a proof based on that of Tierney (1998, Ann. Appl. Prob. 8 , 1–9) that Peskun dominance is a sufficient condition for efficiency dominance for reversible kernels. Using these results, we show that Markov kernels formed by random selection of other ‘component’ Markov kernels will always efficiency-dominate another Markov kernel formed in this way, as long as the component kernels of the former efficiency-dominate those of the latter. These results on the efficiency dominance of combining component kernels generalizes the results on the efficiency dominance of combined chains introduced by Neal and Rosenthal (2024, J. Appl. Prob. 62 , 188–208) from finite state spaces to general state spaces.