Random variate generation using only finitely many unbiased, independently and identically distributed random bits

Understand

For any discrete probability distributions with bounded entropy, we can generate exactly a random variate using only a finite expected number of perfect coin flips.

• A perfect coin flip is the outcome of an unbiased Bernoulli random variable.
• Coin flips are unbiased, independently and identically distributed in all our work.
• We survey well-known algorithms for the discrete case such as the one from Knuth and Yao as well as the one from Han and Hoshi.