Portal de Periódicos da CAPES

Entropy Measures vs. Kolmogorov Complexity

2011; Multidisciplinary Digital Publishing Institute; Volume: 13; Issue: 3 Linguagem: Inglês

10.3390/e13030595

1099-4300

Andréia Teixeira, Armando B. Matos, André Souto, Luís Antunes,

Benford’s Law and Fraud Detection

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´enyi and Tsallis entropies of order α, showing that it only holds for α = 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 mt(x), Tsallis and Rényi entropies converge if and only if α is greater than 1. We also establish the uniform continuity of these entropies.