Hacker News Reader

Comment by sidedishes | Hacker News Reader

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)

View on HN

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

That's basically how arithmetic coding works, isn't it?

https://en.wikipedia.org/wiki/Arithmetic_coding

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

Agreed.

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.

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

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

Ah thanks for the explanation. Makes a lot more sense with the fractional expansion.

But this requires you know p.

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

Reply on news.ycombinator.com