Kybernetika 57 no. 4, 628-646, 2021

Intermittent estimation for finite alphabet finitarily Markovian processes with exponential tails

Gusztáv Morvai and Benjamin WeissDOI: 10.14736/kyb-2021-4-0628


We give some estimation schemes for the conditional distribution and conditional expectation of the the next output following the observation of the first $n$ outputs of a stationary process where the random variables may take finitely many possible values. Our schemes are universal in the class of finitarily Markovian processes that have an exponential rate for the tail of the look back time distribution. In addition explicit rates are given. A necessary restriction is that the scheme proposes an estimate only at certain stopping times, but these have density one so that one rarely fails to give an estimate.


stationary processes, nonparametric estimation


62G05, 60G25, 60G10


  1. P. Algoet: The strong law of large numbers for sequential decisions under uncertainty. IEEE Trans. Inform. Theory 40 (1994), 609-633.   DOI:10.1109/18.335876
  2. P. Algoet: Universal schemes for learning the best nonlinear predictor given the infinite past and side information. IEEE Trans. Inform. Theory 45 (1999), 1165-1185.   DOI:10.1109/18.761258
  3. D. H. Bailey: Sequential Schemes for Classifying and Predicting Ergodic Processes. Ph.D. Thesis, Stanford University, 1976.   CrossRef
  4. I. Csiszár and Zs. Talata: Context tree estimation for not necessarily finite memory processes via BIC and MDL. IEEE Trans. Inform. Theory 52 (2006), 3, 1007-1016.   DOI:10.1109/TIT.2005.864431
  5. L. Györfi, G. Morvai and S. Yakowitz: Limits to consistent on-line forecasting for ergodic time series. IEEE Trans. Inform. Theory 44 (1998), 886-892.   DOI:10.1109/18.661540
  6. W. Hoeffding: Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 (1963), 13-30.   CrossRef
  7. S. Kalikow, Y. Katznelson and B. Weiss: Finitarily deterministic generators for zero entropy systems. Israel J. Math. 79 (1992), 33-45.   DOI:10.1007/BF02764801
  8. Ph. T. Maker: The ergodic theorem for a sequence of functions. Duke Math. J. 6 (1940), 27-30.   CrossRef
  9. G. Morvai: Guessing the output of a stationary binary time series. In: Foundations of Statistical Inference (Y. Haitovsky, H. R.Lerche, and Y. Ritov, eds.), Physika-Verlag, pp. 207-215, 2003.   CrossRef
  10. G. Morvai, S. Yakowitz and P. Algoet: Weakly convergent nonparametric forecasting of stationary time series. IEEE Trans. Inform. Theory 43 (1997), 483-498.   DOI:10.1109/18.556107
  11. G. Morvai and B. Weiss: Forecasting for stationary binary time series. Acta Appl. Math. 79 (2003), 25-34.   DOI:10.1023/A:1025862222287
  12. G. Morvai and B. Weiss: Intermittent estimation of stationary time series. Test 13 (2004), 525-542.   DOI:10.1007/BF02595785
  13. G. Morvai and B. Weiss: Inferring the conditional mean. Theory Stochast. Process. 11 (2005), 1-2, 112-120.   CrossRef
  14. G. Morvai and B. Weiss: Prediction for discrete time series. Probab. Theory Related Fields 132 (2005), 1-12.   DOI:10.1007/s00440-004-0386-3
  15. G. Morvai and B. Weiss: Limitations on intermittent forecasting. Statist. Probab. Lett. 72 (2005), 285-290.   DOI:10.1016/j.spl.2004.12.016
  16. G. Morvai and B. Weiss: On classifying processes. Bernoulli 11 (2005), 523-532.   DOI:10.3150/bj/1120591187
  17. G. Morvai and B. Weiss: Order estimation of Markov chains. IEEE Trans. Inform. Theory 51 (2005), 1496-1497.   DOI:10.1109/TIT.2005.844093
  18. G. Morvai and B. Weiss: Forward estimation for ergodic time series. Ann. I. H. Poincaré Probab. Statist. 41 (2005), 859-870.   DOI:10.1016/j.anihpb.2004.07.002
  19. G. Morvai and B. Weiss: On estimating the memory for finitarily Markovian processes. Ann. I. H. Poincaré PR 43 (2007), 15-30.   DOI:10.1016/j.anihpb.2005.11.001
  20. G. Morvai and B. Weiss: On sequential estimation and prediction for discrete time series. Stoch. Dyn. 7 (2007), 4, 417-437.   DOI:10.1142/s021949370700213x
  21. G. Morvai and B. Weiss: Estimating the lengths of memory words. IEEE Trans. Inform. Theory 54 (2008), 8, 3804-3807.   DOI:10.1109/TIT.2008.926316
  22. G. Morvai and B. Weiss: On universal estimates for binary renewal processes. Annals Appl. Probab. 18 (2008), 5, 1970-1992.   DOI:10.1214/07-aap512
  23. G. Morvai and B. Weiss: Estimating the residual waiting time for binary stationary time series. Proc. ITW2009, Volos 2009, pp. 67-70.   CrossRef
  24. G. Morvai and B. Weiss: A note on prediction for discrete time series. Kybernetika 48 (2012), 4, 809-823.   CrossRef
  25. G. Morvai and B. Weiss: Universal tests for memory words. IEEE Trans. Inform. Theory 59 (2013), 6873-6879.   DOI:10.1109/TIT.2013.2268913
  26. G. Morvai and B. Weiss: Inferring the residual waiting time for binary stationary time series. Kybernetika 50 (2014), 869-882.   DOI:10.14736/kyb-2014-6-0869
  27. G. Morvai and B. Weiss: A versatile scheme for predicting renewal times. Kybernetika 52 (2016), 348-358.   DOI:10.14736/kyb-2016-3-0348
  28. G. Morvai and B. Weiss: Universal rates for estimating the residual waiting time in an intermittent way. Kybernetika 56, (2020), 4, 601-616.   DOI:10.14736/kyb-2020-4-0601
  29. G. Morvai and B. Weiss: On universal algorithms for classifying and predicting stationary processes. Probab. Surveys 18 (2021), 77-131.   CrossRef
  30. G. Morvai and B. Weiss: Consistency, integrability and asymptotic normality for some intermittent estimators. ALEA, Lat. Am. J. Probab. Math. Stat. 18 (2021), 1643-1667.   DOI:10.30757/ALEA.v18-60
  31. B. Ya. Ryabko: Prediction of random sequences and universal coding. Problems Inform. Trans. 24 (1988), 87-96.   DOI:10.1080/10256018808623911
  32. D. Ryabko: Asymptotic Nonparametric Statistical Analysis of Stationary Time Series. Springer, Cham 2019.   CrossRef
  33. P. C. Shields: The Ergodic Theory of Discrete Sample Paths. In: Graduate Studies in Mathematics. American Mathematical Society 13, Providence 1996.   CrossRef
  34. J. Suzuki: Universal prediction and universal coding. Systems Computers Japan 34 (2003), 6, 1-11.   DOI:10.1002/scj.10357
  35. H. Takahashi: Computational limits to nonparametric estimation for ergodic processes. IEEE Trans. Inform. Theory 57 (2011), 6995-6999.   DOI:10.1109/TIT.2011.2165791