The exchange algorithm is one of the most popular extensions of the Metropolis--Hastings algorithm to sample from doubly-intractable distributions. However, the theoretical exploration of the exchange algorithm is very limited. For example, natural questions like `Does exchange algorithm converge at a geometric rate?' or `Does the exchange algorithm admit a Central Limit Theorem?' have not been answered yet. In this paper, we study the theoretical properties of the exchange algorithm, in terms of asymptotic variance and convergence speed. We compare the exchange algorithm with the original Metropolis--Hastings algorithm and provide both necessary and sufficient conditions for the geometric ergodicity of the exchange algorithm. Moreover, we prove that our results can be applied to various practical applications such as location models, Gaussian models, Poisson models, and a large class of exponential families, which includes most of the practical applications of the exchange algorithm. A central limit theorem for the exchange algorithm is also established. Our results justify the theoretical usefulness of the exchange algorithm.
翻译:交换算法是大都会- 尝试算法最受欢迎的延伸, 也是从双重吸引分布中采集的样本。 但是, 交换算法的理论探索非常有限。 例如, “ 交换算法以几何率趋同? ” 或“ 交换算法接受中央限制理论吗? ” 等自然问题尚未解答。 在本文中, 我们研究交换算法的理论性能, 即无症状差异和趋同速度。 我们比较了交换算法与原大都会- 尝试算法, 并为交换算法的几何性提供了必要和充分的条件。 此外, 我们证明, 我们的结果可以应用于各种实际应用, 如地点模型、 高斯模型、 Poisson 模型和一大批指数型家庭, 其中包括交换算法的大部分实际应用。 交换算法的中央限值也被确定。 我们的结果证明交换算法的理论有用性。