News
11 Oct 2025: New page
Oct 2025: Accepted
Title
Rate of convergence of computable predictions
Type
Research article
This is a journal version of the conference paper with the title Computable prediction.
Publication
To appear in Journal of Symbolic Logic
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.
download
preprint