Abstract
We prove rapid mixing for certain Markov chains on the set Sn of permutations on 1,2,…,n in which adjacent transpositions are made with probabilities that depend on the items being transposed. Typically, when in state σ, a position i < n is chosen uniformly at random, and σ(i) and σ(i+ 1) are swapped with probability depending on σ(i) and σ(i+ 1). The stationary distributions of such chains appear in various fields of theoretical computer science (Wilson, Ann. Appl. Probab. 1:274–325, 2004, Diaconis and Shahshahani, Probab. Theory Relat. Fields 57:159–179, 1981, Chierichetti, et al. 2014), and rapid mixing established in the uniform case (Wilson, Ann. Appl. Probab. 1:274–325, 2004). Recently, there has been progress in cases with biased stationary distributions (Benjamini, et al. Trans. Am. Math. Soc. 357, 3013–3029 2005, Bhakta, et al. 2014), but there are wide classes of such chains whose mixing time is unknown. One case of particular interest is what we call the “gladiator chain,” in which each number g is assigned a “strength” sg and when g and g′ are adjacent and chosen for possible swapping, g comes out on top with probability \(s_{g}/(s_{g} + s_{g^{\prime }})\). We obtain a polynomial-time upper bound on mixing time when the gladiators fall into only three strength classes. A preliminary version of this paper appeared as “Mixing of Permutations by Biased Transposition” in STACS 2017 (Haddadan and Winkler, 2017).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Benjamini et al. use this result to prove that the constant biased adjacent transposition chain is rapidly mixing.
Although the notation \(\mathcal {G}_{k}(n_{1},n_{2},\dots ,n_{k})\) would be more precise (ni being cardinality of Ti), we avoid using it for simplicity and also because our analysis is not dependent on n1,n2,…,nk.
More information about q-binomials can be found in Richard Stanley’s course “Topics in Algebraic Combinatorics,” Chapter 6 (see [11]).
References
Randall, D., Tetali, P.: Analyzing glauber dynamics by comparison of Markov chains. J. Math. Phys. 41, 1598–1615 (2000)
Fill, J.: An interesting spectral gap problem. Unpublished manuscript (2003)
Jerrum, M., Sinclair, A.: Approximating the permanent. SIAM J. Comput. 18, 1149–1178 (1989)
Diaconis, P., Saloff-Coste, L.: Comparison techniques for random walks on finite groups. Ann. Appl. Probab. 21, 2131–2156 (1993)
Martin, R., Randall, D.: Disjoint decomposition of Markov chains and sampling circuits in Cayley graphs. Comb. Probab. Comput. 15, 411–448 (2006)
Diaconis, P., Shahshahani, M.: Generating a random permutation with random transpositions. Probab. Theory Relat. Fields 57, 159–179 (1981)
Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society. http://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf (2009)
Wilson, D.: Mixing times of lozenge tiling and card shuffling Markov chains. Ann. Appl. Probab. 1, 274–325 (2004)
Bhakta, P., Miracle, S., Randall, D., Streib, A.: Mixing times of Markov chains for self-organized lists and biased permutations. 25th Symposium on Discrete Algorithms (SODA) (2014)
Benjamini, I., Berger, N., Hoffman, C., Mossel, E.: Mixing times of the biased card shuffling and the asymmetric exclusion process. Trans. Am. Math. Soc. 357, 3013–3029 (2005)
Stanley, R.P.: Topics in algebraic combinatorics. Course notes for mathematics. Citeseer. http://www-math.mit.edu/rstan/algcomb/algcomb.pdf (2012)
Oliveira, R.I.: Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk. Ann. Probab. 41(2), 871–913 (2013)
Morris, B.: The mixing time for simple exclusion. Ann. Probab. 16(2), 615–635 (2006)
Rivest, R.: On self-organizing sequential search heuristics. Commun. ACM 19 (2), 63–67 (1976)
Hester, J.H., Hirschberg, D.S.: Self-organizing linear search. ACM Comput. Surv. 19, 295–311 (1985)
Haddadan, S., Winkler, P.: Mixing of permutations by biased transposition. 34th Symposium on Theoretical Aspects of Computer Science (STACS) (2017)
Chierichetti, F., Dasgupta, A., Kumar, R., Lattanzi, S.: On reconstructing a hidden permutation. In: proceedings of RANDOM (2014)
Mallows, C.L.: Non-null ranking models. I. Biometrika 44(1-2), 114–130 (1957)
Bayer, D., Diaconis, P.: Trailing the dovetail shuffle to its lair. Ann. Appl. Probab. 2(2), 294–313 (1992)
Miracle, S., Streib, A.P.: Rapid mixing of k-class biased permutations. Latin American Symposium on Theoretical Informatics, pp. 820–834 (2018)
Greenberg, S., Pascoe, A., Randall, D.: Sampling biased lattice configurations using exponential metrics. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’09, New York, New York, pp. 76–85. Society for Industrial and Applied Mathematics, Philadelphia. http://dl.acm.org/citation.cfm?id=1496770.1496779 (2009)
Acknowledgements
We would like to thank Dana Randall for a very helpful conversation about the gladiator problem and Fill’s conjecture, and Sergi Elizalde for his help and knowledge concerning generating functions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This article is part of the Topical Collection on Special Issue on Theoretical Aspects of Computer Science (STACS 2017)
Rights and permissions
About this article
Cite this article
Haddadan, S., Winkler, P. Mixing of Permutations by Biased Transpositions. Theory Comput Syst 63, 1068–1088 (2019). https://doi.org/10.1007/s00224-018-9899-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-018-9899-5