Summary: Kolmogorov complexity and Shannon entropy are conceptually different measures. However, for any recursive probability distribution, the expected value of Kolmogorov complexity equals its Shannon entropy, up to a constant. We study if a similar relationship holds for Rényi and Tsallis entropies of order \(\alpha \), showing that it only holds for \(\alpha = 1\). Regarding a time-bounded analogue relationship, we show that, for some distributions we have a similar result. We prove that, for universal time-bounded distribution \(m^{t}(x)\), Tsallis and Rényi entropies converge if and only if \(\alpha \) is greater than 1. We also establish the uniform continuity of these entropies.
- A formal theory of inductive inference. Part I
- A Mathematical Theory of Communication
- An introduction to Kolmogorov complexity and its applications
- scientific article; zbMATH DE number 3492569 (Why is no real title available?)
- Kolmogorov's contributions to information theory and algorithmic complexity
- On the Length of Programs for Computing Finite Binary Sequences
- Possible generalization of Boltzmann-Gibbs statistics.
- Thermodynamic stability conditions for the Tsallis and Rényi entropies
- Three approaches to the quantitative definition of information*
- Uniform estimates on the Tsallis entropies
- An entropy based measure for comparing distributions of complexity
- New statistical models of nonergodic cognitive systems and their pathologies
- Shannon Entropy vs. Kolmogorov Complexity
- Entropy of theK-Satisfiability Problem
- The Complexity of Approximating the Entropy
- Relating description complexity to entropy
- Complexity of two-level systems
- Description complexity of unary structures in first-order logic with links to entropy
This page was built for publication: Entropy measures vs. Kolmogorov complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q657548)
