ANALYSIS OF A NONREVERSIBLE MARKOV CHAIN SAMPLER
ANALYSIS OF A NONREVERSIBLE MARKOV CHAIN SAMPLER
复制标题
DOI：
10.1214/aoap/1019487508
复制
发表时间：
2000-08
影响因子：
1.8
通讯作者：
P. Diaconis;Susan P. Holmes;Radford M. Neal
中科院分区：
文献类型：
--
作者：
P. Diaconis;Susan P. Holmes;Radford M. Neal
我们分析了一个简单的不可逆马尔可夫链的收敛到平稳性，它是几种实际使用的不可逆马尔可夫链抽样方法的模型。我们的理论和数值结果表明，不可逆性确实可以改善简单马尔可夫链抽样方案的扩散行为。该分析同时使用了概率技术和显式对角化。1.引言。马尔可夫链抽样方法广泛应用于统计学[33，32]、计算机科学[31]、统计力学[3]和量子场论[34，23]。在所有这些领域中，都会遇到难以直接抽样的分布，但对于这些分布，可以很容易地构造出收敛于分布的马尔可夫链。对于许多这样的方法(例如，Metropolis算法[25，13]和随机扫描的Gibbs采样器[17，16])，所构造的马尔可夫链是可逆的。其中一些方法通过扩散随机游走的方式来探索分布。我们使用术语“扩散”来描述过程，如d维格子上的普通随机游动，它需要T2阶的时间来行进距离T。其他一些常见的方法，如系统扫描的Gibbs采样器，使用不可逆的马尔可夫链，但具有类似于相关可逆链的扩散行为[30]。一些马尔可夫链方法试图避免这种扩散探索的低效。混合蒙特卡罗方法[15]使用了一种精心设计的Metropolis方案，可以对州进行大的改变。在由Horowitz[21]提出的这种方法的一个变种中，使用被精心设计为不可逆的马尔可夫链也产生了类似的效果。(这些方法的回顾见[34，23，27]。)超松弛方法[1]也使用不可逆马尔可夫链作为抑制扩散行为的一种方法，如[29]中所讨论的。在本文中，我们分析了一维行走的不可逆马尔可夫链，作为这些实用抽样方法的抽象，特别是Horowitz[21]的抽样方法。古斯塔夫森[19]最近也尝试使用霍洛维茨方法的改编。我们发现不可逆游动确实比通常的简单随机游动收敛得更快。我们分析
We analyze the convergence to stationarity of a simple nonreversible Markov chain that serves as a model for several nonreversible Markov chain sampling methods that are used in practice. Our theoretical and numerical results show that nonreversibility can indeed lead to improvements over the diffusive behavior of simple Markov chain sampling schemes. The analysis uses both probabilistic techniques and an explicit diagonalization. 1. Introduction. Markov chain sampling methods are commonly used in statistics [33, 32], computer science [31], statistical mechanics [3] and quantum field theory [34, 23]. In all these fields, distributions are encountered that are difficult to sample from directly, but for which a Markov chain that converges to the distribution can easily be constructed. For many such methods (e.g., the Metropolis algorithm [25, 13], and the Gibbs sampler [17, 16] with a random scan) the Markov chain constructed is reversible. Some of these methods explore the distribution by means of a diffusive random walk. We use the term “diffusive” for processes like the ordinary random walk on a d-dimensional lattice which require time of order T 2 to travel distance T. Some other common methods, such as the Gibbs sampler with a systematic scan, use a Markov chain that is not reversible, but have diffusive behavior resembling that of a related reversible chain [30]. Some Markov chain methods attempt to avoid the inefficiencies of such diffusive exploration. The Hybrid Monte Carlo method [15] uses an elaborate Metropolis proposal that can make large changes to the state. In a variant of this method due to Horowitz [21], a similar effect is produced using a Markov chain that is carefully designed to be nonreversible. (See [34, 23, 27] for reviews of these methods.) The overrelaxation method [1] also employs a nonreversible Markov chain as a way of suppressing diffusive behavior, as discussed in [29]. In this paper, we analyze a nonreversible Markov chain that does a onedimensional walk, as an abstraction of these practical sampling methods, particularly that of Horowitz [21]. Gustafson [19] has also recently tried using adaptations of Horowitz’s method. We find that the nonreversible walk does indeed converge more rapidly than the usual simple random walk. We ana