Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

share|improve this question
    
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

1 Answer 1

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.

Two recent papers which might interest you, if only for the references therein, are Variable length Markov chains and dynamical sources by Cénac et al. and Stochastic chains with memory of variable length by Galves and Löcherbach.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.