×

Context trees, variable length Markov chains and dynamical sources. (English) Zbl 1253.60079

Donati-Martin, Catherine (ed.) et al., Séminaire de Probabilités XLIV. Papers based on the presentations at the 44th séminaire de probabilités, Dijon, France, June 2010. Berlin: Springer (ISBN 978-3-642-27460-2/pbk; 978-3-642-27461-9/ebook). Lecture Notes in Mathematics 2046, 1-39 (2012).
An infinite random sequence of letters from a finite alphabet A is a variable length Markov chain (VLMC) if the transition probabilities to the next letter depend on the present letter together with a variable number of immediately preceding letters. The subsequence of relevant suffix letters from past and present is called a context, and different contexts are given by the leaves of a context tree. Every stationary VLMC can be obtained by a probabilistic dynamical source defined by a random variable \(x\) on the unit interval \([0,1]\), a suitable transformation \(T\) from \([0,1]\) to \([0,1]\), and a coding function from \([0,1]\) to A. Iterations \(x, T(x), T(T(x)),\dots\) are coded to letters in the VLMC. Two special cases of context trees are considered, and necessary and sufficient conditions are given for the existence and uniqueness of a stationary VLMC.
For the entire collection see [Zbl 1244.60005].

MSC:

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

References:

[1] Abadi, M.; Galves, A., Inequalities for the occurrence times of rare events in mixing processes. The state of the art, Markov Proc. Relat. Field., 7, 1, 97-112 (2001) · Zbl 0973.60035
[2] M. Abadi, B. Saussol, Stochastic processes and their applications. 121(2), 314-323 · Zbl 1222.60032
[3] P. Billingsley, Probability and Measure, 3rd edn. Wiley Series in Probability and Mathematical Statistics (Wiley, New York, 1995) · Zbl 0822.60002
[4] Blom, G.; Thorburn, D., How many random digits are required until given sequences are obtained?, J. Appl. Probab., 19, 518-531 (1982) · Zbl 0493.60071
[5] Bühlmann, P.; Wyner, A. J., Variable length markov chains, Ann. Statist., 27, 2, 480-513 (1999) · Zbl 0983.62048
[6] Clément, J.; Flajolet, P.; Vallee, B., Dynamical sources in information theory: Analysis of general tries, Algorithmica, 29, 307-369 (2001) · Zbl 1035.68039
[7] Comets, F.; Fernandez, R.; Ferrari, P., Processes with long memory: Regenerative construction and perfect simulation, Ann. Appl. Prob., 12, 3, 921-943 (2002) · Zbl 1016.60061
[8] P. Flajolet, M. Roux, B. Vallée, Digital trees and memoryless sources: From arithmetics to analysis. DMTCS Proc. AM, 233-260 (2010) · Zbl 1355.68062
[9] Fu, J. C., Bounds for reliability of large consecutive-k-out-of-n : f system, IEEE Trans. Reliab., 35, 316-319 (1986) · Zbl 0597.90036
[10] Fu, J. C.; Koutras, M. V., Distribution theory of runs: A markov chain approach, J. Amer. Statist. Soc., 89, 1050-1058 (1994) · Zbl 0806.60011
[11] S. Gallo, N. Garcia, Perfect simulation for stochastic chains of infinite memory: Relaxing the continuity assumptions. pp. 1-20 (2010) [arXiv:1105.5459v1]
[12] Galves, A.; Löcherbach, E., Stochastic chains with memory of variable length, TICSP Series, 38, 117-133 (2008)
[13] Gerber, H.; Li, S., The occurrence of sequence patterns in repeated experiments and hitting times in a markov chain, Stoch. Process. Their Appl., 11, 101-108 (1981) · Zbl 0449.60050
[14] Harris, T. E., On chains of infinite order, Pac. J. Math., 5, 707-724 (1955) · Zbl 0066.11402
[15] Jacquet, P.; Szpankowski, W., Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach, J. Combin. Theor. A., 66, 237-269 (1994) · Zbl 0802.68097
[16] M.V. Koutras, Waiting Times and Number of Appearances of Events in a Sequence of Discrete Random Variables. Advances in Combinatorial Methods and Applications to Probability and Statistics, Stat. Ind. Technol., (Birkhäuser Boston, Boston, 1997), pp. 363-384 · Zbl 0884.60063
[17] Lambert, A.; Siboni, S.; Vaienti, S., Statistical properties of a nonuniformly hyperbolic map of the interval, J. Stat. Phys., 72, 5-6, 1305-1330 (1993) · Zbl 1101.37309
[18] Li, S.-Y. R., A martingale approach to the study of occurrence of sequence patterns in repeated experiments, Ann. Probab., 8, 6, 1171-1176 (1980) · Zbl 0447.60006
[19] Pozdnyakov, V.; Glaz, J.; Kulldorff, M.; Steele, J. M., A martingale approach to scan statistics, Ann. Inst. Statist. Math., 57, 1, 21-37 (2005) · Zbl 1082.62015
[20] Régnier, M., A unified approach to word occurrence probabilities, Discrete Appl. Math., 104, 259-280 (2000) · Zbl 0987.92017
[21] Reinert, G.; Schbath, S.; Waterman, M. S., Probabilistic and statistical properties of words: An overview, J. Comput. Biol., 7, 1-2, 1-46 (2000)
[22] D. Revuz, Markov Chains. (North-Holland Mathematical Library, Amsterdam, 1984) · Zbl 0539.60073
[23] Rissanen, J., A universal data compression system, IEEE Trans. Inform. Theor., 29, 5, 656-664 (1983) · Zbl 0521.94010
[24] Robin, S.; Daudin, J. J., Exact distribution of word occurrences in a random sequence of letters, J. Appl. Prob., 36, 179-193 (1999) · Zbl 0945.60008
[25] Stefanov, V.; Pakes, A. G., Explicit distributional results in pattern formation, Ann. Appl. Probab., 7, 666-678 (1997) · Zbl 0893.60005
[26] Szpankowski, W., A generalized suffix tree and its (un)expected asymptotic behaviors, SIAM J. Comput., 22, 6, 1176-1198 (1993) · Zbl 0799.68050
[27] Wang, X-J., Statistical physics of temporal intermittency, Phys. Rev. A, 40, 11, 6647-6661 (1989)
[28] D. Williams, Probability with Martingales. Cambridge Mathematical Textbooks (Cambridge University Press, Cambridge, 1991) · Zbl 0722.60001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.