Abstract
This paper investigates the intersection of information theory and algorithmic randomness, specifically exploring whether a universal probability measure—capable of compressing any stationary ergodic source to its entropy rate—can also serve as an optimal predictor for individual sequences. By "effectivizing" classical ergodic theorems, the authors demonstrate that under certain technical conditions, universal coding induces universal prediction. A primary contribution is the theoretical validation of the Prediction by Partial Matching (PPM) algorithm as a mathematically universal predictor for Martin-Löf random sequences.
Introduction
In the realm of information theory, two fundamental tasks are often viewed as two sides of the same coin: Estimation (Coding) and Guessing (Prediction). Coding focuses on assigning probabilities to sequences to achieve maximum compression, while prediction aims to forecast the next symbol in a sequence to minimize error.
While classical results establish that these tasks are related "almost surely"—meaning they hold for the vast majority of sequences generated by a source—this paper addresses a more stringent requirement. The authors ask: Does a universal coder necessarily induce a universal predictor for specific, individual "random" sequences? To answer this, they utilize the framework of algorithmic randomness, specifically focusing on Martin-Löf random points—infinite sequences that pass every computable test for randomness.
Theoretical Framework: Effectivizing Ergodicity
The core challenge in this research is translating classical measure-theoretic results into the language of algorithmic randomness. Many theorems in probability hold "almost everywhere," but the authors seek results that hold "everywhere" on the set of Martin-Löf random points. This transition requires the "effectivization" of several key mathematical tools:
- Ergodic Theorems: The authors extend the Breiman and Birkhoff ergodic theorems to hold specifically for Martin-Löf random points, ensuring that the long-term averages of these sequences behave predictably.
- Effective Azuma’s Inequality: To handle sequences where conditional probabilities fluctuate, the authors employ an algorithmic version of Azuma’s inequality for martingales.
- Condition (1): A critical technical requirement introduced in the paper is a uniform lower bound on conditional probabilities. This condition prevents the estimator from assigning a vanishingly small probability to a symbol that actually occurs, which would otherwise cause the predictor to fail.
The Bridge Between Coding and Prediction
The paper’s primary theoretical breakthrough is Theorem 11, which establishes that if a universal measure $R$ satisfies the authors' specific growth bound (Condition 1), it must function as a universal forward estimator. This proves that the information-theoretic objective of matching entropy rate can successfully force the prequential objective of matching true conditional probabilities.
However, the authors also present a "negative" surprise in Theorem 9: simply being a universal forward estimator is not sufficient to guarantee a universal predictor. It is possible to estimate probabilities accurately on average while failing to provide the optimal guess for the next symbol on specific random sequences. This highlights the necessity of the additional technical constraints proposed in their framework.
The Universality of PPM
A significant practical implication of this work is the formal validation of the Prediction by Partial Matching (PPM) algorithm. Although PPM has been a staple of data compression since the 1980s, its status as a "universal" predictor in the strongest mathematical sense remained unproven.
In Theorem 14, the authors formally demonstrate that the predictor induced by the PPM measure is 1-universal. This means that for any stationary ergodic source, the PPM predictor achieves the optimal error rate (the unpredictability rate $u_P$) on every Martin-Löf random sequence. This provides a rigorous theoretical foundation for the empirical success PPM has enjoyed for decades.
Conclusion and Future Directions
The research establishes a robust link between universal coding and prediction, yet several questions remain. The authors acknowledge that it is currently unknown if their growth bound (Condition 1) is strictly necessary or merely a sufficient condition required for their proof method. Furthermore, while the results are definitive for stationary ergodic sources over finite alphabets, extending these proofs to non-stationary sources or infinite alphabets presents a significant challenge for future study. By bridging the gap between average-case performance and individual sequence randomness, this work advances our understanding of how machines can learn to predict the future from the patterns of the past.
Summary updated