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 { S _j , j ≥1} with equilibrium distribution π , with r distinct elements, on a finite state space X of size N ₁. Given S _{j -1}, each method uses auxiliary random variables to identify the subset of X from which S _j is to be randomly sampled. Let π_min and π_max denote respectively the smallest and largest elements in π and let N_r denote the number of elements in π with value π_max. For a single auxiliary variable, uniform sampling from the subset and ( N ₁− N_r )π_min+ N_r π_max≈1, our results show rapid convergence and high statistical efficiency for large π_min/π_max or N_r / N ₁ and slow convergence and poor statistical efficiency for small π_min/π_max and N_r / N₁ . 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.