Entropy Measures vs. Kolmogorov Complexity

• Tipo: Artigo em Revista Científica Internacional
• Data: 2011

Autores

teixeira, a (Autor) Outra; matos, a (Autor) FCUP; souto, a (Autor) FCUP; antunes, l (Autor) FCUP

Revista

Título: Entropy

Vol. 13

Páginas: 595-611

ISSN: 1099-4300

Editora: MDPI

Indexação

ISI Web of Knowledge - 36 Citações

Scopus - 44 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 17