Effective complexity of stationary process realizations

DOI10.3390/E13061200MaRDI QIDQ400883zbMATHOpenAlexFDO

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

zbMATH Keywords

Shannon entropyKolmogorov complexitycoarse effective complexitycomputable stationary processeseffective complexity

Mathematics Subject Classification ID

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

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.

Recommendations

• Information measures, effective complexity, and total information
• On process complexity
• scientific article; zbMATH DE number 4072382
• Strict process machine complexity
• On the descriptional complexity of systems and their output response

Cites work

• scientific article; zbMATH DE number 3844071 (Why is no real title available?)
• scientific article; zbMATH DE number 45100 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 2116058 (Why is no real title available?)
• A unified approach to weak universal source coding
• Algorithmic statistics
• Coding of sources with unknown statistics--I: Probability of encoding error
• Effective Complexity and Its Relation to Logical Depth
• Kolmogorov's Structure Functions and Model Selection
• Meaningful Information
• Sophistication revisited

Cited in

(5)

• A geometric approach to complexity
• On the descriptional complexity of systems and their output response
• Information measures, effective complexity, and total information
• Effective complexity as a measure of information content
• On process complexity

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)