Computable prediction of infinite binary sequences with zero-one loss

Abstract

A predictor is a total function from binary words into the set of binary outcomes ${0,1}$. It is interpreted as an operation of guessing i+ 1-th outcome using information about the first i outcomes of some process. This thesis focuses on predictors which are total computable functions. The performance of a predictor is assessed via the zero-one loss function, that is, westudy the ratio between the number of wrong guesses and the total number of guesses made so far. This ratio is called the prediction error. In particular, the thesis deals with questions concerning the asymptotic behaviors of prediction errors. We study such issues as convergence, optimality and existence of schemes that are universal for theclass of stationary ergodic processes. The results are presented in the context of the algorithmic randomness theory.

Publication
Institute of Computer Science, Polish Academy of Sciences