5
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – usul Mar 9 '15 at 1:45
  • $\begingroup$ They mean a distribution with min-entropy $k$. $\endgroup$ – user32342 Mar 9 '15 at 2:22
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think you mean "will have min-entropy $\geq n - 1$". $\endgroup$ – Huck Bennett Mar 9 '15 at 17:21
  • $\begingroup$ 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)$ $\endgroup$ – Joe Bebel Mar 9 '15 at 22:42
  • $\begingroup$ 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. $\endgroup$ – Joe Bebel Mar 9 '15 at 22:56
  • 1
    $\begingroup$ 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). $\endgroup$ – Huck Bennett Mar 9 '15 at 23:49
  • $\begingroup$ I think I was a bit imprecise in my initial statement and that led to some confusion through the several edits $\endgroup$ – Joe Bebel Mar 10 '15 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.