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

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?)

  • 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

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

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

American Mathematical Society