If you have a stream of random bits that you can consume, and these bits are
50% ones, and independent of each other then several cute tricks can be used to employ
them "economically".
If routine b() produces the next random bit then
-
if r() returns successive bits of the binary representation of a real number R between 0 and 1 then
int cut(){int B = b(), R = r();
if(B && ~R) return 1;
if (R && ~B) return 0;
return cut();}
returns a 1 with probability R
- and thus routine
int third() {while(1){if(b()) return 0; if(b()) return 1;}}
returns 1 with probability 1/3.
This can be simply explained as the comparison of a randomly selected real B,
uniformly between 0 and 1, and comparing its binary representation with the
bits of R (or 1/3) until a difference is found.
The expected number of random bits consumed is exactly 2.
Alas this is not good enough.
I use 2 bits of entropy to produce
–((1/3)log2(1/3) + (2/3)log2(2/3))
= .918296 bits of entropy conveyed by a bit in a 2:1 channel.
The descrepency indicates that this does not achieve the efficiency of
arithmetic coding.
I think there is an idea lurking here but I can't find it just now.
Its still a useful trick for when entropy is scarce.