Entropy Measures vs. Kolmogorov Complexity

• Type: Article in International Scientific Journal
• Date: 2011

Authors

teixeira, a (Author) Other; matos, a (Author) FCUP; souto, a (Author) FCUP; antunes, l (Author) FCUP

Journal

Title: Entropy

Vol. 13

Pages: 595-611

ISSN: 1099-4300

Publisher: MDPI

Indexing

ISI Web of Knowledge - 36 Citations

Scopus - 44 Citations

Other information

Authenticus ID: P-002-TY2

DOI: 10.3390/e13030595

Abstract (EN): 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 Renyi 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 Renyi entropies converge if and only if alpha is greater than 1. We also establish the uniform continuity of these entropies.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 17