Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
From MaRDI portal
(Redirected from Publication:5222542)
Combinatorial aspects of tessellation and tiling problems (05B45) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
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}] imes [b2^{-t}, (b+1)2^{-t}] for non-negative integers a,b,s,t. 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(nlog n) coming from the diameter of the chain.
Recommendations
- Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
- Phase transitions in random dyadic tilings and rectangular dissections
- Phase transitions in random dyadic tilings and rectangular dissections
- Generalized dominoes tiling's Markov chain mixes fast
- Polynomial mixing time of edge flips on quadrangulations
Cites work
- A Lyapunov function for Glauber dynamics on lattice triangulations
- Analyzing Glauber dynamics by comparison of Markov chains
- Comparison theorems for reversible Markov chains
- Complete subdivision algorithms, II
- Counting dyadic equipartitions of the unit square
- Critical Ising on the square lattice mixes in polynomial time
- Dynamics of lattice triangulations on thin rectangles
- Equation of state calculations by fast computing machines
- Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability
- Glauber dynamics for the mean-field Potts model
- scientific article; zbMATH DE number 1188961 (Why is no real title available?)
- scientific article; zbMATH DE number 1241390 (Why is no real title available?)
- scientific article; zbMATH DE number 1418384 (Why is no real title available?)
- Markov chain algorithms for planar lattice structures
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Minimax-optimal classification with dyadic decision trees
- Mixing time of critical Ising model on trees is polynomial in the height
- Mixing times of critical two-dimensional Potts models
- Phase transitions in random dyadic tilings and rectangular dissections
- Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields
- Random dyadic tilings of the unit square
- Random lattice triangulations: structure and algorithms
- Sampling Regular Graphs and a Peer-to-Peer Network
- The mixing time evolution of Glauber dynamics for the mean-field Ising model
- The switch Markov chain for sampling irregular graphs and digraphs
Cited in
(6)- A polynomial upper bound for the mixing time of edge rotations on planar maps
- Polynomial mixing time of edge flips on quadrangulations
- scientific article; zbMATH DE number 1741010 (Why is no real title available?)
- Phase transitions in random dyadic tilings and rectangular dissections
- Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
- Phase transitions in random dyadic tilings and rectangular dissections
This page was built for publication: Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222542)
