Kybernetika 56 no. 4, 601-616, 2020

Universal rates for estimating the residual waiting time in an intermittent way

Gusztáv Morvai and Benjamin WeissDOI: 10.14736/kyb-2020-4-0601

Abstract:

A simple renewal process is a stochastic process $\{X_n\}$ taking values in $\{0,1\}$ where the lengths of the runs of $1$'s between successive zeros are independent and identically distributed. After observing ${X_0, X_1, \ldots X_n}$ one would like to estimate the time remaining until the next occurrence of a zero, and the problem of universal estimators is to do so without prior knowledge of the distribution of the process. We give some universal estimates with rates for the expected time to renewal as well as for the conditional distribution of the time to renewal.

Keywords:

renewal theory, statistical learning, statistical inference, prediction methods

Classification:

60G25, 60K05

paper.pdf

References:

  1. P. Algoet: The strong low of large numbers for sequential decisions under uncertainity. IEEE Trans. Inform. Theory 40 (1994), 609-634.   DOI:10.1109/18.335876
  2. B. von Bahr and C. G. Esseen: Inequalities for the $r$th absolute moment of a sum of random variables, $1\leq r \leq 2$. Ann. Math. Statist. 36 (1965), 299-303.   DOI:10.1214/aoms/1177700291
  3. L. Denby and Y. Vardi: A short-cut method for estimation in renewal processes. Technometrics 27 (1985), 4, 361-373.   DOI:10.1080/00401706.1985.10488075
  4. W. Feller: An Introduction to Probability Theory and its Applications Vol. I. Third edition. John Wiley and Sons, Inc., New York - London - Sydney 1968.   CrossRef
  5. S. Ghahramani: Fundamentals of Probability with Stochastic Processes. Third edition. Pearson Prentice Hall, Upper Saddle River NJ, 2005.   CrossRef
  6. L. Györfi and G. Ottucsák: Sequential prediction of unbounded stationary time series. IEEE Trans. Inform. Theory 53 (2007), 1866-1872.   DOI:10.1109/tit.2007.894660
  7. S. Khudanpur and P. Narayan: Order estimation for a special class of hidden Markov sources and binary renewal processses. IEEE Trans. Inform. Theory 48 (2002), 1704-1713.   DOI:10.1109/tit.2002.1003850
  8. J. Marcinkiewicz and A. Zygmund: Sur les foncions independantes. Fund. Math. 28 (1937), 60-90.   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 2003, pp. 207-215.   CrossRef
  10. G. Morvai and B. Weiss: Forecasting for stationary binary time series. Acta Applic. Math. 79 (2003), 25-34.   DOI:10.1023/a:1025862222287
  11. 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
  12. G. Morvai and B. Weiss: On sequential estimation and prediction for discrete time series. Stoch. Dynam. 7 (2007), 4, 417-437.   DOI:10.1142/s021949370700213x
  13. G. Morvai and B. Weiss: On universal estimates for binary renewal processes. Ann. Appl. Prob. 18 (2008), 5, 1970-1992.   DOI:10.1214/07-aap512
  14. G. Morvai and B. Weiss: Estimating the residual waiting time for binary stationary time series. In: ITW 2009, IEEE Information Theory Workshop on Networking and Information Theory, 2009 pp. 67-70.   DOI:10.1109/itwnit.2009.5158543
  15. G. Morvai and B. Weiss: Inferring the residual waiting time for binary stationary time series. Kybernetika 50 (2014), 6, 869-882.   DOI:10.14736/kyb-2014-6-0869
  16. G. Morvai and B. Weiss: A versatile scheme for predicting renewal times. Kybernetika 52 (2016), 3, 348-358.   DOI:10.14736/kyb-2016-3-0348
  17. A. B. Nobel: On optimal sequential prediction for general processes. IEEE Trans. Inform. Theory 49 (2003), 83-98.   DOI:10.1109/tit.2002.806141
  18. E. A. Peña, R. Strawderman and M. Hollander: Nonparametric estimation with recurrent event data. J. Amer. Statist. Assoc. 96 (2001), 456, 1299-1315.   DOI:10.1198/016214501753381922
  19. V. V. Petrov: Limit Theorems of Probability Theory. Clarendon Press, Oxford 1995.   DOI:10.1017/s001309150002335x
  20. B. Y. Ryabko: Prediction of random sequences and universal coding. Probl. Inform. Trans. 24 (1988), 87-96.   CrossRef
  21. P. C. Shields: The Ergodic Theory of Discrete Sample Paths. Graduate Studies in Mathematics 13, American Mathematical Society, Providence 1996.   DOI:10.1090/gsm/013
  22. A. N. Shiryayev: Probability. Second edition. Springer-Verlag, New York 1996.   CrossRef
  23. H. Takahashi: Computational limits to nonparametric estimation for ergodic processes. IEEE Trans. Inform. Theory 57 (2011), 10, 6995-6999.   DOI:10.1109/tit.2011.2165791
  24. Y. Vardi: Nonparametric estimation in renewal processes. Ann. Statist. (1982), 772-785.   DOI:10.1214/aos/1176345870