Performance Analysis of the Interval Algorithm for Random Number Generation in the Case of Markov Coin Tossing

Yasutada OOHAMA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E103-A   No.12   pp.1325-1336
Publication Date: 2020/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2020TAP0008
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
random number generation,  interval algorithm,  Markov coin tossing,  number systems,  performance analysis,  

Full Text: FreePDF

In this paper we analyze the interval algorithm for random number generation proposed by Han and Hoshi in the case of Markov coin tossing. Using the expression of real numbers on the interval [0,1), we first establish an explicit representation of the interval algorithm with the representation of real numbers on the interval [0,1) based one number systems. Next, using the expression of the interval algorithm, we give a rigorous analysis of the interval algorithm. We discuss the difference between the expected number of the coin tosses in the interval algorithm and their upper bound derived by Han and Hoshi and show that it can be characterized explicitly with the established expression of the interval algorithm.