Abstract
In this paper, we study a biased version of the nearest-neighbor transposition Markov chain on the set of permutations where neighboring elements i and j are placed in order (i, j) with probability \(p_{i,j}\). Our goal is to identify the class of parameter sets \(\mathbf{P} = \{p_{i,j}\}\) for which this Markov chain is rapidly mixing. Specifically, we consider the open conjecture of Jim Fill that all monotone, positively biased distributions are rapidly mixing.
We resolve Fill’s conjecture in the affirmative for distributions arising from k-class particle processes, where the elements are divided into k classes and the probability of exchanging neighboring elements depends on the particular classes the elements are in. We further require that k is a constant, and all probabilities between elements in different classes are bounded away from 1/2. These particle processes arise in the context of self-organizing lists and our result also applies beyond permutations to the setting where all particles in a class are indistinguishable. Our work generalizes recent work by Haddadan and Winkler (STACS ’17) studying 3-class particle processes. Additionally we show that a broader class of distributions based on trees is also rapidly mixing, which generalizes a class analyzed by Bhakta et al. (SODA ’13).
Our proof involves analyzing a generalized biased exclusion process, which is a nearest-neighbor transposition chain applied to a 2-particle system. Biased exclusion processes are of independent interest, with applications in self-assembly. We generalize the results of Greenberg et al. (SODA ’09) and Benjamini et al. (Trans. AMS ’05) on biased exclusion processes to allow the probability of swapping neighboring elements to depend on the entire system, as long as the minimum bias is bounded away from 1.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We assume, in order to ensure the distribution is positively biased, that for all \(i\le k\), \({C}_i = \{a_{i-1}+1,a_{i-1}+2,\ldots ,a_i\}\), for some sequence \(0=a_0<a_1< a_2< \ldots < a_{k-1}\).
References
Knuth, D.: The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, Boston (1969)
Aldous, D.J.: Random walks on finite groups and rapidly mixing Markov chains. Séminaire de probabilités de Strasbourg 17, 243–297 (1983)
Diaconis, P., Shahshahani, M.: Generating a random permutation with random transpositions. Z. Wahrscheinlichkeitstheorie Verw. Gebiete 57, 159–179 (1981)
Diaconis, P., Saloff-Coste, L.: Comparison techniques for random walks on finite groups. Ann. Appl. Probab. 21, 2131–2156 (1993)
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-organizing lists and biased permutations. In: Proceedings of the 24th ACM/SIAM Symposium on Discrete Algorithms, SODA 2013, pp. 1–15 (2013)
Fill, J.: An interesting spectral gap problem (2003, unpublished manuscript)
Fill, J.: Background on the gap problem (2003, unpublished manuscript)
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)
Hester, J.H., Hirschberg, D.S.: Self-organizing linear search. Comput. Surv. 17, 295–311 (1985)
Haddadan, S., Winkler, P.: Mixing of permutations by biased transposition. In: 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, pp. 41:1–41:13 (2017)
Spitzer, F.: Interaction of Markov processes. Adv. Math. 5, 240–290 (1970)
Luby, M., Randall, D., Sinclair, A.: Markov chain algorithms for planar lattice structures. SIAM J. Comput. 31, 167–192 (2001)
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 2009 (2009)
Pascoe, A., Randall, D.: Self-assembly and convergence rates of heterogenous reversible growth processes. In: Foundations of Nanoscience (2009)
Labbé, C., Lacoin, H.: Cutoff phenomenon for the asymmetric simple exclusion process and the biased card shuffling. arXiv:1610.07383v1 (2016)
Levin, D., Peres, Y.: Mixing of the exclusion process with small bias. J. Stat. Phys. 165, 1036–1050 (2016)
Greenberg, S., Randall, D., Streib, A.: Sampling biased monotonic surfaces using exponential metrics (2017)
Martin, R., Randall, D.: Sampling adsorbing staircase walks using a new Markov chain decomposition method. In: Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, pp. 492–502 (2000)
Martin, R., Randall, D.: Disjoint decomposition of Markov chains and sampling circuits in cayley graphs. Comb. Probab. Comput. 15, 411–448 (2006)
Sinclair, A.: Algorithms for Random Generation and Counting. Progress in Theoretical Computer Science. Birkhäuser, Basel (1993)
Randall, D.: Mixing. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (2003)
Madras, N., Randall, D.: Markov chain decomposition for convergence rate analysis. Ann. Appl. Probab. 12, 581–606 (2002)
Diaconis, P., Saloff-Coste, L.: Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3, 696–730 (1993)
Randall, D., Tetali, P.: Analyzing Glauber dynamics by comparison of Markov chains. J. Math. Phys. 41, 1598–1615 (2000)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Miracle, S., Streib, A.P. (2018). Rapid Mixing of k-Class Biased Permutations. In: Bender, M., Farach-Colton, M., Mosteiro, M. (eds) LATIN 2018: Theoretical Informatics. LATIN 2018. Lecture Notes in Computer Science(), vol 10807. Springer, Cham. https://doi.org/10.1007/978-3-319-77404-6_59
Download citation
DOI: https://doi.org/10.1007/978-3-319-77404-6_59
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-77403-9
Online ISBN: 978-3-319-77404-6
eBook Packages: Computer ScienceComputer Science (R0)