Mallows permutations and finite dependence
Accepted version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Abstract
We use the Mallows permutation model to construct a new family of stationary finitely dependent proper colorings of the integers. We prove that these colorings can be expressed as finitary factors of i.i.d. processes with finite mean coding radii. They are the first colorings known to have these properties. Moreover, we prove that the coding radii have exponential tails, and that the colorings can also be expressed as functions of countable-state Markov chains. We deduce analogous existence statements concerning shifts of finite type and higher-dimensional colorings.
Description
Keywords
Proper coloring, finite dependence, random permutation
Journal Title
Annals of Probability
Conference Name
Journal ISSN
0091-1798
2168-894X
2168-894X
Volume Title
48
Publisher
Institute of Mathematical Statistics
Publisher DOI
Rights
All rights reserved
Sponsorship
Microsoft Research