COMPARISON THEOREMS FOR REVERSIBLE MARKOV CHAINS
COMPARISON THEOREMS FOR REVERSIBLE MARKOV CHAINS
复制标题
可逆马尔可夫链的比较定理
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
L. Saloff‐Coste
中科院分区：
文献类型：
--
作者：
P. Diaconis;L. Saloff‐Coste
通过对称性，P具有本征值1=I03>；I381>；？>；I31xI-12-1。通过与同一状态空间上的第二个可逆链的比较，给出了求8I3的上下界的方法。这推广了Diaconis和Saloff-Coste(1993)中引入的思想，其中考虑了有限群上的随机游动。这些界涉及Diaconis和Stroock(1991)直线上的关联图的直径和覆盖数等几何性质。主要应用给出了对称排斥过程第二特征值的一个精确上界。因此，设S0是一个有n个顶点的连通无向图。为简单起见，我们在本简介中假定Sw是常规的。首先，将r个未标记的粒子放置在初始配置1<；r<；n中。在每个步骤中，随机选择一个粒子；然后随机选择该粒子的一个相邻位置。如果邻近站点未被占用，则选定的粒子将移动到那里；如果邻近站点被占用，系统将保持原样。这是{1，2，.。.，n}具有均匀平稳分布。利格特(1985)给出了背景和动机(他专注于无限系统)。Fill(1991)给出了有限圆ZZN上标号排斥过程的第二个特征值的界。我们通过与r-集上的第二个马氏链的比较来研究这个链，第二个马氏链是通过随机挑选一个粒子，随机挑选一个空位(不一定是邻近的位)并将该粒子移动到空位来进行研究的。这是一个经过充分研究的链条(伯努利-拉普拉斯扩散模型)。它的特征值是已知的。我们证明了比较技巧适用于给出排除本征值的上界
By symmetry, P has eigenvalues 1 = I03 > I381 > ?> I 31xI- 1 2 -1. This paper develops methods for getting upper and lower bounds on 8i3 by comparison with a second reversible chain on the same state space. This extends the ideas introduced in Diaconis and Saloff-Coste (1993), where random walks on finite groups were considered. The bounds involve geometric properties such as the diameter and covering number of an associated graph along the lines of Diaconis and Stroock (1991). The main application gives a sharp upper bound on the second eigenvalue of the symmetric exclusion process. Thus, let S0 be a connected undirected graph with n vertices. For simplicity, we assume in this introduction that SW is regular. To start, r unlabelled particles are placed in an initial configuration, 1 < r < n. At each step, a particle is chosen at random; then one of the neighboring sites of this particle is chosen at random. If the neighboring site is unoccupied, the chosen particle is moved there; if the neighboring site is occupied, the system stays as it was. This is a reversible Markov chain on the r-sets of {1, 2, . . ., n} with uniform stationary distribution. Liggett (1985) gives background and motivation (he focuses on infinite systems). Fill (1991) gives bounds on the second eigenvalue of the labeled exclusion process on the finite circle ZZn 1 We study this chain by comparison with a second Markov chain on r-sets that proceeds by picking a particle at random, picking an unoccupied site at random (not necessarily a neighboring site) and moving the particle to the unoccupied site. This is a well studied chain (the Bernoulli-Laplace model for diffusion). Its eigenvalues are known. We show that the comparison techniques apply to give upper bounds on the eigenvalues of the exclusion