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.

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)
Full Text: DOI arXiv
[1] Algoet, P. (1992). Universal schemes for prediction, gambling and portfolio selection. Ann. Probab. 20 901-941. · Zbl 0758.90006
[2] 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
[3] 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
[4] Bailey, D. H. (1976). Sequential schemes for classifying and predicting ergodic processes. Ph.D. thesis, Stanford Univ.
[5] 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
[6] 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.
[7] Feller, W. (1968). An Introduction to Probability Theory and Its Applications . I , 3rd ed. Wiley, New York. · Zbl 0155.23101
[8] Ghahramani, S. (2005). Fundamentals of Probability with Stochastic Processes , 3rd ed. Prentice Hall, Upper Saddle River, NJ. · Zbl 1336.60001
[9] 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
[10] 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
[11] 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
[12] 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
[13] 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
[14] Morvai, G., Yakowitz, S. and Györfi, L. (1996). Nonparametric inference for ergodic, stationary time series. Ann. Statist. 24 370-379. · Zbl 0855.62076
[15] 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
[16] Morvai, G. and Weiss, B. (2004). Intermittent estimation of stationary time series. Test 13 525-542. · Zbl 1082.62073
[17] Morvai, G. and Weiss, B. (2005). Forward estimation for ergodic time series. Ann. Inst. H. Poincaré Probab. Statist. 41 859-870. · Zbl 1070.62073
[18] Morvai, G. and Weiss, B. (2005). Prediction for discrete time series. Probab. Theory Related Fields 132 1-12. · Zbl 1061.62148
[19] Morvai, G. and Weiss, B. (2005). Limitations on intermittent forecasting. Statist. Probab. Lett. 72 285-290. · Zbl 1066.62090
[20] Morvai, G. and Weiss, B. (2005). On classifying processes. Bernoulli 11 523-532. · Zbl 1073.62077
[21] Morvai, G. and Weiss, B. (2005). Inferring the conditional mean. Theory Stoch. Process. 11 112-120. · Zbl 1164.62382
[22] 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
[23] Nobel, A. B. (1999). Limits to classification and regression estimation from ergodic processes. Ann. Statist. 27 262-273. · Zbl 0933.62033
[24] Ornstein, D. S. (1978). Guessing the next output of a stationary process. Israel J. Math. 30 292-296. · Zbl 0386.60032
[25] Ornstein, D. S. and Weiss, B. (1990). How sampling reveals a process. Ann. Probab. 18 905-930. · Zbl 0709.60036
[26] Petrov, V. V. (1995). Limit Theorems of Probability Theory. Oxford Studies in Probability 4 . Oxford Univ. Press, New York. · Zbl 0826.60001
[27] Ryabko, B. Y. (1988). Prediction of random sequences and universal coding. Problemy Peredachi Informatsii 24 3-14. · Zbl 0666.94009
[28] Shields, P. C. (1996). The Ergodic Theory of Discrete Sample Paths. Graduate Studies in Mathematics 13 . Amer. Math. Soc., Providence, RI. · Zbl 0879.28031
[29] Weiss, B. (2000). Single Orbit Dynamics. CBMS Regional Conference Series in Mathematics 95 . Amer. Math. Soc., Providence, RI. · Zbl 1083.37500
[30] 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.