Some authors use a heuristic estimate obtained from the Asymptotic Equipartition Property, which yields roughly $n$ extractable bits, where $n$ is the total Shannon entropy amount. However the best known precise form gives only $n-O(\sqrt{\log(1/\epsilon) n})$, where $\epsilon$ is the distance of the extracted bits from uniform. In this paper we show a matching $ n-\Omega(\sqrt{\log(1/\epsilon) n})$ upper bound. Therefore, the loss of $\Theta(\sqrt{\log(1/\epsilon) n})$ bits is necessary. As we show, this theoretical bound is of practical relevance. Namely, applying the imprecise AEP heuristic to a mobile phone accelerometer one might overestimate extractable entropy even by $100\%$, no matter what the extractor is. Thus, the ``AEP extracting heuristic'' should not be used without taking the precise error into account.
Category / Keywords: foundations / Date: received 15 Jun 2015 Contact author: maciej skorski at gmail com Available format(s): PDF | BibTeX Citation Version: 20150621:162725 (All versions of this report) Short URL: ia.cr/2015/591 Discussion forum: Show discussion | Start new discussion