On: Randomness extractors: making fair coins out of bi...

[remram]

Does it take a fixed long time or a long random potentially-infinite time?

[big-green-man → remram]

The latter (except that it doesn't always have to be long; the length of time per bit follows a gaussian distribution). If it were the former then randomness would be predictable in some sense. It's similar to the halting problem.

[remram → big-green-man]

I'm not sure what you mean by "randomness would be predictable". For example, it is possible to do this if you know the bias.

[big-green-man → remram]

If you can predict precisely how often in an input stream randomness occurs, it's not randomness.

[remram → big-green-man]

Knowing the bias is not knowing exactly how often each results come out... it is still probabilistic...

[big-green-man → remram]

Yeah, that's why you can't predict how long you'll wait for a random bit in an entropy extractor.

[remram → big-green-man]

I give up. Thankfully somebody else in this thread gave an answer.