4 ms·
A similar cute trick for making a coin with arbitrary bias p out of a fair coin: go through the (possibly infinite) binary expansion of p, flipping once for eac
by sidedishes 5y ago
A similar cute trick for making a coin with arbitrary bias p out of a fair coin: go through the (possibly infinite) binary expansion of p, flipping once for each digit. If you flip tails on a 1 or heads on a 0, go to the next digit and repeat. If you flip heads on a 1 or tails on a 0, stop and take that as your flip. (And if you get to the end of the expansion, you can think of it as only 0s now, so interpret it as tails)
- peeters 5y agoThis doesn't seem quite right, unless I'm misunderstanding. If your bias was 128 (10000000) by your algorithm you would get heads at least 50% of the time (heads on the first flip) and tails at least 25% of the time (heads then tails). I think instead of taking the "wrong" flip result when they don't match, you should treat "getting to the end" as heads and failing before that as tails (or vice versa).
- klipt 5y agop is a probability in range [0, 1]. So if p = 1/128, the expansion is 0.0000001. In this case the algorithm says you return tails unless you flip 7 heads in a row (which happens with probability 1/128).
- peeters 5y agoAh thanks for the explanation. Makes a lot more sense with the fractional expansion.
- klipt 5y agoIntuitively, you're building a random real number in the range [0, 1) bit by bit, and returning 0 or 1 once you're sure that number is above or below threshold p.
- eru 5y agoThat's basically how arithmetic coding works, isn't it? https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding
- steerablesafe 5y agoMy impression is that arithmetic coding is the inverse. You have N symbols with different known probabilities, and you turn it into a stream of 1/2 probability random bits. edit: On second thought this is probably a bijection and you can call it "arithmetic coding" in either direction.
- eru 5y agoAgreed. As far as I can tell, arithmetic coding needs both a compressor and a decompressor. Otherwise it's relatively useless in eg your fancy video file format.
- hyperbovine 5y agoBut this requires you know p.
- eru 5y agoWell, if you want to go backwards, you kind of have to know p? Though I can see an interesting problem: You have a known unbiased coin, and a biased coin with unknown p. Your task is to create a stream of coin flips with bias p. You want to minimize how often you have to flip the biased coin; and somehow work out a way to make use of the unbiased coin to 'stretch' your sequence of biased coin flips. I am not sure if this is possible.