There is no generally accepted definition of conditional Rényi entropy. The (unconditional) Rényi entropy depends on a parameter α, which for the case of min-entropy takes the value ∞. Even for this particular case, there are several proposals for the definition of conditional entropy. This paper describes three general definitions of conditional Rényi entropy that were found or suggested in the literature. Their properties are studied and their values, as a function of α, are compared. The particular case of min-entropy is widely used in cryptography as a security parameter; this case is studied in some detail.

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ényi and Tsallis entropies of order α, showing that it only holds for Ré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 mt(x), Tsallis and Rényi entropies converge if and only if a is greater than 1.