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. 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.