Universal prediction and universal coding
Joe Suzuki · Systems and Computers in Japan · 2003
Abstract Although prediction schemes called “universal” are now abundant, very little attention has been devoted to the definition of universal prediction. This paper addresses, for α‐nary (α ≥ 2) sequences, the criteria of successful universal prediction and the prediction schemes that achieve the goals. We propose the following criteria: for any probability measures in a given measure class, the error probability of prediction (in the problem of predicting a value for the next outcome) and the conditional probability of the next outcome given the past sequence (in the problem of predicting a probability distribution for the next outcome, i.e., the probability assignment problem) should converge to the optimal values in probability (weakly universal) and almost surely (strongly universal). We present a small review of various results on universal prediction, and give several results relating the developed criteria to each other and to various prediction submeasures. Furthermore, we explore the connection between universal prediction and universal coding. The proposed criteria are applied to any measure class as well as stationary ergodic measures. © 2003 Wiley Periodicals, Inc. Syst Comp Jpn, 34(6): 1–11, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/scj.10357