Polynomial mixing of the edge-flip Markov chain for unbiased dyadic\n tilings

2016/11/11 by Sarah Cannon, Cannon, Sarah, David Levin +4 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Cellular Automata and Applications #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1611.03636

openalex publication_date 2016/11/11 · openalex created_date 2022/08/20 · openalex updated_date 2026/07/28

Abstract

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

Cited by

• On weighted partial triangulations of convex polygons

Related

• Polynomial mixing time of edge flips on quadrangulations
• Mixing Time for Square Tilings
• Mixing time bounds for edge flipping on regular graphs
• Mixing time bounds for edge flipping on regular graphs
• Analysis of a non-reversible Markov chain speedup by a single edge