Document Open Access Logo

Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings

Authors Sarah Cannon, David A. Levin, Alexandre Stauffer

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.34.pdf
  • Filesize: 2.17 MB
  • 21 pages

Document Identifiers

Author Details

Sarah Cannon
David A. Levin
Alexandre Stauffer

Cite As Get BibTex

Sarah Cannon, David A. Levin, and Alexandre Stauffer. Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 34:1-34:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.34

Abstract

We give the first polynomial upper bound on the mixing time of the edge-flip Markov chain for unbiased dyadic tilings, resolving an open problem originally posed by Janson, Randall, and Spencer in 2002. A dyadic tiling of size n is a tiling of the unit square by n non-overlapping dyadic rectangles, each of area 1/n, where a dyadic rectangle is any rectangle that can be written in the form [a2^{-s}, (a+1)2^{-s}] x [b2^{-t}, (b+1)2^{-t}] for a,b,s,t nonnegative integers. The edge-flip Markov chain selects a random edge of the tiling and replaces it with its perpendicular bisector if doing so yields a valid dyadic tiling. Specifically, we show that the relaxation time of the edge-flip Markov chain for dyadic tilings is at most O(n^{4.09}), which implies that the mixing time is at most O(n^{5.09}). We complement this by showing that the relaxation time is at least Omega(n^{1.38}), improving upon the previously best lower bound of Omega(n*log n) coming from the diameter of the chain.

Subject Classification

Keywords
  • Random dyadic tilings
  • spectral gap
  • rapid mixing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Russ Bubley and Martin Dyer. Path coupling: A technique for proving rapid mixing in markov chains. In FOCS'97: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), 1997. Google Scholar
  2. Michael Burr, Sung Woo Choi, Ben Galehouse, and Chee K. Yap. Complete subdivision algorithms, II: Isotopic meshing of singular algebraic curves. Journal of Symbolic Computation, 47(2):131-152, 2012. URL: http://dx.doi.org/10.1016/j.jsc.2011.08.021.
  3. Sarah Cannon, Sarah Miracle, and Dana Randall. Phase transitions in random dyadic tilings and rectangular dissections. In Proceedings of the 26th Symposium on Discrete Algorithms (SODA), 2015. Google Scholar
  4. Pietro Caputo, Fabio Martinelli, Alistair Sinclair, and Alexandre Stauffer. Random lattice triangulations: Structure and algorithms. The Annals of Applied Probability, 25(4):1650-1685, 2015. Google Scholar
  5. Pietro Caputo, Fabio Martinelli, Alistair Sinclair, and Alexandre Stauffer. Dynamics of lattice triangulations on thin rectangles. Electronic Journal of Probability, 21(29), 2016. Google Scholar
  6. Filippo Cesi. Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields. Probability Theory and Related Fields, 120(4):569-584, 2001. URL: http://dx.doi.org/10.1007/PL00008792.
  7. Mu-Fa Chen. Trilogy of couplings and general formulas for lower bound of spectral gap. In Probability towards 2000 (New York, 1995), volume 128 of Lecture Notes in Statist., pages 123-136. Springer, New York, 1998. URL: http://dx.doi.org/10.1007/978-1-4612-2224-8_7.
  8. Colin Cooper, Martin Dyer, and Catherine Greenhill. Sampling regular graphs and a peer-to-peer network. Combinatorics, Probability and Computing, 16(4):557-593, July 2007. URL: http://dx.doi.org/10.1017/S0963548306007978.
  9. P. Cuff, J. Ding, O. Louidor, E. Lubetzky, Y. Peres, and A. Sly. Glauber dynamics for the mean-field Potts model. Journal of Statistical Physics, 149(3):432-477, 2012. URL: https://search.ebscohost.com/login.aspx?direct=true&db=a9h&AN=82730695&site=eds-live&scope=site.
  10. Persi Diaconis and Laurent Saloff-Coste. Comparison theorems for reversible Markov chains. The Annals of Applied Probability, 3:696-730, 1993. Google Scholar
  11. Jian Ding, Eyal Lubetzky, and Yuval Peres. The mixing time evolution of Glauber dynamics for the mean-field Ising model. Communications in Mathematical Physics, 289(2):725-764, 2009. URL: http://dx.doi.org/10.1007/s00220-009-0781-9.
  12. Jian Ding, Eyal 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, 2010. URL: http://dx.doi.org/10.1007/s00220-009-0978-y.
  13. Reza Gheissari and Eyal Lubetzky. Mixing times of critical 2D Potts models. Submitted. Available at URL: https://arxiv.org/abs/1607.02182.
  14. Catherine Greenhill. The switch Markov chain for sampling irregular graphs. In Proceedings of the 26th Symposium on Discrete Algorithms (SODA), 2015. Google Scholar
  15. OEIS Foundation Inc. The on-line encyclopedia of integer sequences, 2017. URL: http://oeis.org/A062764.
  16. Svante Janson, Dana Randall, and Joel Spencer. Random dyadic tilings of the unit square. Random Structures and Algorithms, 21:225-251, 2002. Google Scholar
  17. Jeffery C. Lagarias, Joel H. Spencer, and Jade P. Vinson. Counting dyadic equipartitions of the unit square. Discrete Mathematics, 257(2-3):481-499, November 2002. URL: http://dx.doi.org/10.1016/S0012-365X(02)00508-3.
  18. David A. Levin, Malwina J. Luczak, and Yuval Peres. Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability. Probab. Theory Related Fields, 146(1-2):223-265, 2010. URL: http://dx.doi.org/10.1007/s00440-008-0189-z.
  19. David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, Providence, RI, 2009. Google Scholar
  20. Eyal Lubetzky and Allan Sly. Critical Ising on the square lattice mixes in polynomial time. Communications in Mathematical Physics, 313(3):815-836, 2012. URL: http://dx.doi.org/10.1007/s00220-012-1460-9.
  21. Michael Luby, Dana Randall, and Alistair Sinclair. Markov chain algorithms for planar lattice structures. SIAM Journal on Computing, 31:167-192, 2001. Google Scholar
  22. Fabio Martinelli. Lectures on Glauber dynamics for discrete spin models. In Pierre Bernard, editor, Lectures on Probability Theory and Statistics: Ecole d'Eté de Probailités de Saint-Flour XXVII - 1997, pages 93-191. Springer Berlin Heidelberg, Berlin, Heidelberg, 1999. URL: http://dx.doi.org/10.1007/978-3-540-48115-7_2.
  23. Leslie McShine and Prasad Tetali. On the mixing time of the triangulation walk and other Catalan structures. DIMACS-AMS Volume on Randomization Methods in Algorithm Design, 43:147-160, 1998. Google Scholar
  24. N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller. Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21:1087-1092, 1953. Google Scholar
  25. Dana Randall and Prasad Tetali. Analyzing Glauber dynamics by comparison of Markov chains. Journal of Mathematical Physics, 41:1598-1615, 2000. Google Scholar
  26. Clayton Scott and Robert D. Nowak. Minimax-optimal classification with dyadic decision trees. IEEE Transactions on Information Theory, 52(4), 2006. Google Scholar
  27. Alexandre Stauffer. A Lyapunov function for Glauber dynamics on lattice triangulations. Probability Theory and Related Fields, to appear. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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