Mixing times of the biased card shuffling and the asymmetric exclusion process
HTML articles powered by AMS MathViewer
- by Itai Benjamini, Noam Berger, Christopher Hoffman and Elchanan Mossel PDF
- Trans. Amer. Math. Soc. 357 (2005), 3013-3029 Request permission
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
- D. Aldous and J. A. Fill, Reversible Markov chains and random walks on graphs, book in preparation, 2002.
- David Aldous and Persi Diaconis, Shuffling cards and stopping times, Amer. Math. Monthly 93 (1986), no. 5, 333–348. MR 841111, DOI 10.2307/2323590
- Dave Bayer and Persi Diaconis, Trailing the dovetail shuffle to its lair, Ann. Appl. Probab. 2 (1992), no. 2, 294–313. MR 1161056
- 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, DOI 10.1016/S0375-9601(02)01512-8
- Persi Diaconis, Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988. MR 964069, DOI 10.1007/BFb0086177
- 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
- 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, DOI 10.1307/mmj/1030132713
- 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, DOI 10.1006/jcss.1998.1576
- U. Feige, D. Peleg, P. Raghavan and E. Upfal, Computing with unreliable information, STOC 90 (1990), 128–137.
- George S. Fishman, Coordinate selection rules for Gibbs sampling, Ann. Appl. Probab. 6 (1996), no. 2, 444–465. MR 1398053, DOI 10.1214/aoap/1034968139
- E. Gilbert, Bell Lab technical report, 1955.
- 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
- J. Reeds, unpublished manuscript, 1981.
- Thomas M. Liggett, Interacting particle systems, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 276, Springer-Verlag, New York, 1985. MR 776231, DOI 10.1007/978-1-4613-8542-4
- 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, DOI 10.1007/978-3-662-03990-8
- 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, DOI 10.1007/BFb0092621
- David Bruce Wilson, Mixing times of Lozenge tiling and card shuffling Markov chains, Ann. Appl. Probab. 14 (2004), no. 1, 274–325. MR 2023023, DOI 10.1214/aoap/1075828054
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
- © Copyright 2005 American Mathematical Society
- 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
- MathSciNet review: 2135733