Mixing times of the biased card shuffling and the asymmetric exclusion process
Mixing times of the biased card shuffling and the asymmetric exclusion process
复制标题
偏向洗牌和不对称排除过程的混合时间
DOI：
10.1090/s0002-9947-05-03610-x
复制
发表时间：
2002
影响因子：
1.3
通讯作者：
Elchanan Mossel
中科院分区：
文献类型：
--
作者：
I. Benjamini;Noam Berger;C. Hoffman;Elchanan Mossel
考虑以下洗牌方法。从一副编号为 1 到 N 的 N 张牌开始。将参数 p 固定在 0 和 1 之间。在此模型中，“洗牌”包括均匀选择一对相邻的牌，然后翻转一枚正面朝上的概率为 p 的硬币。如果硬币正面朝上，那么我们将两张牌排列起来，使数字较小的牌出现在数字较大的牌之前。如果硬币出现反面，则我们先将数字较大的卡片排列。在本文中，我们证明对于所有 p ≠ 1/2，洗牌的混合时间为 O(N^2)，正如 Diaconis 和 Ram (2000) 所推测的那样。我们的结果是对 Metropolis 算法收敛速度进行精确估计的罕见情况。我们证明的一个新颖特征是，无限（不对称排除）过程的分析在限制有限过程的混合时间方面起着至关重要的作用。
Consider the following method of card shuffling. Start with a deck of N cards numbered 1 through N. Fix a parameter p between 0 and 1. In this model a "shuffle" consists of uniformly selecting a pair of adjacent cards and then flipping a coin that is heads with probability p. If the coin comes up heads, then we arrange the two cards so that the lower-numbered card comes before the higher-numbered card. If the coin comes up tails, then we arrange the cards with the higher-numbered card first. In this paper we prove that for all p ≠ 1/2, the mixing time of this card shuffling is O(N^2), as conjectured by Diaconis and Ram (2000). Our result is a rare case of an exact estimate for the convergence rate of the Metropolis algorithm. A novel feature of our proof is that the analysis of an infinite (asymmetric exclusion) process plays an essential role in bounding the mixing time of a finite process.