Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 2020 | Submitted
Journal Article Open

Mallows permutations and finite dependence


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.

Additional Information

© 2020 Institute of Mathematical Statistics. Received: 1 June 2017; Revised: 1 January 2019; Published: January 2020. First available in Project Euclid: 25 March 2020. AL and TH were supported by internships at Microsoft Research while portions of this work were completed. TH was also supported by a Microsoft Research PhD fellowship.

Attached Files

Submitted - 1706.09526.pdf


Files (849.9 kB)
Name Size Download all
849.9 kB Preview Download

Additional details

August 19, 2023
October 23, 2023