<p>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$.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-03-09T17:21:44.223Z
I think you mean "will have min-entropy $\geq n - 1$".
Huck Bennett
CC BY-SA 3.0
2015-03-09T22:42:25.807Z
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)$
Joe Bebel
CC BY-SA 3.0
2015-03-09T22:56:54.547Z
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.
Joe Bebel
CC BY-SA 3.0
2015-03-09T23:49:05.417Z
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).
Huck Bennett
CC BY-SA 3.0
2015-03-10T06:33:23.147Z
I think I was a bit imprecise in my initial statement and that led to some confusion through the several edits
Joe Bebel
CC BY-SA 3.0
2015-03-09T04:51:04.690Z
2015-03-10T17:23:40.600Z
2015-03-10T17:23:40.600Z
Joe Bebel
<p>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?</p>

CC BY-SA 3.0
2015-03-09T01:45:44.753Z
Not sure what exactly they have in mind for "weak source", but maybe this is answered by Vadhan's chapter on Extractors ([pdf](http://people.seas.harvard.edu/~salil/pseudorandomness/extractors.pdf)) in Prop 6.6, or the discussion after Lemma 6.8.
usul
CC BY-SA 3.0
2015-03-09T02:22:31.017Z
They mean a distribution with min-entropy $k$.
user32342
<randomness>
Deterministic Randomness Extractors
user32342
# Deterministic Randomness Extractors

(Asked by: username_0 on 2015-03-09)

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?

**Tags:** randomness

> **Comments:**
> **username_1**: Not sure what exactly they have in mind for "weak source", but maybe this is answered by Vadhan's chapter on Extractors ([pdf](http://people.seas.harvard.edu/~salil/pseudorandomness/extractors.pdf)) in Prop 6.6, or the discussion after Lemma 6.8.  
> **username_0**: They mean a distribution with min-entropy $k$.  

---

## 1 answers

### Answer by username_2 on 2015-03-09. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_3**: I think you mean "will have min-entropy $\geq n - 1$".  
> **username_2**: 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)$  
> **username_2**: 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.  
> **username_3**: 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).  
> **username_2**: I think I was a bit imprecise in my initial statement and that led to some confusion through the several edits  

---

