履歴
2025年10月11日：ページ作成
2025年10月：受理
タイトル
Rate of convergence of computable predictions
種類
研究論文
会議論文Computable predictionの雑誌版．
出版情報
To appear in Journal of Symbolic Logic
要旨
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.
ダウンロード
preprint