One-dimensional Markov random fields, Markov chains and topological Markov fields

A one-dimensional Markov chain is defined by a one-sided, directional conditional independence property, and a process is Markov in the forward direction if and only if it is Markov in the backward direction. In two and higher dimensions, this property is replaced with a conditional independence property that is not associated with a particular direction. This leads to the notion of a Markov random field (MRF). Of course, the definition of MRF makes sense in one dimension as well (see Section 2), but here the conditional independence is a two-sided property, and this is not the same as the Markov chain property. It is well known that any onedimensional Markov chain is an MRF. However, the converse is not true: there are counter-examples for non-stationary, finite-valued processes and for stationary countable-valued processes. The converse does hold (and this is well known) for finite-valued stationary MRF’s that either have full support or satisfy a certain mixing condition. In this paper we show that any one-dimensional stationary, finite-valued MRF is a Markov chain, without any mixing condition or condition on the support. Our proof makes use of two properties of the support X of a finite-valued stationary MRF: 1) X is non-wandering (this is a property of the support of any finite-valued stationary process) and 2) X is a topological Markov field (TMF) (defined in Section 2). The latter is a new property that sits in between the classes of shifts of finite type and sofic shifts, which are well-known objects of study in symbolic dynamics [5]. Here, we develop the TMF property in one dimension, and we will develop this property in higher dimensions in a future paper. While we are mainly interested in discrete-time finite-valued stationary MRF’s, in Section 5 we also consider continuous-time, finite-valued stationary MRF’s, and show that these are (continuous-time) Markov chains as well.