# Consistent Prediction Of Stationary Ergodic Sequences

We are interested in stationary ergodic sequences . A striking result by Bailey says that there does not exist a predictor of such that

holds for any stationary ergodic sequence . (In other words, there does no exist a universal strongly consistent predictor.) This is true even for binary sequences .

Examples for binary sequences were constructed independently by David Bailey (1976) and, later, by Boris Ryabko (1988). Ryabko's example is much simpler; his intuitive exposition was interpreted and extended in Gyorfi et al. (1998), too.

A predictor of is called universally consistent if

holds for any bounded stationary ergodic sequence . The existence of a universally consistent predictor was established by Morvai et al. (1997).

### Bibliography

• D. H. Bailey (1976). Sequential schemes for classifying and predicting ergodic processes. PhD dissertation, Stanford University, Stanford, CA.
• L. Gyorfi, G. Morvai, and S. J. Yakowitz (1998). Limits to consistent on-line forecasting for ergodic time series. IEEE Transactions on Information Theory 44:886 - 892.
• G. Morvai, S. J. Yakowitz, and P. Algoet (1997). Weakly convergent non-parametric forecasting of stationary time series. IEEE Transactions on Information Theory 43:483 - 498.
• B. Ryabko (1998). Prediction of random sequences and universal coding. Problems of Information Transmission 24:87 - 96.