Interval Algorithm for Random Number Generation

The random number generation problem with an arbitrary probability distribution by using a general biased $M$-coin is studied. An efficient and very simple algorithm based on the successive refinement of partitions of the unit interval $[0,1)$, which we call the {\em interval algorithm}, is proposed and analysed in detail which turns out to give a fairly tight evaluation on the efficiency. A generalization of the interval algorithm to the case where the target is not a single random number but is a Markov process or the process of repeated $M$-coin tosses is subject to a Markov transition is also investigated. In particular, an intrinsic analogy of the interval algorithm with the arithmetic decoding algorithm is also revealed.