

Preprint 2/2010
Effective complexity of stationary process realizations
Nihat Ay, Markus Mueller, and Arleta Szkola
Contact the author: Please use for correspondence this email.
Submission date: 11. Jan. 2010 (revised version: November 2011)
Pages: 16
published in: Entropy, 13 (2011) 6, p. 1200-1211
DOI number (of the published article): 10.3390/e13061200
Bibtex
MSC-Numbers: 60, 94
Keywords and phrases: Effective complexity, Kolmogorov complexity, stochastic processes
Download full preprint: PDF (178 kB)
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 [1] 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.