Optimal rolling of fair dice using fair coins

Mark Huber, Danny Vargas

In 1976, Knuth and Yao presented an algorithm for sampling from a finite distribution using flips of a fair coin that on average used the optimal number of flips. Here we show how…