# Deterministic Randomness Extractors

I have read in several papers it is well known that deterministically extracting even one bit from a weak source is impossible. Could someone explain why?

• Not sure what exactly they have in mind for "weak source", but maybe this is answered by Vadhan's chapter on Extractors (pdf) in Prop 6.6, or the discussion after Lemma 6.8.
– usul
Mar 9, 2015 at 1:45
• They mean a distribution with min-entropy $k$. Mar 9, 2015 at 2:22

Intuitively, the situation is you'd like some deterministic extractor $E: \{0,1\}^n \rightarrow \{0,1\}$ that can take in $n$ bits sampled from a weak source and output one bit with probability close to $1/2$, say it outputs 0 with probability $1/2 \pm \epsilon$ and 1 with $1/2\pm\epsilon$.
Here's a weak argument that at the very least, such extractors $E$ can't exist if we don't put any restrictions on the input distribution other than it has 'enough' min-entropy. Suppose $E$ is such a potential extractor. By flipping the output if necessary, we may assume without loss of generality that $|E^{-1}(0)|\ge|E^{-1}(1)|$; that is, $E^{-1}(0)$ is a set of $n$-bit strings of size at least $2^{n}/2$. Thus a random variable that samples uniformly from $E^{-1}(0)$ will have min-entropy at least $n - 1$, but the extractor will never give you any 'random' output other than 0.
Of course, if we tighten the restrictions on the input distribution (say, we assume all $n$ bits are IID) then we do have deterministic extractors that work. But as problem 6.6 in Salil Vadhan's survey of pseudorandomness shows, even weakening the IID assumption a little bit will cause deterministic extractors to fail, by a slight generalization of the same argument as I made above.
• I think you mean "will have min-entropy $\geq n - 1$". Mar 9, 2015 at 17:21
• It's not precisely min-entropy $\ge n-1$ because the set could be smaller than $2^{n-1}$ by a constant fraction. So in this case, saying $\Omega(n-1)$ could be slightly misleading , even though it's equivalent to $\Omega(n)$ Mar 9, 2015 at 22:42
• Of course, one can always look at both $E^{-1}(0)$ and $E^{-1}(1)$, and then sampling uniformly from the larger would always have min-entropy $\ge n-1$ as you suggest. Mar 9, 2015 at 22:56
• My comment was based on the previous edit. I thought you were trying to emphasize that the min-entropy is very close to $n$ (off by an additive constant), which is stronger than just saying it's $\Omega(n)$ (although the latter is true and still certainly makes your point). Mar 9, 2015 at 23:49