Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 13 (2008) > Paper 48 open journal systems 


Random perturbations of stochastic processes with unbounded variable length memory

Pierre Collet, CNRS
Antonio Galves, Universidade de Sao Paulo
Florencia Leonardi, Universidade de Sao Paulo


Abstract
We consider binary infinite order stochastic chains perturbed by a random noise. This means that at each time step, the value assumed by the chain can be randomly and independently flipped with a small fixed probability. We show that the transition probabilities of the perturbed chain are uniformly close to the corresponding transition probabilities of the original chain. As a consequence, in the case of stochastic chains with unbounded but otherwise finite variable length memory, we show that it is possible to recover the context tree of the original chain, using a suitable version of the algorithm Context, provided that the noise is small enough.


Full text: PDF

Pages: 1345-1361

Published on: August 25, 2008
Bibliography
  1. Bühlmann, Peter; Wyner, Abraham J. Variable length Markov chains. Ann. Statist. 27 (1999), no. 2, 480--513. MR1714720 (2000j:62123)
  2. Csiszár, Imre; Talata, Zsolt. Context tree estimation for not necessarily finite memory processes, via BIC and MDL. IEEE Trans. Inform. Theory 52 (2006), no. 3, 1007--1016. MR2238067 (2007a:94052)
  3. Dedecker, Jérôme; Doukhan, Paul. A new covariance inequality and applications. Stochastic Process. Appl. 106 (2003), no. 1, 63--80. MR1983043 (2004c:60111)
  4. Dedecker, Jérôme; Prieur, Clémentine. New dependence coefficients. Examples and applications to statistics. Probab. Theory Related Fields 132 (2005), no. 2, 203--236. MR2199291 (2007b:62081)
  5. Duarte, Denise; Galves, Antonio; Garcia, Nancy L. Markov approximation and consistent estimation of unbounded probabilistic suffix trees. Bull. Braz. Math. Soc. (N.S.) 37 (2006), no. 4, 581--592. MR2284889 (2008b:60185)
  6. Fernández, Roberto; Ferrari, Pablo; Galves, Antonio. Coupling, renewal and perfect simulation of chains of infinite order, 2001. Notes for a minicourse at the Vth Brazilian School of Probability.
  7. Ferrari, Fiorenzo; Wyner, Abraham. Estimation of general stationary processes by variable length Markov chains. Scand. J. Statist. 30 (2003), no. 3, 459--480. MR2002222 (2004f:62092)
  8. Galves, Antonio; Leonardi, Florencia. Exponential inequalities for empirical unbounded context trees. Progress in Probability 60 (2008), 257--270.
  9. Galves, Antonio; Löcherbach, Eva. Stochastic chains with memory of variable length. TICSP Series 38 (2008), 117--133.
  10. Galves, Antonio; Maume-Deschamps, Véronique; Schmitt, Bernard. Exponential inequalities for VLMC empirical trees. ESAIM Probab. Stat. 12 (2008), 219--229. MR2374639
  11. Rissanen, Jorma. A universal data compression system. IEEE Trans. Inform. Theory 29 (1983), no. 5, 656--664. MR0730903 (84m:94017)
  12. Ron, Dana ; Singer, Yoram ; Tishby, Naftali. The power of amnesia: Learning probabilistic automata with variable memory length. Machine Learning 25 (1996), 117--149.
  13. Willems, Frans ; Shtarkov, Yuri ; Tjalkens, Tjalling. The context-tree weighting method: basic properties. IEEE Trans. Inform. Theory IT-44 (1995), 653--664.













Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489