Effective complexity of stationary process realizations (Q400883): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / arXiv ID | |||
Property / arXiv ID: 1001.2686 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Effective Complexity and Its Relation to Logical Depth / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4827369 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3995624 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithmic statistics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Meaningful Information / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Kolmogorov's Structure Functions and Model Selection / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sophistication revisited / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4337021 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A unified approach to weak universal source coding / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Coding of sources with unknown statistics--I: Probability of encoding error / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3314114 / rank | |||
Normal rank |
Latest revision as of 23:06, 8 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Effective complexity of stationary process realizations |
scientific article |
Statements
Effective complexity of stationary process realizations (English)
0 references
26 August 2014
0 references
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)].
0 references
effective complexity
0 references
Kolmogorov complexity
0 references
Shannon entropy
0 references
computable stationary processes
0 references
coarse effective complexity
0 references