Existence and Non-Existence of Finitary Codings for a Class of Random Fields.211 Probability, Networks and Algorithms

摘要

We study the existence of finitary codings (also called finitary homomorphisms or211u001efinitary factor maps) from a finite-valued i.i.d. process to certain random 211u001efields. For Markov random fields we show, using ideas of Marton and Shields, that 211u001ethe presence of a phase transition is an obstruction for the existence of the 211u001eabove coding: this yields a large class of Bernoulli shifts for which no such 211u001ecoding exists. Conversely, we show that for the stationary distribution of a 211u001emonotone exponentially ergodic probabilistic cellular automaton such a coding 211u001edoes exist. The construction of the coding is partially inspired by the Propp-211u001eWilson algorithm for exact simulation.