binarization trees and random number generation

• DOI: 10.48550/arxiv.1602.06058
• Publication Date: 2020-04-01
• Authors: Sung-Il Pae
• Keywords: FOS: Computer and information sciences; Computer Science - Information Theory; Information Theory (cs.IT); Computer Science - Data Structures and Algorithms; 0202 electrical engineering, electronic engineering, information engineering; Data Structures and Algorithms (cs.DS); 02 engineering and technology

8 pages<br/>An m-extracting procedure produces unbiased random bits from a loaded dice with m faces. 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. An entropy- preserving binarization is to be called complete, and such a procedure has been proposed by Zhou and Bruck. We show that there exist complete binarizations in abundance as naturally arising from binary trees with m leaves. The well-known leaf entropy theorem and a closely related structure lemma play important roles in the arguments.<br/>