2009/07/13 by Sandro Gallo, Gallo, Sandro · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #60G10 (Primary) #60G99 (Secondary) #Algorithms and Data Compression #DNA and Biological Computing #FOS: Mathematics #Genomics and Phylogenetic Studies #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.0907.2150
openalex publication_date 2009/07/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a new perfect simulation algorithm for stationary chains having unbounded variable length memory. This is the class of infnite memory chains for which the family of transition probabilities is represented by a probabilistic context tree. We do not assume any continuity condition: our condition is expressed in terms of the structure of the context tree. More precisely, the length of the contexts is a deterministic function of the distance to the last occurrence of some determined string of symbols. It turns out that the resulting class of chains can be seen as a natural extension of the class of chains having a renewal string. In particular, our chains exhibit a visible regeneration scheme.