2020/03/14 by Alexey Milovanov, Milovanov, Alexey
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Information Theory (cs.IT) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2005.03467
openalex publication_date 2020/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider the following prediction problem. Assume that there is a block box that produces bits according to some unknown computable distribution on the binary tree. We know first n bits x1 x2 … xn. We want to know the probability of the event that that the next bit is equal to 1. Solomonoff suggested to use universal semimeasure m for solving this task. He proved that for every computable distribution P and for every b ∈ \0,1\ the following holds: ∑n=1∞∑x: l(x)=n P(x) (P(b | x) - m(b | x))2 lt; ∞ . However, Solomonoff's method has a negative aspect: Hutter and Muchnik proved that there are an universal semimeasure m, computable distribution P and a random (in Martin-Löf sense) sequence x1 x2… such that limn → ∞ P(xn+1 | x1… xn) - m(xn+1 | x1… xn) \nrightarrow 0. We suggest a new way for prediction. For every finite string x we predict the new bit according to the best (in some sence) distribution for x. We prove the similar result as Solomonoff theorem for our way of prediction. Also we show that our method of prediction has no that negative aspect as Solomonoff's method.