Context trees, variable length Markov chains and dynamical sources

DOI10.1007/978-3-642-27461-9_1zbMATH Open1253.60079arXiv1007.2986OpenAlexW195770915WikidataQ105584935 ScholiaQ105584935MaRDI QIDQ2906153FDOQ2906153

Authors: Peggy Cénac, Brigitte Chauvin, Frédéric Paccaut, Nicolas Pouyanne 

Publication date: 29 August 2012

Published in: Lecture Notes in Mathematics (Search for Journal in Brave)

Abstract: Infinite random sequences of letters can be viewed as stochastic chains or as strings produced by a source, in the sense of information theory. The relationship between Variable Length Markov Chains (VLMC) and probabilistic dynamical sources is studied. We establish a probabilistic frame for context trees and VLMC and we prove that any VLMC is a dynamical source for which we explicitly build the mapping. On two examples, the ``comb and the ``bamboo blossom, we find a necessary and sufficient condition for the existence and the unicity of a stationary probability measure for the VLMC. These two examples are detailed in order to provide the associated Dirichlet series as well as the generating functions of word occurrences.

Full work available at URL: https://arxiv.org/abs/1007.2986

Recommendations

• Variable length memory chains: characterization of stationary probability measures
• Variable length Markov chains
• Model selection for variable length Markov chains and tuning the context algorithm
• scientific article; zbMATH DE number 2159642
• Exponential inequalities for VLMC empirical trees

zbMATH Keywords

variable length Markov chainsdynamical systems of the interval Dirichlet seriesoccurrences of wordsprobabilistic dynamical source

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Prefix, length-variable, comma-free codes (94A45) Stationary stochastic processes (60G10) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Dynamical systems involving maps of the interval (37E05)

Cites Work

• Title not available (Why is that?)
• Probability with Martingales
• A unified approach to word occurrence probabilities
• Title not available (Why is that?)
• Distribution Theory of Runs: A Markov Chain Approach
• Dynamical sources in information theory: A general analysis of trie structures
• Processes with long memory: Regenerative construction and perfect simulation
• Hitting and returning to rare events for all alpha-mixing processes
• A martingale approach to scan statistics
• Inequalities for the occurrence times of rare events in mixing processes. The state of the art
• A universal data compression system
• On chains of infinite order
• Explicit distributional results in pattern formation
• Digital trees and memoryless sources: from arithmetics to analysis
• Title not available (Why is that?)
• Exact distribution of word occurrences in a random sequence of letters
• Variable length Markov chains
• The occurrence of sequence patterns in repeated experiments and hitting times in a Markov chain
• How many random digits are required until given sequences are obtained?
• Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach
• A martingale approach to the study of occurrence of sequence patterns in repeated experiments
• A Generalized Suffix Tree and Its (Un)Expected Asymptotic Behaviors
• Bounds for Reliability of Large Consecutive-K-out-of-N:F Systems with Unequal Component Reliability
• Statistical properties of a nonuniformly hyperbolic map of the interval

Cited In (16)

• Attractive regular stochastic chains: perfect simulation and phase transition
• Title not available (Why is that?)
• Limit theorems for chains with unbounded variable length memory which satisfy Cramer condition
• Probability and algorithmics: a focus on some recent developments
• Uncommon suffix tries
• Persistent random walks. I. Recurrence versus transience
• Recurrence of multidimensional persistent random walks. Fourier and series criteria
• Model selection for variable length Markov chains and tuning the context algorithm
• Estimation of General Stationary Processes by Variable Length Markov Chains
• Context Tree Estimation in Variable Length Hidden Markov Models
• Local limit theorem for a Markov additive process on with a null recurrent internal Markov chain
• Variable length memory chains: characterization of stationary probability measures
• Variable length Markov chain with exogenous covariates
• Non-regular g-measures and variable length memory chains
• Chains with unbounded variable length memory: perfect simulation and a visible regeneration scheme
• Variable length Markov chains

This page was built for publication: Context trees, variable length Markov chains and dynamical sources

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2906153)