Remote Access Transactions of the American Mathematical Society
Green Open Access

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
MR Author ID: 311800

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
MR Author ID: 634876

Elchanan Mossel
Affiliation: Department of Computer Science, University of California, Berkeley, California 94720
MR Author ID: 637297

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