# zbMATH — the first resource for mathematics

On universal estimates for binary renewal processes. (English) Zbl 1158.62053
In many applications the occurrences of a zero, which represent the failure times of some system which is renewed after each failure, are of importance and so the problem arises of estimating when the next failure will occur. The classical binary 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.
The authors of this paper investigate the possibility of giving a universal estimator at time $$n$$ for the residual waiting time to the next zero in the binary renewal process $$\{X_n\}$$. Let $$\{p_k\}_{k=0}^{\infty}$$ be the conditional probability that a run of $$k$$ 1’s follows a given 0 event. This distribution describes completely the renewal process as a two-sided stationary process. If the distribution of the process is known, then after observing $$X_{0},X_{1},\ldots,X_n$$ one may give a consistent estimator for the expected value of residual waiting time to the occurrence of the next zero as $\mu_L={\sum_{k=L}^{\infty} (k-L)p_k}/ {\sum_{k=L}^{\infty}p_k}$ if there is at least one zero among the values of $$X_{0},X_{1},\ldots,X_n$$, and the last zero occurs at the moment $$X_{n-L}=0$$. This $$L$$ is denoted by $$\tau(X_{0},X_{1},\ldots,X_n)$$. From the stationarity it follows that $$P(\tau=L)$$ is proportional to $$\sum_{k=L}^{\infty}p_k$$.
For the estimator itself it is most natural to use the empirical distribution observed in the data segment $$X_{0},X_{1},\ldots,X_n$$. However, if there is an insufficient number of occurrences of 1-blocks of length at least $$\tau(X_{0},X_{1},\ldots,X_n)$$, then we do not expect the empirical distribution to be close to the true distribution. For this reason estimates only along stopping times $$\lambda_1,\lambda_2,\dots$$ are considered and the main positive result is that there is a sequence of universally defined stopping times $$\lambda_n$$ with density 1 and estimators $$h_n(X_{0},X_{1},\ldots,X_n)$$ which are almost surely converging to $$\mu_{\tau}(X_{0},X_{1},\ldots,X_{\lambda_n})$$. Estimators $$\hat{p}_l(X_{0},X_{1},\ldots,X_{\lambda_n})$$ are also defined which are almost surely converging in the variation metric to the conditional distribution of the residual waiting time. A variety of different estimates are proposed, including universal estimates for the expected time to renewal as well as estimates for the conditional distribution of the time to renewal.

##### MSC:
 62M05 Markov processes: estimation; hidden Markov models 60K05 Renewal theory 62M20 Inference from stochastic processes and prediction 62G30 Order statistics; empirical distribution functions 60G25 Prediction theory (aspects of stochastic processes) 62L15 Optimal stopping in statistics 60K25 Queueing theory (aspects of probability theory)
##### Keywords:
binary renewal process; renewal theory; estimate; prediction
Full Text:
##### References:
  Algoet, P. (1992). Universal schemes for prediction, gambling and portfolio selection. Ann. Probab. 20 901-941. · Zbl 0758.90006  Algoet, P. H. (1994). The strong law of large numbers for sequential decisions under uncertainty. IEEE Trans. Inform. Theory 40 609-633. · Zbl 0827.62077  Algoet, P. (1999). Universal schemes for learning the best nonlinear predictor given the infinite past and side information. IEEE Trans. Inform. Theory 45 1165-1185. · Zbl 0959.62078  Bailey, D. H. (1976). Sequential schemes for classifying and predicting ergodic processes. Ph.D. thesis, Stanford Univ.  von Bahr, B. and Esseen, C.-G. (1965). Inequalities for the r th absolute moment of a sum of random variables, 1\leq r \leq 2. Ann. Math. Statist. 36 299-303. · Zbl 0134.36902  Cover, T. M. (1976). Open problems in information theory. In Proceedings of the IEEE-USSR Joint Workshop in Information Theory ( Moscow , 1975) 35-36. IEEE, New York.  Feller, W. (1968). An Introduction to Probability Theory and Its Applications . I , 3rd ed. Wiley, New York. · Zbl 0155.23101  Ghahramani, S. (2005). Fundamentals of Probability with Stochastic Processes , 3rd ed. Prentice Hall, Upper Saddle River, NJ. · Zbl 1336.60001  Györfi, L., Morvai, G. and Yakowitz, S. J. (1998). Limits to consistent on-line forecasting for ergodic time series. IEEE Trans. Inform. Theory 44 886-892. · Zbl 0899.62122  Györfi, L., Lugosi, G. and Morvai, G. (1999). A simple randomized algorithm for sequential prediction of ergodic time series. IEEE Trans. Inform. Theory 45 2642-2650. · Zbl 0951.62080  Khudanpur, S. and Narayan, P. (2002). Order estimation for a special class of hidden Markov sources and binary renewal processes. IEEE Trans. Inform. Theory 48 1704-1713. Special issue on Shannon theory: perspective, trends, and applications. · Zbl 1061.94022  Morvai, G. (2003). Guessing the output of a stationary binary time series. In Foundations of Statistical Inference ( Shoresh , 2000). Contrib. Statist. 207-215. Physica, Heidelberg. · Zbl 05280104  Morvai, G., Yakowitz, S. J. and Algoet, P. (1997). Weakly convergent nonparametric forecasting of stationary time series. IEEE Trans. Inform. Theory 43 483-498. · Zbl 0871.62082  Morvai, G., Yakowitz, S. and Györfi, L. (1996). Nonparametric inference for ergodic, stationary time series. Ann. Statist. 24 370-379. · Zbl 0855.62076  Morvai, G. and Weiss, B. (2003). Forecasting for stationary binary time series. In Proceedings of the Eighth Vilnius Conference on Probability Theory and Mathematical Statistics , Part II (2002) 79 25-34. TEV, Vilnius. · Zbl 1030.62076  Morvai, G. and Weiss, B. (2004). Intermittent estimation of stationary time series. Test 13 525-542. · Zbl 1082.62073  Morvai, G. and Weiss, B. (2005). Forward estimation for ergodic time series. Ann. Inst. H. Poincaré Probab. Statist. 41 859-870. · Zbl 1070.62073  Morvai, G. and Weiss, B. (2005). Prediction for discrete time series. Probab. Theory Related Fields 132 1-12. · Zbl 1061.62148  Morvai, G. and Weiss, B. (2005). Limitations on intermittent forecasting. Statist. Probab. Lett. 72 285-290. · Zbl 1066.62090  Morvai, G. and Weiss, B. (2005). On classifying processes. Bernoulli 11 523-532. · Zbl 1073.62077  Morvai, G. and Weiss, B. (2005). Inferring the conditional mean. Theory Stoch. Process. 11 112-120. · Zbl 1164.62382  Morvai, G. and Weiss, B. (2007). On estimating the memory for finitarily Markovian processes. Ann. Inst. H. Poincaré Probab. Statist. 43 15-30. · Zbl 1106.62094  Nobel, A. B. (1999). Limits to classification and regression estimation from ergodic processes. Ann. Statist. 27 262-273. · Zbl 0933.62033  Ornstein, D. S. (1978). Guessing the next output of a stationary process. Israel J. Math. 30 292-296. · Zbl 0386.60032  Ornstein, D. S. and Weiss, B. (1990). How sampling reveals a process. Ann. Probab. 18 905-930. · Zbl 0709.60036  Petrov, V. V. (1995). Limit Theorems of Probability Theory. Oxford Studies in Probability 4 . Oxford Univ. Press, New York. · Zbl 0826.60001  Ryabko, B. Y. (1988). Prediction of random sequences and universal coding. Problemy Peredachi Informatsii 24 3-14. · Zbl 0666.94009  Shields, P. C. (1996). The Ergodic Theory of Discrete Sample Paths. Graduate Studies in Mathematics 13 . Amer. Math. Soc., Providence, RI. · Zbl 0879.28031  Weiss, B. (2000). Single Orbit Dynamics. CBMS Regional Conference Series in Mathematics 95 . Amer. Math. Soc., Providence, RI. · Zbl 1083.37500  Weissman, T. and Merhav, N. (2004). Universal prediction of random binary sequences in a noisy environment. Ann. Appl. Probab. 14 54-89. · Zbl 1040.62085
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.