Projects per year

## 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 [14]. 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} ] × [b2
^{-t} , (b + 1)2
^{-t} ] for a, b, s, t EZ≥ 0. 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 Ω(n
^{1.38} ), improving upon the previously best lower bound of Ω(n log n) coming from the diameter of the chain.

Original language | English |
---|---|

Pages (from-to) | 365-387 |

Number of pages | 23 |

Journal | Combinatorics, Probability and Computing |

Volume | 28 |

Issue number | 3 |

Early online date | 31 Oct 2018 |

DOIs | |

Publication status | Published - 1 May 2019 |

## Keywords

- Random dyadic tilings
- Rapid mixing
- Spectral gap

## ASJC Scopus subject areas

- Theoretical Computer Science
- Applied Mathematics
- Statistics and Probability
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'Polynomial mixing of the edge-flip markov chain for unbiased dyadic tilings'. Together they form a unique fingerprint.

## Projects

- 1 Active