CaltechAUTHORS
  A Caltech Library Service

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

Benjamini, Itai and Berger, Noam and Hoffman, Christopher and Mossel, Elchanan (2005) Mixing times of the biased card shuffling and the asymmetric exclusion process. Transactions of the American Mathematical Society, 357 (8). pp. 3013-3029. ISSN 0002-9947. http://resolver.caltech.edu/CaltechAUTHORS:20090813-150839885

[img]
Preview
PDF - Published Version
See Usage Policy.

247Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20090813-150839885

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 ≠ 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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1090/S0002-9947-05-03610-XDOIUNSPECIFIED
http://www.ams.org/tran/2005-357-08/S0002-9947-05-03610-X/home.htmlPublisherUNSPECIFIED
Additional Information:© 2005 American Mathematical Society. Received by editor(s): June 10, 2003. Received by editor(s) in revised form: June 24, 2003. Posted: March 10, 2005. We thank Persi Diaconis for important comments on a previous version of this paper. We thank Dror Weitz, Prasad Tetali, Thomas Liggett and David Aldous for many interesting discussions. Part of the work was done while Noam Berger was an intern at Microsoft Research. Christopher Hoffman was partially supported by NSF grant #0100445.
Funders:
Funding AgencyGrant Number
NSF0100445
Record Number:CaltechAUTHORS:20090813-150839885
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20090813-150839885
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:15016
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:14 Aug 2009 17:12
Last Modified:26 Dec 2012 11:11

Repository Staff Only: item control page