5 ms·

The method to get fair flips from an unfair coin is interesting and was recently on hackernews. say a coin is heads(H) 70% of the time. that means it must be ta

The method to get fair flips from an unfair coin is interesting and was recently on hackernews. say a coin is heads(H) 70% of the time. that means it must be tails(T) 30% of the time. If you flip it twice, and calculate the odds of each pair of flips (multiply the probabilities) - HH 49%, HT 21% TH 21% TT 9%. The middle two outcomes are equal probability, aka a fair coin. So ignore HH and TT flips and use HT and TH as Head and Tail of the 'fair' coin.

dragontamer 6y ago
Just note: you're throwing away 58% of your results! The original coin flip runs 230% the speed of your new RNG (that throws away so many results). The Von Neuman method is a great way at demonstrating that removal of bias is possible, but not necessarily practical (especially at high bandwidth). In practice, you want to just cryptographic_hash(coin flips), which should maximize your entropy up to the entropy limit of 1/2 the hashsize (assuming you have a perfect cryptographic hash function). A 512-bit perfect cryptographic hash can only support 256-bits of entropy, due to the birthday attack.
- typicalset 6y ago
  In the general case, you can compress a sequence of N biased coin flips with arithmetic coding. For a coin with known bias, this compression is (essentially) optimal and will therefore produce ~N*(Shannon information) unbiased bits.
  - dragontamer 6y ago
    In the "even more general case", the Shannon Theorem suggests that random_code(message) -> reaches the Shannon Limit. :-) The problem is that perfectly-random codes can't be decoded very easily... so this little factoid is kind of worthless in most cases. Fortunately, we don't actually care what the information looks like when flipping coins. We usually just want "some random message", so no need to decode in this application! ------ Cryptographers assume hash-functions are perfect random codes (they aren't in theory, but they are in practice... at least until they're cracked. Kinda funny how that works out). As such, the cryptohash(message) methodology should also reach the Shannon-limit, as long as your cryptohash remains secure... and you stay within the blocksize restrictions of the hash.
- ChrisLomont 6y ago
  >assuming you have a perfect cryptographic hash function Except there is no such thing (not in the sense you need it) - it too would be a perfect source of randomness, and you're just pushing the problem down the road. As an example, NIST publication 800-90B recommends multiple randomness extractors, one of which is SHA. They recommend using twice the amount of entropy in as the entropy out to get random "enough" bits. Thus even SHA is not going to mix bits well enough as you want. (The things called perfect hash functions in the literature map N items into N slots with no collisions, which is not what is needed here). As a perhaps surprising counterexample to any simple solution, here [1] is a math paper with a proof that there can be no optimal algorithm that is best for all values of coin bias. Here's [2] a cool walkthough on some of the ideas in theory that have been investigated. [1] https://web.eecs.umich.edu/~qstout/abs/AnnProb84.html https://web.eecs.umich.edu/~qstout/abs/AnnProb84.html [2] http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf
  - dragontamer 6y ago
    > Except there is no such thing (not in the sense you need it) ??? Okay, lets choose the simplest hash function of them all: a 1-bit XOR (resulting in a 1-bit "hash"). Lets say I flip the 75% biased coin 100 times, count heads as 1 and tails as 0. I XOR all the results together. What's the probability of XOR(all) == 1, and what's the probability that XOR(all) == 0? You'll find that its quite close to 50/50, which is the limit to the amount of entropy you can pull from a 1-bit hash function. --------- Now lets see for smaller values: 1 flip: 75% chance of 1, 25% of 0. Which is the limit of information so far. 2 flips: ... you know what? Imma write a program and get back to ya a bit later. I probably will edit my post. ------ 2 flips: 62% chance of Parity0 3 flips: 43% chance of Parity0 4 flips: 53% chance of Parity0 Etc. etc. etc. By 16 flips, its 49.9985% chance of Parity0, pretty close to unbiased. It gets pretty hard to distinguish this coin from an unbiased one. -------- I'm not sure if you need a cryptographic hash actually. Its just that cryptographic hashes are close enough to random that its easier to use. Now I'm curious if a CRC32 would efficiently extract 16-bits of entropy from biased coins. CRC32 is clearly not a cryptographic hash, but its pretty good as an "avalanche" due to the nature of GF-arithmetic.
- rini17 6y ago
  The entropy is -0.7log2(0.7)-0.3log2(0.3) = 0.88 . The post is very confusing, in no case can deterministic hashing increase the entropy. And if it outputs only half of input entropy then it's only 8% more efficient than von neumann in this case.
jonahx 6y ago
Related: https://fivethirtyeight.com/features/can-you-make-an-unfair-coin-fair/ https://fivethirtyeight.com/features/can-you-make-an-unfair-...
MrQuincle 6y ago
What about just after the unfair coin sequence toggling every even position? HTHHTHHTTHHH HHHTTTHHTTHT Should be fair. Though there is order now when the coin was unfair.
- Someone 6y ago
  Fair, but only over time, and not truly random. Only over time: this doesn’t help if you need _one_ fair flip. Not random: for any 2 flips in sequence, you want a probability of ¼ to get two heads. This gets you either 70% × 30% or 30% × 70%, both of which are 0.21. That’s only 84% of the expected 0.25. In general, longer sequences of heads or tails are too rare with this method (e.g. for four flips: 70% × 30% × 70% × 30% is 0.0441; only 70.56% of the expected 0.0625. The probability of 6 consecutive heads or tails is less than 60% of what it should be, etc.)
  - MrQuincle 6y ago
    Good point about it not being random over sequences. Would be fun to find a method that would obey more constraints and requires fewer flips than TH, HT from the other comment.
    - Someone 6y ago
      As https://news.ycombinator.com/item?id=25531532 https://news.ycombinator.com/item?id=25531532 said look up arithmetic coding (https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding) It’s not 100% the same, but understanding it should enable you to use the same idea for this problem.
- EvgeniyZh 6y ago
  Each individual flip is still unfair
btilly 6y ago
The Von Neumann method depends on coins being independent. But the measured bias here is a 51% chance of getting what you started with. Which means that if you flip over and over again, there is a correlation between consecutive entries.
- pmiller2 6y ago
  What says you can't reset the coin the same side up in between flips?

dragontamer 6y ago

Just note: you're throwing away 58% of your results! The original coin flip runs 230% the speed of your new RNG (that throws away so many results). The Von Neuman method is a great way at demonstrating that removal of bias is possible, but not necessarily practical (especially at high bandwidth). In practice, you want to just cryptographic_hash(coin flips), which should maximize your entropy up to the entropy limit of 1/2 the hashsize (assuming you have a perfect cryptographic hash function). A 512-bit perfect cryptographic hash can only support 256-bits of entropy, due to the birthday attack.

typicalset 6y ago
In the general case, you can compress a sequence of N biased coin flips with arithmetic coding. For a coin with known bias, this compression is (essentially) optimal and will therefore produce ~N*(Shannon information) unbiased bits.
- dragontamer 6y ago
  In the "even more general case", the Shannon Theorem suggests that random_code(message) -> reaches the Shannon Limit. :-) The problem is that perfectly-random codes can't be decoded very easily... so this little factoid is kind of worthless in most cases. Fortunately, we don't actually care what the information looks like when flipping coins. We usually just want "some random message", so no need to decode in this application! ------ Cryptographers assume hash-functions are perfect random codes (they aren't in theory, but they are in practice... at least until they're cracked. Kinda funny how that works out). As such, the cryptohash(message) methodology should also reach the Shannon-limit, as long as your cryptohash remains secure... and you stay within the blocksize restrictions of the hash.
ChrisLomont 6y ago
>assuming you have a perfect cryptographic hash function Except there is no such thing (not in the sense you need it) - it too would be a perfect source of randomness, and you're just pushing the problem down the road. As an example, NIST publication 800-90B recommends multiple randomness extractors, one of which is SHA. They recommend using twice the amount of entropy in as the entropy out to get random "enough" bits. Thus even SHA is not going to mix bits well enough as you want. (The things called perfect hash functions in the literature map N items into N slots with no collisions, which is not what is needed here). As a perhaps surprising counterexample to any simple solution, here [1] is a math paper with a proof that there can be no optimal algorithm that is best for all values of coin bias. Here's [2] a cool walkthough on some of the ideas in theory that have been investigated. [1] https://web.eecs.umich.edu/~qstout/abs/AnnProb84.html https://web.eecs.umich.edu/~qstout/abs/AnnProb84.html [2] http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf
- dragontamer 6y ago
  > Except there is no such thing (not in the sense you need it) ??? Okay, lets choose the simplest hash function of them all: a 1-bit XOR (resulting in a 1-bit "hash"). Lets say I flip the 75% biased coin 100 times, count heads as 1 and tails as 0. I XOR all the results together. What's the probability of XOR(all) == 1, and what's the probability that XOR(all) == 0? You'll find that its quite close to 50/50, which is the limit to the amount of entropy you can pull from a 1-bit hash function. --------- Now lets see for smaller values: 1 flip: 75% chance of 1, 25% of 0. Which is the limit of information so far. 2 flips: ... you know what? Imma write a program and get back to ya a bit later. I probably will edit my post. ------ 2 flips: 62% chance of Parity0 3 flips: 43% chance of Parity0 4 flips: 53% chance of Parity0 Etc. etc. etc. By 16 flips, its 49.9985% chance of Parity0, pretty close to unbiased. It gets pretty hard to distinguish this coin from an unbiased one. -------- I'm not sure if you need a cryptographic hash actually. Its just that cryptographic hashes are close enough to random that its easier to use. Now I'm curious if a CRC32 would efficiently extract 16-bits of entropy from biased coins. CRC32 is clearly not a cryptographic hash, but its pretty good as an "avalanche" due to the nature of GF-arithmetic.
rini17 6y ago
The entropy is -0.7log2(0.7)-0.3log2(0.3) = 0.88 . The post is very confusing, in no case can deterministic hashing increase the entropy. And if it outputs only half of input entropy then it's only 8% more efficient than von neumann in this case.

jonahx 6y ago

Related: https://fivethirtyeight.com/features/can-you-make-an-unfair-coin-fair/ https://fivethirtyeight.com/features/can-you-make-an-unfair-...

MrQuincle 6y ago

What about just after the unfair coin sequence toggling every even position? HTHHTHHTTHHH HHHTTTHHTTHT Should be fair. Though there is order now when the coin was unfair.

Someone 6y ago
Fair, but only over time, and not truly random. Only over time: this doesn’t help if you need _one_ fair flip. Not random: for any 2 flips in sequence, you want a probability of ¼ to get two heads. This gets you either 70% × 30% or 30% × 70%, both of which are 0.21. That’s only 84% of the expected 0.25. In general, longer sequences of heads or tails are too rare with this method (e.g. for four flips: 70% × 30% × 70% × 30% is 0.0441; only 70.56% of the expected 0.0625. The probability of 6 consecutive heads or tails is less than 60% of what it should be, etc.)
- MrQuincle 6y ago
  Good point about it not being random over sequences. Would be fun to find a method that would obey more constraints and requires fewer flips than TH, HT from the other comment.
  - Someone 6y ago
    As https://news.ycombinator.com/item?id=25531532 https://news.ycombinator.com/item?id=25531532 said look up arithmetic coding (https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding) It’s not 100% the same, but understanding it should enable you to use the same idea for this problem.
EvgeniyZh 6y ago
Each individual flip is still unfair

btilly 6y ago

The Von Neumann method depends on coins being independent. But the measured bias here is a 51% chance of getting what you started with. Which means that if you flip over and over again, there is a correlation between consecutive entries.

pmiller2 6y ago
What says you can't reset the coin the same side up in between flips?