# Finitarily Markovian Finite Factors of Bernoulli Schemes

By processes, I mean discrete, stationary stochastic processes, that is $(X,\mathcal{U},\mu,T)$ where $X$ is the set of doubly infinite sequences of some alphabet $A$, $\mathcal{U}$ is the $\sigma$-algebra generated by the coordinates, $\mu$ is a probability measure on $(X,\mathcal{U})$, and $T$ is the left shift by one.

Finitarily Markovovian processes (as defined by Morvai and Weiss in On Estimating the Memory for Finitarily Markovian Processes) are those processes $\{X_n\}_{n=-\infty}^{\infty}$ for which there is a finite $K$ $(K=K(\{X_n\}_{n=-\infty}^0))$ such that the conditional distribution of $X_1$ given the entire past is equal to the conditional distribution of $X_1$ given only $\{X_n\}_{n=1-K}^0$.

First, can anyone suggest good literature on the topic of when a hidden Markov process is finitarily Markov?

Specifically, I would like to know when a finite factor (also called $k$-block factor or simply block factor) of a Bernoulli scheme is finitarily Markovian?

The following is an example of a 2 block factor of a Bernoulli scheme which is not finitarily Markovian.

Let $X=\{0,1\}^{\mathbb{Z}}$ with measure $\mu=(1/3,2/3)^{\mathbb{Z}}$. Define a map $\phi:X \to Y$ where $(\phi(x))_i=(x_i+x_{i+1})$mod $2$.

• Finitarily Markovian seems like a really strong property, far stronger than something like k-dependence. What examples do you have other than from choosing K and a transition distribution for each history of length K? – Douglas Zare Feb 26 '10 at 13:03
• Douglas, all finite factors are k-dependent for some k. Not all finite factors are finitarily Markovian. However, I claim (without much proof) that "most" finite factors are finitarily Markovian. For an example, consider altering the above defined $\phi$ so that the 2-block 00 maps to 0 and 10, 01, and 00 map to 1. 0 is then a renewal state in $Y$ and thus $Y$ is finitarily Markovian. – Stephen Shea Feb 28 '10 at 1:28
• That second example does not appear finitarily Markovian to me. For any k, it looks like conditioning on k 1s in a row is different from conditioning on k+1 1s in a row. – Douglas Zare Mar 1 '10 at 8:29
• Douglas, you are correct. In this example, the function $K$ looks back until the last occurrence of a 0. Unless I am misinterpreting the definition, one should be allowed to choose $K$ in such a manner. – Stephen Shea Mar 1 '10 at 12:27
• If $K$ is defined on a subset of $Y$ of full measure, is that sufficient? – Stephen Shea Mar 1 '10 at 12:30

This is not to provide an answer per se but to mention that indeed $K$ is an almost surely finite random variable (otherwise the resulting process is an ordinary Markov chain of a given order). This class of models, introduced by Jorma Rissanen in 1983 in his paper A universal data compression system, is known under several different names: context models, VLMC (variable length Markov chains), chains of variable order, chains with memory of variable length, etc.