The present paper investigates non-asymptotic properties of two popular
procedures of context tree (or Variable Length Markov Chains) estimation:
Rissanen's algorithm Context and the Penalized Maximum Likelihood criterion.
First showing how they are related, we prove finite horizon bounds for the
probability of over- and under-estimation. Concerning overestimation, no
boundedness or loss-of-memory conditions are required: the proof relies on new
deviation inequalities for empirical probabilities of independent interest. The
underestimation properties rely on loss-of-memory and separation conditions of
the process.
These results improve and generalize the bounds obtained previously. Context
tree models have been introduced by Rissanen as a parsimonious generalization
of Markov models. Since then, they have been widely used in applied probability
and statistics.