文章基本信息

标题：Asymmetry of the Kolmogorov complexity of online predicting odd and even bits
本地全文：下载
作者：Bruno Bauwens
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：25
页码：125-136
DOI：10.4230/LIPIcs.STACS.2014.125
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：(On-line) Kolmogorov complexity; (On-line) Algorithmic Probability; Philosophy of Causality; Information Transfer