Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-18T15:21:25.989Z Has data issue: false hasContentIssue false
  • English
  • Français

Chains with unbounded variable length memory: perfect simulation and a visible regeneration scheme

Part of: Stochastic processes

Published online by Cambridge University Press:  01 July 2016

Sandro Gallo
Sandro Gallo*
Affiliation:
University of Campinas
*
∗ Postal address: University of Campinas, Rua Sérgio Buarque de Holanda 651, CEP 13083-859 Campinas, São Paulo, Brazil. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We present a new perfect simulation algorithm for stationary chains having unbounded variable length memory. This is the class of infinite 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.

Keywords

Variable length memory chainprobabilistic context treeperfect simulationregeneration scheme

MSC classification

Primary: 60G10: Stationary processes
Secondary: 60G99: None of the above, but in this section
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 43 , Issue 3 , September 2011 , pp. 735 - 759
Copyright
Copyright © Applied Probability Trust 2011 

Footnotes

This work forms part of the USP Project ‘Mathematics, Computation, Language and the Brain’. Research supported by an FAPESP fellowship (grant number 2006/57387-0).

References

Berbee, H. (1987). Chains with infinite connections: uniqueness and Markov representation. Prob. Theory Relat. Fields 76, 243–253.CrossRefGoogle Scholar
Borovkov, A. A. (1998). Ergodicity and Stability of Stochastic Processes. John Wiley, Chichester.Google Scholar
Bowen, R. (2008). Equilibrium States and the Ergodic Theory of Anosov Diffeomorphisms (Lecture Notes Math. 470), 2nd revised edn. Springer, Berlin.CrossRefGoogle Scholar
Bramson, M. and Kalikow, S. (1993). Nonuniqueness in g-functions. Israel J. Math. 84, 153–160.Google Scholar
Bressaud, X., Fernández, R. and Galves, A. (1999). Decay of correlations for non-Hölderian dynamics. A coupling approach. Electron. J. Prob. 4, 19pp.CrossRefGoogle Scholar
Cénac, P., Chauvin, B., Paccaut, F. and Pouyanne, N. (2010). Variable length markov chains and dynamical sources. Preprint, Université de Bourgogne.Google Scholar
Comets, F., Fernández, R. and Ferrari, P. A. (2002). Processes with long memory: regenerative construction and perfect simulation. Ann. Appl. Prob. 12, 921–943.Google Scholar
Doeblin, W. and Fortet, R. (1937). Sur des chaıcirc;nes à liaisons complètes. Bull. Soc. Math. France 65, 132–148.CrossRefGoogle Scholar
Feller, W. (1968). An Introduction to Probability Theory and Its Applications, Vol. I, 3rd edn. John Wiley, New York.Google Scholar
Fernández, R., Ferrari, P. A. and Galves, A. (2001). Coupling, Renewal and Perfect Simulations of Chains of Infinite Order. Lecture Notes for the Vth Brazilian School of Probability.Google Scholar
Foss, S. and Konstantopoulos, T. (2003). Extended renovation theory and limit theorems for stochastic ordered graphs. Markov Process. Relat. Fields 9, 413–468.Google Scholar
Foss, S. G. and Tweedie, R. L. (1998). Perfect simulation and backward coupling. Commun. Statist. Stoch. Models 14, 187–203.Google Scholar
Galves, A. and Löcherbarch, E. (2008). Stochastic chains with memory of variable length. TICSP series 38, 117–133.Google Scholar
Harris, T. E. (1955). On chains of infinite order. Pacific J. Math. 5, 707–724.CrossRefGoogle Scholar
Iosifescu, M. and Grigorescu, Ş. (1990). Dependence with Complete Connections and Its Applications (Camb. Tracks Math. 96). Cambridge University Press.Google Scholar
Johansson, A. and Öberg, A. (2003). Square summability of variations of g-functions and uniqueness of g-measures. Math. Res. Lett. 10, 587–601.CrossRefGoogle Scholar
Kalikow, S. (1990). Random Markov processes and uniform martingales. Israel J. Math. 71, 33–54.Google Scholar
Lalley, S. P. (1986). Regenerative representation for one-dimensional Gibbs states. Ann. Prob. 14, 1262–1271.Google Scholar
Onicescu, O. and Mihoc, G. (1935). Sur les chaînes de variables statistiques. Bull. Sci. Math 59, 174–192.Google Scholar
Propp, J. G. and Wilson, D. B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures and Algorithms 9, 223–252.3.0.CO;2-O>CrossRefGoogle Scholar
Rissanen, J. (1983). A universal data compression system. IEEE Trans. Inform. Theory 29, 656–664.CrossRefGoogle Scholar