4 ms·
Cool idea! I wonder what you mean concretely by “extract unbiased bits from unbiased integer”? Let’s say my experiment results in an index of 42, how do you co
by j7ake 5y ago
Cool idea! I wonder what you mean concretely by “extract unbiased bits from unbiased integer”?
Let’s say my experiment results in an index of 42, how do you convert that integer into information about a string of unbiased coin flips?
- steerablesafe 5y agoArithmetic coding. https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding
- eru 5y agoArithmetic coding is the industrial strength way to do this, yes! However, you can do much simpler and still be pretty efficient (and unbiased). Suppose your range was numbers between 1 to 49 (inclusive). If you get a number between 1 to 32, you interpret that as 5 bits. If you got a number between 33 to 48, you interpret that as 4 bits (because you have 16 == 2^4 possibilities between 33 to 48). If you hit 49, you just drop everything and sample again. So if you got 42, like j7ake suggested, that would be 42 - 32 = 10 = 0b1010. You can generalize this scheme to other numbers of possibilities.