Hacker News Reader

Comment by ziofill | Hacker News Reader

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).

View on HN

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.

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.

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.

Damn, that is cool

Yeah this is probably the neatest little 5 second math thing I've ever seen. Can't believe I hadn't seen this before.

John von Neumann strikes again!

Wikipedia: https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_...

Original paper: https://mcnp.lanl.gov/pdf_files/InBook_Computing_1961_Neuman...

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 ...

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

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

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?

Reply on news.ycombinator.com