Entropy and an optimal random number transformation (Corresp.)

Abstract

A simple proof is given of the optimality of the procedure of D. E. Knuth and A. C. Yao for transforming a random number with distribution <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(1/2, 1/2)</tex> into one with distribution <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(p_{1}, \cdots,p_{r})</tex> . A direct representation of the cost (average number of input symbols needed to output one symbol) of the optimal transformation is given in terms of entropy, a procedure that leads to a refined entropic upper bound to the cost.