Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Mixing times of the biased card shuffling and the asymmetric exclusion process


Authors: Itai Benjamini, Noam Berger, Christopher Hoffman and Elchanan Mossel
Journal: Trans. Amer. Math. Soc. 357 (2005), 3013-3029
MSC (2000): Primary 60J10, 60K35
Published electronically: March 10, 2005
MathSciNet review: 2135733
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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\ne 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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 60J10, 60K35

Retrieve articles in all journals with MSC (2000): 60J10, 60K35


Additional Information

Itai Benjamini
Affiliation: Department of Mathematics, Weizmann Institute, Rehovot 76100, Israel

Noam Berger
Affiliation: Department of Mathematics, California Institute of Technology, Pasadena, California 91125-0050

Christopher Hoffman
Affiliation: Department of Mathematics, University of Washington, Seattle, Washington 98195

Elchanan Mossel
Affiliation: Department of Computer Science, University of California, Berkeley, California 94720

DOI: http://dx.doi.org/10.1090/S0002-9947-05-03610-X
PII: S 0002-9947(05)03610-X
Received by editor(s): June 10, 2003
Received by editor(s) in revised form: June 24, 2003
Published electronically: March 10, 2005
Article copyright: © Copyright 2005 American Mathematical Society