Our results and techniques used in the proof immediately imply many quantitatively tight separations between Shannon and smooth Renyi entropy, which were previously known as qualitative statements or one-sided bounds. In particular, we precisely calculate the number of bits that can be extracted from a Shannon entropy source, and calculate how far from the uniform distribution is a distribution with the given amount Shannon entropy. To illustrate our results we provide clear numerical examples.
In the typical situation, when the gap between Shannon entropy of a distribution and its length is bigger than $1$, the length of the extracted sequence is very small, even if we allow the randomness quality to be poor. In the case of almost full entropy, where the gap is close to $0$, the $\ell_2$-distance to uniform is roughly of the same order as the gap. Therefore, it is actually not possible to decide the strong quality of supposed true randomness, {efficiently and at extremely high confidence level} , by means of Shannon entropy estimators, like Maurer's Universal Test or others.
Our approach involves convex optimization techniques, applied to characterize worst case distributions, and the use of the Lambert $W$ function, by which we resolve equations coming from Shannon entropy constraints. We believe that it may be of independent interests and useful in studying Shannon entropy with constraints elsewhere.
Category / Keywords: foundations / Entropy Estimators, Smooth Entropy, Randomness Extractors Original Publication (with minor differences): IMACC 2015 Date: received 26 Nov 2014, last revised 8 Oct 2015 Contact author: maciej skorski at gmail com Available format(s): PDF | BibTeX Citation Note: Some typos corrected Version: 20151008:163331 (All versions of this report) Short URL: ia.cr/2014/967 Discussion forum: Show discussion | Start new discussion