Economizing on Entropy

I seek a scheme to send data thru a biased channel like arithmetic coding. I suppose it costs more to send 1’s than 0’s.

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();}

more obscurely:

int cut(){int B = b(), R = !r(); return B && R || (B || R) && cut();}

returns a 1 with probability R

and thus routine
int third() {while(1){if(b()) return 0; if(b()) return 1;}}
or
int third() {return b() && (b() || third());}
or even
int third() {return b() && !third();}
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)log₂(1/3) + (2/3)log₂(2/3)) = .918296 bits of entropy conveyed by a bit in a 2:1 channel. The discrepancy 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.

The original notion of arithmetic coding is most cleanly expressed in Scheme. The message is a real number m between 0 and 1. Given a channel with cost of 1 is R and cost of 0 is 1−R, a channel coder is yielded by

(define ((cc R) m) (let ((m m)) (lambda ()
  (let ((v (- m R))(r (> m R))) (set! m 
    (if r (/ (- m R) (- 1 R)) (/ m R))) (if r 1 0)))))

Invoking cc creates a procedure whose successive invocations produce the bits to be transmitted.

(define (Do n p) (let Do ((n n)) (if (> n 0) (let ((u (- n 1))) (p u) (Do u)))))
(let ((w ((cc 1/3) 0.2540226510663))) (Do 60 (lambda (j) (write (w)))))

yields: 011101100111001001110101001110111111111011101001101111111110