4 ms·

Tangent, but interesting: how do you get fair samples from a biased coin? 1. You take a string of biased samples like 001011100101 2. you split it in pairs 00 1

Tangent, but interesting: how do you get fair samples from a biased coin? 1. You take a string of biased samples like 001011100101 2. you split it in pairs 00 10 11 10 01 01 3. you keep only pairs with a zero and a one in them 10 10 01 01 4. You assign 0 and 1 to them, e.g. 1 1 0 0, this is a fair sampling from an unbiased coin Why does it work? Because even if p(0) ≠ p(1), p(01) = p(10).

Exuma 2y ago
Damn, that is cool
- somenameforme 2y ago
  Yeah this is probably the neatest little 5 second math thing I've ever seen. Can't believe I hadn't seen this before.
  - soulofmischief 2y ago
    John von Neumann strikes again! Wikipedia: https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_... Original paper: https://mcnp.lanl.gov/pdf_files/InBook_Computing_1961_Neumann_JohnVonNeumannCollectedWorks_VariousTechniquesUsedinConnectionwithRandomDigits.pdf https://mcnp.lanl.gov/pdf_files/InBook_Computing_1961_Neuman...
- amelius 2y ago
  It's a nice trick, but it requires a lot of extra coin flips. Imagine you have a coin with p(1)=0.501, and you want 1000 random bits. With the proposed method, this will take about 4000 coin flips. Surely, since the coin is quite close to being fair, it should be possible to do it with far fewer flips ...
randomcatuser 2y ago
how do you get biased samples from a fair coin? (say, 0.3) (this one has less wow, i guess) 1. You take a string of fair samples 0101011101010 2. you split it into chunks of 3 (8 possibilities, so each one is 0.125 chance) 3. 000, 001, 010 -> 1, and all the rest is 0, which will get 0.275 chance Any better approaches?
layer8 2y ago
However, that stops working as soon as you have a biased coin with memory. ;)
jsmcgd 2y ago
Instead of discounting some of the results, can we alternate the value of the coin each toss? So on the first flip, heads is 0 and tails is 1, then on the next flip, heads is 1 and tails is 0.
- hansvm 2y ago
  That'll obtain the right average but won't have the same pairwise relations as an independent, unbiased coin. That's probably easiest to see if you imagine approaching an infinitely biased coin (100% heads, 0% tails). Your strategy alternates between 0 and 1 almost always. The listed strategy throws away most flips but gives actualy unbiased results when a pair does pass. Another way to look at it is from an entropy perspective. An unbiased, independent coin flip has 1 bit of entropy. A biased coin with, e.g., 99% heads has 0.0807 bits of entropy. On average, you need at least 12.377 such flips to emulate an unbiased, independent flip. Any strategy without some sort of rejection/continuation/... (like your proposal) is doomed to fail. I haven't checked if their proposal is actually optimal. Empirically, it's suggestive of having room for improvement. I'm seeing something like 101 flips on average instead of 12.377 for that 99% bias example.
  - hatthew 2y ago
    A general direction you could go is to use blocks greater than 2. For example, you flip the coin exactly 64 times, and discard the result unless there is exactly 1 tails and 63 heads. This happens about 22% of the time, so it's on average 290 flips to get a single sample. When you do get that sample, you convert the single tails' position within that 64 block into binary, and get a 6 bit number uniformly distributed 0-63, i.e. you get 6 bits of entropy. So on average 6/290=0.02 bits of entropy per flip, twice as good as using blocks of 2, though only a quarter as good as the theoretical upper bound. I picked "block of 64 with only a single tails" since it was simple, and I'm sure a mathematician could figure out how to optimize it much more, but my general point is to agree that there's definitely ways to get closer to the theoretical upper bound you mentioned.
deleted 2y ago
[deleted]
kingforaday 2y ago
Remember you also have to determine the coin is biased and the results are in a biased order. "An ideal unbiased coin might not correctly model a real coin, which could be biased slightly one way or another. After all, real life is rarely fair." https://www.eecs.harvard.edu/~michaelm/coinflipext.pdf https://www.eecs.harvard.edu/~michaelm/coinflipext.pdf
deleted 2y ago
[deleted]

Exuma 2y ago

Damn, that is cool

somenameforme 2y ago
Yeah this is probably the neatest little 5 second math thing I've ever seen. Can't believe I hadn't seen this before.
- soulofmischief 2y ago
  John von Neumann strikes again! Wikipedia: https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_... Original paper: https://mcnp.lanl.gov/pdf_files/InBook_Computing_1961_Neumann_JohnVonNeumannCollectedWorks_VariousTechniquesUsedinConnectionwithRandomDigits.pdf https://mcnp.lanl.gov/pdf_files/InBook_Computing_1961_Neuman...
amelius 2y ago
It's a nice trick, but it requires a lot of extra coin flips. Imagine you have a coin with p(1)=0.501, and you want 1000 random bits. With the proposed method, this will take about 4000 coin flips. Surely, since the coin is quite close to being fair, it should be possible to do it with far fewer flips ...

randomcatuser 2y ago

how do you get biased samples from a fair coin? (say, 0.3) (this one has less wow, i guess) 1. You take a string of fair samples 0101011101010 2. you split it into chunks of 3 (8 possibilities, so each one is 0.125 chance) 3. 000, 001, 010 -> 1, and all the rest is 0, which will get 0.275 chance Any better approaches?

layer8 2y ago

However, that stops working as soon as you have a biased coin with memory. ;)

jsmcgd 2y ago

Instead of discounting some of the results, can we alternate the value of the coin each toss? So on the first flip, heads is 0 and tails is 1, then on the next flip, heads is 1 and tails is 0.

hansvm 2y ago
That'll obtain the right average but won't have the same pairwise relations as an independent, unbiased coin. That's probably easiest to see if you imagine approaching an infinitely biased coin (100% heads, 0% tails). Your strategy alternates between 0 and 1 almost always. The listed strategy throws away most flips but gives actualy unbiased results when a pair does pass. Another way to look at it is from an entropy perspective. An unbiased, independent coin flip has 1 bit of entropy. A biased coin with, e.g., 99% heads has 0.0807 bits of entropy. On average, you need at least 12.377 such flips to emulate an unbiased, independent flip. Any strategy without some sort of rejection/continuation/... (like your proposal) is doomed to fail. I haven't checked if their proposal is actually optimal. Empirically, it's suggestive of having room for improvement. I'm seeing something like 101 flips on average instead of 12.377 for that 99% bias example.
- hatthew 2y ago
  A general direction you could go is to use blocks greater than 2. For example, you flip the coin exactly 64 times, and discard the result unless there is exactly 1 tails and 63 heads. This happens about 22% of the time, so it's on average 290 flips to get a single sample. When you do get that sample, you convert the single tails' position within that 64 block into binary, and get a 6 bit number uniformly distributed 0-63, i.e. you get 6 bits of entropy. So on average 6/290=0.02 bits of entropy per flip, twice as good as using blocks of 2, though only a quarter as good as the theoretical upper bound. I picked "block of 64 with only a single tails" since it was simple, and I'm sure a mathematician could figure out how to optimize it much more, but my general point is to agree that there's definitely ways to get closer to the theoretical upper bound you mentioned.

deleted 2y ago

[deleted]

kingforaday 2y ago

Remember you also have to determine the coin is biased and the results are in a biased order. "An ideal unbiased coin might not correctly model a real coin, which could be biased slightly one way or another. After all, real life is rarely fair." https://www.eecs.harvard.edu/~michaelm/coinflipext.pdf https://www.eecs.harvard.edu/~michaelm/coinflipext.pdf

deleted 2y ago

[deleted]