Entropy Measures vs. Algorithmic Information

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2010

Autores

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

Ata de Conferência Internacional

Título: IEEE International Symposium on Information Theory (ISIT 2010), Austin TX, June 2010

Páginas: 1413-1417

IEEE International Symposium on Information Theory (ISIT 2010), Austin TX, June 2010

Austin TX, JUL 13-13, 2010

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 1 Citação

Outras Informações

ID Authenticus: P-003-DDF

DOI: 10.1109/isit.2010.5513643

Abstract (EN): Algorithmic entropy and Shannon entropy are two conceptually different information measures, as the former is based on size of programs and the later in probability distributions. However, it is known that, for any recursive probability distribution, the expected value of algorithmic entropy equals its Shannon entropy, up to a constant that depends only on the distribution. We study if a similar relationship holds for Renyi and Tsallis entropies of order a, showing that it only holds for Renyi and Tsallis entropies of order 1 (i.e., for Shannon entropy). Regarding a time bounded analogue relationship, we show that, for distributions such that the cumulative probability distribution is computable in time t(n), the expected value of time-bounded algorithmic entropy (where the alloted time is nt(n) log(nt(n))) is in the same range as the unbounded version. So, for these distributions, Shannon entropy captures the notion of computationally accessible information. We prove that, for universal time-bounded distribution m(t)(x), Tsallis and Renyi entropies converge if and only if a is greater than 1.

Idioma: Inglês

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

Nº de páginas: 5