Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: Markov Approximation And Consistent Estimation Of Unbounded Probabilistic Suffix Trees
Author: Duarte D.
Galves A.
Garcia N.L.
Abstract: We consider infinite order chains whose transition probabilities depend on a finite suffix of the past. These suffixes are of variable length and the set of the lengths of all suffix is unbounded. We assume that the probability transitions for each of these suffixes are continuous with exponential decay rate. For these chains, we prove the weak consistency of a modification of Rissanen's algorithm Context which estimates the length of the suffix needed to predict the next symbol, given a finite sample. This generalizes to the unbounded case the original result proved for variable length Markov chains in the seminal paper Rissanen (1983). Our basic tool is the canonical Markov approximation which enables to approximate the chain of infinite order by a sequence of variable length Markov chains of increasing order. Our proof is constructive and we present an explicit decreasing upper bound for the probability of wrong estimation of the length of the current suffix. © Springer-Verlag Berlin Heidelberg 2006.
Rights: fechado
Identifier DOI: 10.1007/s00574-006-0029-7
Date Issue: 2006
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-33845799190.pdf109.26 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.