3
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Douglas Zare
    Commented Feb 26, 2010 at 13:03
  • $\begingroup$ 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. $\endgroup$
    – Stephen Shea
    Commented Feb 28, 2010 at 1:28
  • $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Mar 1, 2010 at 8:29
  • $\begingroup$ 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. $\endgroup$
    – Stephen Shea
    Commented Mar 1, 2010 at 12:27
  • $\begingroup$ If $K$ is defined on a subset of $Y$ of full measure, is that sufficient? $\endgroup$
    – Stephen Shea
    Commented Mar 1, 2010 at 12:30

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .