Predictions and algorithmic statistics for infinite sequence

DOI10.1007/978-3-030-79416-3_17MaRDI QIDQ6340242arXivFDO

Authors Alexey Milovanov

Publication date 14 March 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-79416-3_17

Mathematics Subject Classification ID

Theory of computing (68Qxx)

arXiv classification

cs.ITmath.IT

Abstract: 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 $x_1{x}_{2}ldots{x}_n$. 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 $bin0,1$ the following holds: ${\displaystyle }$sum_{n=1}^{infty}sum_{x: l(x)=n} P(x) (P(b | x) - m(b | x))^2 < infty .${\displaystyle }$ 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{"o}f sense) sequence $x_1{x}_{2}ldots$ such that $li{m}_{noinfty}P(x_{n+1}|x_{1}ldots{x}_n)-m(x_{n+1}|x_{1}ldots{x}_n)rightarrow0$. 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.

This page was built for publication: Predictions and algorithmic statistics for infinite sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6340242)