RATE OF CONVERGENCE OF COMPUTABLE PREDICTIONS

Abstract We consider the problem of predicting the next bit in an infinite binary sequence sampled from the Cantor space with an unknown computable measure. We propose a new theoretical framework to investigate the properties of good computable predictions, focusing on such predictions’ convergence rate. Since no computable prediction can be the best, we first define a better prediction as one that dominates the other measure. We then prove that this is equivalent to the condition that the sum of the KL divergence errors of its predictions is smaller than that of the other prediction for more computable measures. We call that such a computable prediction is more general than the other. We further show that the sum of any sufficiently general prediction errors is a finite left-c.e. Martin-Löf random real. This means the errors converge to zero more slowly than any computable function.