MichelangeRoll: Sculpting Rational Distributions Exactly and Efficiently

Abstract

Simulating an arbitrary discrete distribution $D\in [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/\epsilon )\log (m/\epsilon ))$ memory, the entropy cost of generating a ongoing sequence of $D$ is reduced to $H(D)+\epsilon$ per sample.

14 pages, 7 figures, RANDOM says no so here