Effective complexity of stationary process realizations

DOI10.3390/E13061200MaRDI QIDQ400883zbMATH OpenOpenAlexFDO

Authors Nihat Ay, Arleta Szkoła, Markus Müller

Publication date 26 August 2014

Published in Entropy (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1001.2686

coarse effective complexity computable stationary processes effective complexity Kolmogorov complexity Shannon entropy

Stationary stochastic processes (60G10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Measures of information, entropy (94A17)

Abstract: The concept of effective complexity of an object as the minimal description length of its regularities has been initiated by Gell-Mann and Lloyd. The regularities are modeled by means of ensembles, that is probability distributions on finite binary strings. In our previous paper we propose a definition of effective complexity in precise terms of algorithmic information theory. Here we investigate the effective complexity of binary strings generated by stationary, in general not computable, processes. We show that under not too strong conditions long typical process realizations are effectively simple. Our results become most transparent in the context of coarse effective complexity which is a modification of the original notion of effective complexity that uses less parameters in its definition. A similar modification of the related concept of sophistication has been suggested by Antunes and Fortnow.

Review text

Summary: The concept of effective complexity of an object as the minimal description length of its regularities has been initiated by \textit{M. Gell-Mann} and \textit{S. Lloyd} [Complexity 2, No. 1, 44--52 (1996; Zbl 1294.94011)]. The regularities are modeled by means of ensembles, which is the probability distributions on finite binary strings. In our previous paper [IEEE Trans. Inform. Theory 56, No. 9, 4593--4607 (2010), \url{doi:10.1109/TIT.2010.2053892})], we proposed a definition of effective complexity in precise terms of algorithmic information theory. Here, we investigate the effective complexity of binary strings generated by stationary, in general not computable, processes. We show that, under not too strong conditions, long typical process realizations are effectively simple. Our results become most transparent in the context of coarse effective complexity, which is a modification of the original notion of effective complexity that needs less parameters in its definition. A similar modification of the related concept of sophistication has been suggested by \textit{L. Antunes} and \textit{L. Fortnow} [Theory Comput. Syst. 45, No.~1, 150--161 (2009; Zbl 1175.68209)].

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Effective complexity of stationary process realizations

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