Effective Complexity of Stationary Process Realizations

Abstract: The concept of effective complexity of an object as the minimal descriptionlength of its regularities has been initiated by Gell-Mann and Lloyd. The regularities aremodeled by means of ensembles, which is the probability distributions on finite binarystrings. In our previous paper [1] we propose a definition of effective complexity in preciseterms of algorithmic information theory. Here we investigate the effective complexity ofbinary strings generated by stationary, in general not computable, processes. We show thatunder not too strong conditions long typical process realizations are effectively simple. Ourresults become most transparent in the context of coarse effective complexity which is amodification of the original notion of effective complexity that needs less parameters in itsdefinition. Asimilarmodificationoftherelatedconceptofsophisticationhasbeensuggestedby Antunes and Fortnow.Keywords: effective complexity; Kolmogorov complexity; Shannon entropy; computablestationary processes; coarse effective complexity