A classic programming puzzle: given only a fair coin flip function, how do you simulate a fair dice roll? The post walks through three progressively harder questions. First, a basic rejection-sampling approach using 3 coin flips mapped to 8 outcomes (re-flipping on invalid results). Second, it proves no finite-time guarantee is possible since 2^n outcomes can never be evenly partitioned into 6 buckets. Third, it tackles the efficiency question using information theory: each coin flip yields 1 bit, each dice roll requires log2(6) bits, setting a lower bound. The optimal solution encodes a stream of coin flips as a binary fraction between 0 and 1, then converts to base 6 — an approach analogous to arithmetic coding.
Sort: