Premium
An Analysis of Swendsen–Wang and Related Sampling Methods
Author(s) -
Fishman George S.
Publication year - 1999
Publication title -
journal of the royal statistical society: series b (statistical methodology)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 6.523
H-Index - 137
eISSN - 1467-9868
pISSN - 1369-7412
DOI - 10.1111/1467-9868.00197
Subject(s) - convergence (economics) , mathematics , sampling (signal processing) , sample size determination , statistics , rate of convergence , distribution (mathematics) , mathematical optimization , combinatorics , algorithm , computer science , mathematical analysis , key (lock) , computer security , filter (signal processing) , economics , computer vision , economic growth
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 1 . 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 1 − N r )π min + N r π max ≈1, our results show rapid convergence and high statistical efficiency for large π min /π max or N r / N 1 and slow convergence and poor statistical efficiency for small π min /π max and N r / N 1 . 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.