Entropy Measures vs. Algorithmic Information

Details Entropy Measures vs. Algorithmic Information Entropy Measures vs. Algorithmic Information

2009-01-19

arxiv.org/abs/0901.2903v2

Computer Science

Information Theory

Scientific paper

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 R\'{e}nyi and Tsallis entropies of order $\alpha$, showing that it only holds for R\'{e}nyi 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 R\'{e}nyi entropies converge if and only if $\alpha$ is greater than 1.

Affiliated with

Also associated with

No associations

Rating

Entropy Measures vs. Algorithmic Information does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Entropy Measures vs. Algorithmic Information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Entropy Measures vs. Algorithmic Information will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-567054