2016/02/19 by Sung-il Pae, Pae, Sung-il
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Arithmetic #Artificial intelligence #Binary number #Binary tree #Biology #Combinatorics #Computability, Logic, AI Algorithms #Computer science #Data Structures and Algorithms (cs.DS) #Dice #Discrete mathematics #Entropy (arrow of time) #FOS: Computer and information sciences #Information Theory (cs.IT) #Lemma (botany) #Mathematics #Pattern recognition (psychology) #Statistics #cs.DS #cs.IT #math.IT #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1602.06058
published in arXiv (Cornell University) (Cornell University) · 8 pages
openalex publication_date 2016/02/19 · arxiv created 2018/05/11 · arxiv updated 2018/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.