We study the existence of finitary codings (also called finitary
homomorphisms or finitary factor maps) from a finite-valued i.i.d. process to
certain random fields. For Markov random fields we show, using ideas of Marton
and Shields, that the presence of a phase transition is an obstruction for the
existence of the above coding; this yields a large class of Bernoulli shifts
for which no such coding exists.
¶ Conversely, we show that, for the stationary distribution of a
monotone exponentially ergodic probabilistic cellular automaton, such a coding
does exist. The construction of the coding is partially inspired by the
Propp–Wilson algorithm for exact simulation.
¶ In particular, combining our results with a theorem of Martinelli
and Olivieri, we obtain the fact that for the plus state for the ferromagnetic
Ising model on $\mathbf{Z}^d, d \geq 2$, there is such a coding when the
interaction parameter is below its critical value and there is no such coding
when the interaction parameter is above its critical value.