2026-08-10T11:21:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4452 2024-03-06T10:35:03Z ddc:004 open_access

Asymmetry of the Kolmogorov complexity of online predicting odd and even bits Bauwens, Bruno (On-line) Kolmogorov complexity (On-line) Algorithmic Probability Philosophy of Causality Information Transfer Symmetry of information states that C(x)+C(y|x)=C(x,y)+O(log(C(x))). In [Chernov, Shen, Vereshchagin, and Vovk, 2008] an online variant of Kolmogorov complexity is introduced and we show that a similar relation does not hold. Let the even (online Kolmogorov) complexity of an n-bitstring x_1 x_2...x_n be the length of a shortest program that computes x_2 on input x_1, computes x_4 on input x_1 x_2 x_3, etc; and similar for odd complexity. We show that for all n there exists an n-bit x such that both odd and even complexity are almost as large as the Kolmogorov complexity of the whole string. Moreover, flipping odd and even bits to obtain a sequence x_2 x_1 x_4 x_3..., decreases the sum of odd and even complexity to C(x). Our result is related to the problem of inferrence of causality in timeseries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bruno Bauwens 2014 Is Part Of LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2014.125 urn:nbn:de:0030-drops-44520 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.125 eng https://creativecommons.org/licenses/by/3.0/legalcode