Effective complexity of stationary process realizations

DOI10.3390/E13061200zbMATH Open1301.94042arXiv1001.2686OpenAlexW3098817310MaRDI QIDQ400883FDOQ400883

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

Publication date: 26 August 2014

Published in: Entropy (Search for Journal in Brave)

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Kolmogorov's Structure Functions and Model Selection
• Algorithmic statistics
• Meaningful Information
• A unified approach to weak universal source coding
• Effective Complexity and Its Relation to Logical Depth
• Coding of sources with unknown statistics--I: Probability of encoding error
• Sophistication revisited

Cited In (1)

• A geometric approach to 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)