In today's Discrete Lunch, we'll discuss randomness extractors. A randomness extractor is a function which maps the points of a probability space to bit strings in such a way that, for all k, all length k strings are produced with equal probability (i.e., either 0 or 2-k.) One is then interested in the average length of the strings produced by the extractor.
We will first prove the easy upper bound on the average length of the strings produced by an extractor: the entropy of the probability space. After that, we'll look at a few constructions of randomness extractors.
Discrete Lunch >