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

DOI:
https://doi.org/10.1090/S0002-9947-05-03610-X

Published electronically:
March 10, 2005

MathSciNet review:
2135733

Full-text PDF

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.**D. Aldous and P. Diaconis,*Shuffling cards and stopping times*, Amer. Math. Monthly**93**(1986), no. 5, 333-348. MR**0841111 (88a:60021)****3.**D. Bayer and P. Diaconis,*Trailing the dovetail shuffle to its lair*, Annals of Applied Probability**2**(1992), 294-313. MR**1161056 (93d:60014)****4.**P. Caputo and F. Martinelli,*Relaxation time of anisotropic simple exclusion processes and quantum Heisenberg models*, Ann. Appl. Probab.**13**(2003), 691-721. MR**1972083****5.**P. Diaconis,*Group representations in probability and statistics*, Institute of Mathematical Statistics Lecture Notes--Monograph Series**11**(1988). MR**0964069 (90a:60001)****6.**P. 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, 187-204. MR**1648031 (99e:60154)****7.**P. Diaconis and A. Ram,*Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques*, Michigan Math. J.**48**(2000), 157-190. MR**1786485 (2001j:60132)****8.**P. Diaconis and L. Saloff-Coste,*What do we know about the Metropolis algorithm*? 27th Annual STOC, J. Comput. System Sci.**57**(1998), 20-36. MR**1649805 (2000b:68094)****9.**U. Feige, D. Peleg, P. Raghavan and E. Upfal,*Computing with unreliable information*, STOC**90**(1990), 128-137.**10.**G. Fishman,*Coordinate selection rules for Gibbs sampling*, Ann. Appl. Probab.**6**(1996), 444-465. MR**1398053 (97k:62058)****11.**E. Gilbert, Bell Lab technical report, 1955.**12.**C. Kipnis,*Central limit theorems for infinite series of queues and applications to simple exclusion*, Ann. Probab.**14**, no. 2, (1986), 397-408. MR**0832016 (88a:60173)****13.**J. Reeds, unpublished manuscript, 1981.**14.**T. M. Liggett,*Interacting particle systems*, Springer, 1985, Grundlehren der mathematischen Wissenschaften, 276. MR**0776231 (86e:60089)****15.**T. M. Liggett,*Stochastic interacting systems*:*contact, voter, and exclusion processes*, Springer, New York, 1999. Grundlehren der mathematischen Wissenschaften, 324. MR**1717346 (2001q:60247)****16.**L. Saloff-Coste,*Lectures on finite Markov chains*, Lectures on probability theory and statistics (Saint-Flour, 1996), 301-413, Lecture Notes in Math., 1665, Springer, 1996. MR**1490046 (99b:60119)****17.**D. Wilson,*Mixing times of lozenge tiling and card shuffling Markov chains*, Ann. Appl. Probab.**14**, no. 1, (2004), 274-325. MR**2023023**

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:
https://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