Document Open Access Logo

Iterated Decomposition of Biased Permutations via New Bounds on the Spectral Gap of Markov Chains

Authors Sarah Miracle, Amanda Pascoe Streib, Noah Streib

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2020.3.pdf
  • Filesize: 0.55 MB
  • 21 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
Keywords
  • Markov chains
  • Permutations
  • Decomposition
  • Spectral Gap
  • Iterated Decomposition

Metrics

Abstract

In this paper, we address a conjecture of Fill [Fill03] about the spectral gap of a nearest-neighbor transposition Markov chain ℳ_nn over biased permutations of [n]. Suppose we are given a set of input probabilities 𝒫 = {p_{i,j}} for all 1 ≤ i, j ≤ n with p_{i, j} = 1-p_{j, i}. The Markov chain ℳ_nn operates by uniformly choosing a pair of adjacent elements, i and j, and putting i ahead of j with probability p_{i,j} and j ahead of i with probability p_{j,i}, independent of their current ordering. 
We build on previous work [S. Miracle and A.P. Streib, 2018] that analyzed the spectral gap of ℳ_nn when the particles in [n] fall into k classes. There, the authors iteratively decomposed ℳ_nn into simpler chains, but incurred a multiplicative penalty of n^-2 for each application of the decomposition theorem of [Martin and Randall, 2000], leading to an exponentially small lower bound on the gap. We make progress by introducing a new complementary decomposition theorem. We introduce the notion of ε-orthogonality, and show that for ε-orthogonal chains, the complementary decomposition theorem may be iterated O(1/√ε) times while only giving away a constant multiplicative factor on the overall spectral gap. We show the decomposition given in [S. Miracle and A.P. Streib, 2018] of a related Markov chain ℳ_pp over k-class particle systems is 1/n²-orthogonal when the number of particles in each class is at least C log n, where C is a constant not depending on n. We then apply the complementary decomposition theorem iteratively n times to prove nearly optimal bounds on the spectral gap of ℳ_pp and to further prove the first inverse-polynomial bound on the spectral gap of ℳ_nn when k is as large as Θ(n/log n). The previous best known bound assumed k was at most a constant.

Cite As Get BibTex

Sarah Miracle, Amanda Pascoe Streib, and Noah Streib. Iterated Decomposition of Biased Permutations via New Bounds on the Spectral Gap of Markov Chains. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 3:1-3:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.3

Author Details

Sarah Miracle
  • University of St. Thomas, St. Paul, MN, USA
Amanda Pascoe Streib
  • Center for Computing Sciences, Bowie, MD, USA
Noah Streib
  • Center for Computing Sciences, Bowie, MD, USA

Acknowledgements

We wish to thank Dana Randall for several useful discussions about the decomposition method.

References

  1. D. Aldous. Random walk on finite groups and rapidly mixing Markov chains. In Seminaire de Probabilites XVII, pages 243-297, 1983. Google Scholar
  2. D. Bayer and P. Diaconis. Trailing the dovetail shuffle to its lair. The Annals of Applied Probability, 2:295-313, 1992. Google Scholar
  3. I. Benjamini, N. Berger, C. Hoffman, and E. Mossel. Mixing times of the biased card shuffling and the asymmetric exclusion process. Trans. Amer. Math. Soc, 357:3013-3029, 2005. Google Scholar
  4. P. Bhakta, S. Miracle, D. Randall, and A. P. Streib. Mixing times of Markov chains for self-organizing lists and biased permutations. In Proceedings of the 24th ACM/SIAM Symposium on Discrete Algorithms, SODA '13, pages 1-15, 2013. Google Scholar
  5. F. Chierichetti, A. Dasgupta, R. Kumar, and S. Lattanzi. On reconstructing a hidden permutation. Leibniz International Proceedings in Informatics, LIPIcs, 28:604-617, September 2014. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.604.
  6. C. Cooper, M. Dyer, A. Frieze, and R. Rue. Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids. Journal of Mathematical Physics, 41(3):1499-1527, 2000. URL: https://doi.org/10.1063/1.533194.
  7. N. Destainville. Bounding spectral gaps of markov chains: a novel exact multi-decomposition technique. Journal of Physics A: Mathematical and General, 36(13):3647-3670, March 2003. URL: https://doi.org/10.1088/0305-4470/36/13/301.
  8. P. Diaconis and L. Saloff-Coste. Comparison techniques for random walks on finite groups. The Annals of Applied Probability, 21:2131-2156, 1993. Google Scholar
  9. P. Diaconis and L. Saloff-Coste. Comparison theorems for reversible Markov chains. Annals of Applied Probability, 3:696-730, 1993. Google Scholar
  10. P. Diaconis and M. Shahshahani. Generating a random permutation with random transpositions. Z. Wahrscheinlichkeitstheorie Verw. Gebiete, 57:159-179, 1981. Google Scholar
  11. J. Ding, E. Lubetzky, and Yuval Peres. Mixing time of critical Ising model on trees is polynomial in the height. Communications in Mathematical Physics, 295(1):161-207, April 2010. Google Scholar
  12. P.L. Erdős, I. Miklós, and Z. Toroczkai. New classes of degree sequences with fast mixing swap Markov chain sampling. Combinatorics Probability and Computing, 27(2):186-207, 2018. Google Scholar
  13. J. Fill. Background on the gap problem. Unpublished manuscript, 2003. Google Scholar
  14. J. Fill. An interesting spectral gap problem. Unpublished manuscript, 2003. Google Scholar
  15. R. Grone, K. Heinz Hoffmann, and P. Salamon. An interlacing theorem for reversible Markov chains. Journal of Physics A: Mathematical and Theoretical, 41(21):212002, May 2008. URL: https://doi.org/10.1088/1751-8113/41/21/212002.
  16. S. Haddadan and P. Winkler. Mixing of permutations by biased transposition. In 34th Symposium on Theoretical Aspects of Computer Science, STACS '17, pages 41:1-41:13, 2017. Google Scholar
  17. J. H. Hester and D. S. Hirschberg. Self-organizing linear search. ACM Computing Surveys (CSUR), 17 Issue 3:295-311, 1985. Google Scholar
  18. M. Jerrum, J. Son, P. Tetali, and E. Vigoda. Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains. Ann. Appl. Probab., 14(4):1741-1765, November 2004. URL: https://doi.org/10.1214/105051604000000639.
  19. Donald K. The Art of Computer Programming, volume 2: Seminumerical Algorithms. Addison-Wesley, 1969. Google Scholar
  20. D. A. Levin, Y. Peres, and E. L. Wilmer. Markov chains and mixing times. American Mathematical Society, 2006. Google Scholar
  21. N. Madras and D. Randall. Markov chain decomposition for convergence rate analysis. Annals of Applied Probability, pages 581-606, 2002. Google Scholar
  22. Y. Mao and Liang H. Spectral gap for open Jackson networks. Acta Mathematica Sinica, English Series, 31:1879-1894, December 2015. URL: https://doi.org/10.1007/s10114-015-4138-3.
  23. R. Martin and D. Randall. Sampling adsorbing staircase walks using a new Markov chain decomposition method. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, pages 492-502, 2000. Google Scholar
  24. S. Miracle, D. Randall, and A. P. Streib. Cluster algorithms for discrete models of colloids with bars. In 8th Workshop on Analytic Algorithmics and Combinatorics, ANALCO, pages 135-150, 2011. Google Scholar
  25. S. Miracle and A.P. Streib. Rapid mixing of k-class biased permutations. In LATIN, volume 10807 of Lecture Notes in Computer Science, pages 820-834. Springer, 2018. Google Scholar
  26. N. Pillai and A. Smith. Elementary bounds on mixing times for decomposable Markov chains. Stochastic Processes and their Applications, 127(9):3068-3109, 2017. URL: https://doi.org/10.1016/j.spa.2017.02.002.
  27. D. Randall. Decomposition methods and sampling circuits in the Cartesian lattice. In Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, MFCS '01, pages 74-86, London, UK, UK, 2001. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=645730.668026.
  28. D. Randall and P. Tetali. Analyzing Glauber dynamics by comparison of Markov chains. Journal of Mathematical Physics, 41:1598-1615, 2000. Google Scholar
  29. O. Reingold, S. Vadhan, and A. Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, FOCS '00, pages 3-13, Washington, DC, USA, 2000. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=795666.796583.
  30. R. Rivest. On self-organizing sequential search heuristics. Commun. ACM, 19(2):63–67, February 1976. URL: https://doi.org/10.1145/359997.360000.
  31. S. Vadhan. Pseudorandomness. Foundations and Trends® in Theoretical Computer Science, 7(1–3):1-336, 2012. URL: https://doi.org/10.1561/0400000010.
  32. D. Wilson. Mixing times of lozenge tiling and card shuffling Markov chains. The Annals of Applied Probability, 1:274-325, 2004. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact