Let X be a stationary Z^d-process. We say that X is a factor of an i.i.d. process if there is a (deterministic and translation-invariant) way to construct a realization of X from i.i.d. variables associated to the sites of Z^d. That is, if there is an i.i.d. process Y and a measurable map F from the underlying space of Y to that of X, which commutes with translations of Z^d and satisfies that F(Y)=X in distribution. Such a factor is called finitary if, in order to determine the value of X at a given site, one only needs to look at a finite (but random) region of Y.
It is known that a phase transition (existence of multiple Gibbs states) is an obstruction for the existence of such a finitary factor. On the other hand, we show that when X is a Markov random field satisfying certain spatial mixing conditions, then X is a finitary factor of an i.i.d. process. Moreover, the coding radius has exponential tails, so that typically the value of X at a given site is determined by a small region of Y.
We give applications to models such as the Potts model, proper colorings and the hard-core model.