2025/07/01 by Shao, Jui-Hsiang, Wang, Hsin-Po
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2507.00915
Simulating an arbitrary discrete distribution D ∈ [0, 1]n using fair coin tosses incurs trade-offs between entropy complexity and space and time complexity. Shannon's theory suggests that H(D) tosses are necessary and sufficient, but does not guarantee exact distribution. Knuth and Yao showed that a decision tree consumes fewer than H(D) + 2 tosses for one exact sample. Draper and Saad's recent work addresses the space and time aspect, showing that H(D) + 2 tosses, O(n log(n) log(m)) memory, and O(H(D)) operations are all it costs, where m is the common denominator of the probability masses in D and n is the number of possible outcomes. In this paper, MichelangeRoll recycles leftover entropy to break the "+2" barrier. With O((n + 1/ε) log(m/ε)) memory, the entropy cost of generating a ongoing sequence of D is reduced to H(D) + ε per sample.