English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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

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