Binarization Trees and Random Number Generation
Sung-il Pae · IEEE Transactions on Information Theory · 2019
An m-extracting procedure produces unbiased random bits from a loaded dice with m faces, and its output rate, the average number of output per input is bounded by the Shannon entropy of the source. This information-theoretic upper bound can be achieved only asymptotically as the input size increases, by certain extracting procedures that we call asymptotically optimal. Although a computationally efficient asymptotically optimal 2-extracting procedure has been known for a while, its counterparts for m-ary input, m > 2, was found only recently, and they are still relatively complicated to describe. A binarization takes inputs from an m-faced dice and produce bit sequences to be fed into a binary extracting procedure to obtain random bits. Thus, binary extracting procedures give rise to an m-extracting procedure via a binarization. A binarization is to be called complete, if it preserves the asymptotic optimality, and such a procedure has been proposed by Zhou and Bruck. We show that a complete binarization naturally arises from a binary tree with m leaves. Therefore, there exist complete binarizations in abundance and Zhou-Bruck scheme is an instance of them. We now have a relatively simple way to obtain an asymptotically optimal and computationally efficient m-extracting procedure, from a binary one, because these binarizations are both conceptually and computationally simple. The well-known leaf entropy theorem and a closely related structure lemma play important roles in the arguments.