Consistent Prediction Of Stationary Ergodic Sequences

We are interested in stationary ergodic sequences ⚠ $X_1,X_2,\ldots$. A striking result by Bailey says that there does not exist a predictor ⚠ $g_n(X_1,\ldots,X_n)$ of ⚠ $E(X_{n+1}\mid X_1,\ldots,X_n)$ such that ⚠ $$ \lim_{n\to\infty} (g_n(X_1,\ldots,X_n)-E(X_{n+1}\mid X_1,\ldots,X_n))=0 \quad\text{a.s.} ⚠ $$ holds for any stationary ergodic sequence ⚠ $X_1,X_2,\ldots$. (In other words, there does no exist a universal strongly consistent predictor.) This is true even for binary sequences ⚠ $X_1,X_2,\ldots$.

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 ⚠ $g_n(X_1,\ldots,X_n)$ of ⚠ $E(X_{n+1}\mid X_1,\ldots,X_n)$ is called universally ⚠ $L_1$ consistent if ⚠ $$ \lim_{n\to\infty} E|g_n(X_1,\ldots,X_n)-E(X_{n+1}\mid X_1,\ldots,X_n)|=0 ⚠ $$ holds for any bounded stationary ergodic sequence ⚠ $X_1,X_2,\ldots$. The existence of a universally ⚠ $L_1$ consistent predictor was established by Morvai et al. (1997).

Bibliography

• D. H. Bailey (1976). Sequential schemes for classifying and predicting ergodic processes. Ph D 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.