Coding Markov chains from the past

It is shown that a mixing Markov chain is a unilateral or one-sided factor of every ergodic process of equal or greater entropy. This extends the work of Sinai, who showed that the result holds for independent processes, and the work of Ornstein and Weiss, who showed that the result holds for mixing Markov chains in which all transition probabilities are positive. The proof exploits the Rothstein-Burton joinings-space formulation of Ornstein’s isomorphism theory, and uses a random coding argument. Partially supported by an NSF Graduate Fellowship, an NSF Postdoctoral Fellowship, and NSF Grant # DMS 84-03182 during the writing of this article.