4 ms·
If the coin is biased so that it lands on heads only 1 in a million times it will take a lot of coin throws to get some randomness out of it. This isn't a limit
by cedilla 2y ago
If the coin is biased so that it lands on heads only 1 in a million times it will take a lot of coin throws to get some randomness out of it. This isn't a limit of the technique, just a consequence of the low entropy source.
- remram 2y agoDoes it take a fixed long time or a long random potentially-infinite time?
- deleted 2y ago[deleted]
- big-green-man 2y agoThe 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 2y agoI'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 2y agoIf you can predict precisely how often in an input stream randomness occurs, it's not randomness.
- remram 2y agoKnowing the bias is not knowing exactly how often each results come out... it is still probabilistic...
- big-green-man 2y agoYeah, that's why you can't predict how long you'll wait for a random bit in an entropy extractor.
- remram 2y agoI give up. Thankfully somebody else in this thread gave an answer.