An Analysis of Swendsen–Wang and Related Sampling Methods

Convergence rates, statistical efficiency and sampling costs are studied for the original and extended Swendsen–Wang methods of generating a sample path {Sj, j≥1} with equilibrium distribution π, with r distinct elements, on a finite state space X of size N1. Given Sj‐1, each method uses auxiliary random variables to identify the subset of X from which Sj is to be randomly sampled. Let πmin and πmax denote respectively the smallest and largest elements in π and let Nr denote the number of elements in π with value πmax. For a single auxiliary variable, uniform sampling from the subset and (N1−Nr)πmin+Nrπmax≈1, our results show rapid convergence and high statistical efficiency for large πmin/πmaxorNr/N1 and slow convergence and poor statistical efficiency for small πmin/πmaxandNr/N1. Other examples provide additional insight. For extended Swendsen–Wang methods with non‐uniform subset sampling, the analysis identifies the properties of a decomposition of π(x) that favour fast convergence and high statistical efficiency. In the absence of exploitable special structure, subset sampling can be costly regardless of which of these methods is employed.