5 ms·
I assume it's impossible to achieve in bounded time?
by throwaway613834 9y ago
I assume it's impossible to achieve in bounded time?
- contravariant 9y agoThe coin can only generate a limited amount of entropy per flip, it could take arbitrary long to get enough to generate 1 unbiased coin-flip. You could bound the time if you knew the exact distribution though. Not sure if there's a method that's guaranteed to meet this bound.
- throwaway613834 9y agoHow could you bound the time if you knew the exact distribution? Like say it has heads probability p?
- contravariant 9y agoYeah I may have spoken to soon. There's a minimum bound, but now that I think of it there's generally no reason to believe that any subset of outcomes for any bounded number of flips would have a probability of exactly 1/2. In fact this is impossible if p is transcendental. The set of p for which there is a method to do it in finitely many flips is quite interesting though. It is bigger than the irrational numbers (it contains sqrt(1/2)), but smaller than all algebraic numbers. At the very least you'd need 1/2 ∈ Z[p], but that might not be enough.
- hughes 9y agoWith a few dozen flips you can achieve a greater likelihood that you're flipping the most biased coin on the planet, and stop the game.
- throwaway613834 9y agoRight, this was a theoretical question..
- geeio 9y agoI don’t think this would be possible even with a fair coin.