How much randomness can be extracted from memoryless Shannon entropy sources
Maciej Skórski · 2015
Abstract. We revisit the classical problem: given a memoryless source having a certain amount of Shannon Entropy, how many random bits can be extracted? This question appears in works studying random number generators built from physical entropy sources. 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 pre-cise form gives only n − O(√log(1/)n), where is the distance of the extracted bits from uniform. In this paper we show a matching n−Ω(√log(1/)n) upper bound. Therefore, the loss of Θ(√log(1/)n) bits is necessary. As we show, this theoretical bound is of practical rele-vance. 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.