Asymmetry of the Kolmogorov complexity of online predicting odd and even bits

Bauwens, Bruno

doi:10.4230/LIPIcs.STACS.2014.125

Document

Asymmetry of the Kolmogorov complexity of online predicting odd and even bits

Author Bruno Bauwens

Part of: Volume: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2014-03-05

PDF

File

PDF

LIPIcs.STACS.2014.125.pdf

Filesize: 0.63 MB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2014.125
URN: urn:nbn:de:0030-drops-44520

Subject Classification

Keywords

(On-line) Kolmogorov complexity
(On-line) Algorithmic Probability
Philosophy of Causality
Information Transfer

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

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.

Cite As Get BibTex

Bruno Bauwens. Asymmetry of the Kolmogorov complexity of online predicting odd and even bits. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 125-136, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.STACS.2014.125

Author Details

Bruno Bauwens

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail