Document ESAIM: PS, 2008, Vol. 12, p. 219-229
DOI: 10.1051/ps:2007035
Exponential inequalities for VLMC empirical trees
Antonio Galves1, Véronique Maume-Deschamps2 and Bernard Schmitt21 Instituto de Matemática e Estatística, Universidade de São Paulo, BP 66281, 05315-970 São Paulo, Brasil; galves@ime.usp.br
2 Institut de Mathématiques de Bourgogne, BP 47870, 21078 Dijon cedex France; vmaume@u-bourgogne.fr; schmittb@u-bourgogne.fr
Received October 22, 2006. Revised June 10, 2007. Published online 23 January 2008
Abstract
A seminal paper by Rissanen, published in 1983, introduced the class
of Variable Length Markov Chains and the algorithm Context which
estimates the probabilistic tree generating the chain. Even if the
subject was recently considered in several papers, the central
question of the rate of convergence of the algorithm remained
open. This is the question we address here. We provide an
exponential upper bound for the probability of incorrect estimation
of the probabilistic tree, as a function of the size of the
sample. As a consequence we prove the almost sure consistency of the
algorithm Context. We also derive exponential upper bounds for type
I errors and for the probability of underestimation of the context tree.
The constants appearing in the bounds are all
explicit and obtained in a constructive way.
Mathematics Subject Classification. 62M05, 60G99
Key words: Variable Length Markov Chain, context tree, algorithm context, weak dependance
© EDP Sciences, SMAI 2008