Interval Algorithm for Random Number Generation: Information Spectrum\n Approach

The problem of exactly generating a general random process (target process)\nby using another general random process (coin process) is studied. The\nperformance of the interval algorithm, introduced by Han and Hoshi, is analyzed\nfrom the perspective of information spectrum approach. When either the coin\nprocess or the target process has one point spectrum, the asymptotic optimality\nof the interval algorithm among any random number generation algorithms is\nproved, which demonstrates utility of the interval algorithm beyond the ergodic\nprocess. Furthermore, the feasibility condition of exact random number\ngeneration is also elucidated. Finally, the obtained general results are\nillustrated by the case of generating a Markov process from another Markov\nprocess.\n