LIPIcs.STACS.2017.41.pdf
- Filesize: 0.68 MB
- 13 pages
Document
Mixing of Permutations by Biased Transposition
Authors
-
Part of:
Volume:
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-03-06
Cite As Get BibTex
Shahrzad Haddadan and Peter Winkler. Mixing of Permutations by Biased Transposition. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.STACS.2017.41
Abstract
Markov chains defined on the set of permutations of n elements have been studied widely by mathematicians and theoretical computer scientists. We consider chains in which a position i<n is chosen uniformly at random, and then sigma(i) and sigma(i+1) are swapped with probability depending on sigma(i) and sigma(i+1). Our objective is to identify some conditions that assure rapid mixing. One case of particular interest is what we call the "gladiator chain," in which each number g is assigned a "strength" s_g and when g and g' are swapped, g comes out on top with probability s_g / ( s_g + s_g' ). The stationary probability of this chain is the same as that of the slow-mixing "move ahead one" chain for self-organizing lists, but an open conjecture of Jim Fill's implies that all gladiator chains mix rapidly. Here we obtain some positive partial results by considering cases where the gladiators fall into only a few strength classes.
Subject Classification
Keywords
- Markov chains
- permutations
- self organizing lists
- mixing time
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
I. Benjamini, N. Berger, C. Hoffman, and Mossel E. Mixing times of the biased card shuffling and the asymmetric exclusion process. Transactions of the American Mathematical Society, 357:3013-3029, 2005.
-
P. Bhakta, S. Miracle, D. Randall, and A. Streib. Mixing times of Markov chains for self-organized lists and biased permutations. 25th Symposium on Discrete Algorithms (SODA), 2014.
-
P. Diaconis and L. Saloff-Coste. Comparison techniques for random walks on finite groups. The annals of applied probability, 21:1149-1178, 1993.
-
P. Diaconis and M. Shahshahani. Generating a random permutation with random transpositions. Probablity theory and related fields, 57:159-179, 1981.
-
J. Fill. An interesting spectral gap problem, 2003. Unpublished manuscript.
-
J. H. Hester and D. S. Hirscheberg. Self-organizing linear search. ACM Computing survey, 19:295-311, 1985.
-
M. Jerrum and Sinclair A. Approximating the permanent. SIAM Journal on computing, 18:1149-1178, 1989.
-
D. A. Levin, Y. Peres, and E. L. Wilmer. Markov chains and Mixing times. American Mathematical Society, 2009.
-
R. Martin and D. Randall. Disjoint decomposition of Markov chains and sampling circuits in cayley graphs. Combinatorics, Probability and Computing, 15:411-448, 2006.
-
B. Morris. The mixing time for simple exclusion. Annals of probabilty, 16:63-67, 1976.
-
R. I. Oliveria. Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk. Annals of probablity, 41:871-913, 2013.
-
D. Randall and P. Tatali. Analyzing glauber dynamics by comparision of Markov chains. Journal of Mathematical Physics, 41:1598-1615, 2000.
-
R. Rivest. On self-organizing sequential search heuristics. Communication of the ACM, 19:63-67, 1976.
- R. P. Stanley. Topics in algebraic combinatorics, 2012. Course notes for Mathematics, 2012. URL: http://www-math.mit.edu/~rstan/algcomb/algcomb.pdf.
-
D. Wilson. Mixing times of lozenge tiling and card shuffling Markov chains. The annals of applied probablity, 1:274-325, 2004.