MichelangeRoll: Sculpting Rational Distributions Exactly and Efficiently

Jui-Hsiang Shao, Hsin-Po Wang

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 s…