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 cards numbered 1 through . Fix a parameter 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 . 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 , the mixing time of this card shuffling is , 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.

**1.**D. Aldous and J. A. Fill,*Reversible Markov chains and random walks on graphs*, book in preparation, 2002.**2.**David Aldous and Persi Diaconis,*Shuffling cards and stopping times*, Amer. Math. Monthly**93**(1986), no. 5, 333–348. MR**841111**, 10.2307/2323590**3.**Dave Bayer and Persi Diaconis,*Trailing the dovetail shuffle to its lair*, Ann. Appl. Probab.**2**(1992), no. 2, 294–313. MR**1161056****4.**Gert Brodin, Lennart Stenflo, Dan Anderson, Mietek Lisak, Mattias Marklund, and Pontus Johannisson,*Light bullets and optical collapse in vacuum*, Phys. Lett. A**306**(2003), no. 4, 206–210. MR**1972083**, 10.1016/S0375-9601(02)01512-8**5.**Persi Diaconis,*Group representations in probability and statistics*, Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11, Institute of Mathematical Statistics, Hayward, CA, 1988. MR**964069****6.**Persi Diaconis,*From shuffling cards to walking around the building: an introduction to modern Markov chain theory*, Proceedings of the International Congress of Mathematicians, Vol. I (Berlin, 1998), 1998, pp. 187–204. MR**1648031****7.**Persi Diaconis and Arun Ram,*Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques*, Michigan Math. J.**48**(2000), 157–190. Dedicated to William Fulton on the occasion of his 60th birthday. MR**1786485**, 10.1307/mmj/1030132713**8.**P. Diaconis and L. Saloff-Coste,*What do we know about the Metropolis algorithm?*, J. Comput. System Sci.**57**(1998), no. 1, 20–36. 27th Annual ACM Symposium on the Theory of Computing (STOC’95) (Las Vegas, NV). MR**1649805**, 10.1006/jcss.1998.1576**9.**U. Feige, D. Peleg, P. Raghavan and E. Upfal,*Computing with unreliable information*, STOC**90**(1990), 128-137.**10.**George S. Fishman,*Coordinate selection rules for Gibbs sampling*, Ann. Appl. Probab.**6**(1996), no. 2, 444–465. MR**1398053**, 10.1214/aoap/1034968139**11.**E. Gilbert, Bell Lab technical report, 1955.**12.**Claude Kipnis,*Central limit theorems for infinite series of queues and applications to simple exclusion*, Ann. Probab.**14**(1986), no. 2, 397–408. MR**832016****13.**J. Reeds, unpublished manuscript, 1981.**14.**Thomas M. Liggett,*Interacting particle systems*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 276, Springer-Verlag, New York, 1985. MR**776231****15.**Thomas M. Liggett,*Stochastic interacting systems: contact, voter and exclusion processes*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 324, Springer-Verlag, Berlin, 1999. MR**1717346****16.**Laurent Saloff-Coste,*Lectures on finite Markov chains*, Lectures on probability theory and statistics (Saint-Flour, 1996) Lecture Notes in Math., vol. 1665, Springer, Berlin, 1997, pp. 301–413. MR**1490046**, 10.1007/BFb0092621**17.**David Bruce Wilson,*Mixing times of Lozenge tiling and card shuffling Markov chains*, Ann. Appl. Probab.**14**(2004), no. 1, 274–325. MR**2023023**, 10.1214/aoap/1075828054

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

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