Inequalities for Shannon entropy and Kolmogorov complexity (Q1567410): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q4079503 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A strange application of Kolmogorov complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5626684 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3214803 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Logical basis for information theory and probability theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4337021 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Relations between varieties of kolmogorov complexities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4111952 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS / rank | |||
Normal rank |
Revision as of 16:40, 29 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Inequalities for Shannon entropy and Kolmogorov complexity |
scientific article |
Statements
Inequalities for Shannon entropy and Kolmogorov complexity (English)
0 references
10 July 2002
0 references
It was mentioned by \textit{A. N. Kolmogorov} [IEEE Trans. Inf. Theory IT-14, 662-664 (1968; Zbl 0167.47601)] that the properties of algorithmic complexity and Shannon entropy are similar. We investigate one aspect of this similarity. Namely, we are interested in linear inequalities that are valid for Shannon entropy and for Kolmogorov complexity. It turns out that (1) all linear inequalities that are valid for Kolmogorov complexity are also valid for Shannon entropy and vice versa; (2) all linear inequalities that are valid for Shannon entropy are valid for ranks of finite subsets of linear spaces; (3) the opposite statement is not true, Ingleton's inequality [\textit{A. W. Ingleton}, Combinat. Math. Appl., Proc. Conf. Math. Inst., Oxford 1969, 149-167 (1971; Zbl 0222.05025)] is valid for ranks but not for Shannon entropy; (4) for some special cases, all three classes of inequalities coincide and have a simple description. We present an inequality for Kolmogorov complexity that implies Ingleton's inequality for ranks; another application of this inequality is a new simple proof of one of \textit{P. Gács} and \textit{J. Körner}'s results on common information [Probl. Control Inform. Theory 2, 149-162 (1973; Zbl 0317.94025)].
0 references
Shannon entropy
0 references
Kolmogorov complexity
0 references
linear inequalities
0 references
Ingleton's inequality
0 references